Clear understanding of compressed sensing

Question

I am trying to get a clear understanding of how compressed sensing works.

A continuous signal $x(t)$ is under-sampled (less samples are collected than the numbers required by the Nyquist theorem). The signal is sampled using a random matrix $\Psi$: $$y= \Psi x$$ where $\Psi$ is a random matrix (measurement matrix). The discrete signal $x[n]= \Phi s$, i.e. it has a sparse representation under the specific basis $\Phi$. Technically, there are multiple bases under which the signal is potentially sparse. The above equation becomes $$y=\Psi \Phi s$$ where the matrix $(\Psi \Phi)$ is not invertible since it is not a square matrix.

The system $y=\Psi \Phi s$ represents an underdetermined system of linear equations with zero or infinite solutions. The objective is to find the sparsest solution $s$. The vector $s$ is a vector containing the coefficients for the random basis vector represented by the columns of the matrix $\Psi \Phi$. Is that correct?

By imposing specific and extra conditions, the underdetermined system is solvable if we look for the sparsest of the solutions $s$ via a minimization process of the $L1$-norm. Is that correct?

Do we need to know a priori, before applying CS, the basis in which the signal is sparse?

What characteristics does the random sensing matrix $\Psi$ need to have? Are its rows supposed to be independent vectors?

Answer 1

Let clarify some points first. In $y= \Psi x$, the time continuous signal, $x(t)$, is not sampled but actually instead we take random measurements (sampled and combine) from a grid, i.e., implicitly Nyquist-sampled $x[n]$ signal. This is done for example by "Analog to Information Convertors". They leverage compressive sensing to minimize signal quantization (and sometime sampling). Another small thing on notation; it is common to have $\Phi$ for measurement matrix and $\Psi$ for transform matrix.

The vector s is a vector containing the coefficients for the random basis vector represented by the columns of the matrix $\Psi \Phi$. Is that correct?

Yes. For sake of simplicity assume a time-sparse signal measured using a random matrix as below. The vector $y$, is linear weighted summation of three column (marked by red) from matrix $\Psi$.

The problem of recovering, $x$ from $y$, is all about which columns of matrix $\Psi$ contributed to $y$. If we know that, we can drop all other columns and only keep those contributing columns. In the following picture it is only 3 columns, so a new 9-by-3 matrix can be form and hence the system of equations become overdetermined and solvable. If signal is not sparse in a different domain still same concept applies. Now, back to your questions:

Do we need to know a priori, before applying CS, the basis in which the signal is sparse?

No, the signal can be measured in, e.g., time but reconstructed using Fourier basis. To recover the signal we need to know which basis represents the signal in sparsest form.

What characteristics does the random sensing matrix $\Psi$ need to have?

In essence of signal recovery we need to know which columns of $A=\Psi \Phi$ contribute to $y$. So, the columns of $A$ must be as distinguishable from each other as possible, i.e., be highly incoherence. Having random measurement matrix with very high probability guarantees such a condition.