Does the use of a sparse basis in Compressed Sensing imply the need to have access to all the information beforehand?

Question

According to literature, the CS framework operates on the knowledge that most natural signals are sparse in some domain given by a sparsifying transform operation $\Phi$ (Fourier, Haar, WHT, etc.).

Following a single-pixel camera example, if we are trying to image a phenomenon described by a signal $x$, we use a sampling matrix $A$ to obtain a compressed measurement $y=A\Phi x$ of a representation of $x$ in the $\Phi$ domain, which is sparse.

• My question is, assuming we have some kind of physical single-pixel device (using a DMD to project linear combinations of $x$ (given by the sampling matrix $A$) onto a detector to obtain a measurement vector $y$), where does the sparsifying transform operation $\Phi$ manifest in this device?

• Do the DMD patterns correspond not to the sampling matrix $A$, but to the $A\Phi$ product?

• Must we provide the DMD with the signal in the sparse domain, $\Phi x$? In that case, don't we require previous knowledge of $x$ in its entirety in order to obtain its transform in the $\Phi$ domain? It is my understanding this is not the case, but I fail to grasp the mapping between the mathematical framework and hardware implementation in this matter.

Answer 1

It seems to me you have a little misassumption here. During the sampling only $\Phi$ matrix is applied to the signal $x$, which is resulted in measurements vector $y$, $y=Φx$ . Later, in reconstruction we use sparsity assumption to reconstruct the signal through solving problems of this form (there are other forms of solution):

$$\min|x|_1 s.t. |\Phi x-Y|_2 < \mu$$

with $\mu$ being a small figure. This means find an $x$ with minimum norm 1 length, that satisfies the second term. Till now, we assumed $x$ to be sparse in sampling domain (in case of images it is space, in case of signals it is time and in case of video it time-space). But what if the signal is not sparse in the sampling domain and it is sparse in transform domain. Do we have to get the transform of the signal/image prior to measuring it through $Φ$ matrix? No! we don't. We can still sample the sparse signal in time or space domain but modify the reconstruction problem so as to find the sparse signal of transformed signal. So, if the input signal has an sparse representation in a transform domain with operator of matrix $\Psi$, we can write $x=\Psi^{-1}a$ or $a=\Psi x$ and substitute it in the reconstruction problem as follows:

$$\min |a|_1 s.t. |\Phi\Psi^{-1}a-Y|_2 < \mu$$

So it is on reconstruction phase where we enter the sparsity and transform matrix to the problem and there is no need to have the transformed signal during the sampling.

Having said that, in response to your question:

Does this mean the DMD pattern represents the AΦ product?

No, DMD pattern only represent $\Phi$. The $A\Phi$ product appears later on in reconstruction phase, and it is not $A\Phi$ if by $A$ you meant transform matrix . It rather would be $\Phi A$