Compressed sensing

Remarks

It is the case $\varepsilon = 0$ of sparse approximation, restricted to data that come from a sparse vector. Suppose every $2s$ columns of $A$ are linearly independent. Then an $s$-sparse $x$ is the only $s$-sparse solution of $Az = Ax$, since two such solutions differ by a $2s$-sparse vector in the kernel of $A$. A matrix with the restricted isometry property of order $2s$ and constant $\delta_{2s} < \sqrt{2} - 1$ allows recovery of $s$-sparse vectors by basis pursuit. Example: $A = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$, $s = 1$, $x = (0, 0, 2)$, $y = (2, 2)$. The solutions of $Az = y$ are $z = (2 - t, 2 - t, t)$, and $\norm{z}_1 = 2\abs{2 - t} + \abs{t}$ is minimal exactly at $t = 2$, so basis pursuit returns $x$. Non-example: for $A = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ and $s = 1$, the $1$-sparse vectors $e_1$ and $e_2$ give the same $y = (1, 0)$, so no method can recover both.