applicability of dictionary learning in compressed sensing problem

Question

Compressed Sensing Problem:

$Y = MX$, $M$ = measurement matrix (known), $X$ = full signal (unknown), $Y$ = sampled points (known). Objective is to obtain $X$ using the concept of sparsity i.e. $X = \phi S$, $S$ = sparse vector (unknown), and $\phi$ = a basis which converts the signal to a sparse domain (known). So $Y=M \phi S$, from this experssion we find $S$, and put it into $X = \phi S$ to get $X$.

Dictionary Learning Problem

$P = \psi Q$, $P$ is a signal (known), $Q$ = sparse vector (unknown), and $\psi$ = a basis which converts the signal $P$ to a sparse domain (unknown). We find $\psi$ and $Q$ using alternating minimization algorithms like k-svd.

My question is: Compressed sensing using Dictionary Learning

$Y=M \phi S$, $Y$ = sampled points (known), $M$ = measurement matrix (known), $S$ = sparse vector (unknown), and $\phi$ = a basis which converts the signal $Y$ to a sparse domain (unknown). Is this possible to solve at all?

Referring to appropriate references will also help a lot.

Answer 1

Why of course, it is certainly possible. As you already noted, dictionary learning is tightly coupled to sparse recovery, which is what you need for compressed sensing.

In DL, we are trying to factor $Y = D X$, which is only possible if additional assumptions are made. Typically that includes some notion of sparsity of $X$ and some additional normalization constraints on $D$. There are a few more conditions though to even render the problem unique. Note that $D$ might not be a basis, in general it is not even square. Typical strategies for DL include alternating optimization (have a look for MOD-based algorithms): starting from some guess about one of them, estimate the other one, and then take turns. This takes advantage of the fact that while finding both $D$ and $X$ is a hard (non-convex) problem, finding one of them given the other is much easier:

• Finding $D$ given $X$ (and $Y$) is a linear least squares problem
• Finding $X$ given $D$ (and $Y$) is a sparse recovery problem (which by itself is also non-convex but has nice convex relaxations that are quite well studied).

In the CS setup, we are encountering a similar situation, except that here, $D$ is typically composed of a measurement matrix we know (say, $\Phi$) and some sparsifying dictionary or basis (say, $A$) we may or may not know so that $D=\Phi A$ and $Y=D X = \Phi A X$. In this case $A$ could be a basis (i.e., it is square) but it could also be some more general dictionary (i.e., flat). The matrix $\Phi$ on the other hand is always flat. Given that, the above strategy still applies and you can apply alternating optimization:

• Finding $A$ given $\Phi$, $X$, and $Y$ is a linear least squares problem (unless you need $A$ to be a basis, which adds an orthonormality constraint)
• Finding $X$ given $\Phi$, $A$, and $Y$ is a sparse recovery problem (in no way different from what is already used in the CS context).

That said, there are strategies to optimize $D$ and $X$ jointly, like the K-SVD. They might not be directly applicable.