Sparse approximation

Remarks

The count $\norm{x}_0$ is not a norm, since $\norm{2x}_0 = \norm{x}_0$; the notation is standard anyway. Example: let $A = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$, $b = (1, 1)$ and $\varepsilon = 0$. The vector $x = (0, 0, 1)$ solves $Ax = b$ with $\norm{x}_0 = 1$, and no $x$ with $\norm{x}_0 = 0$ works since $b \ne 0$, so it solves problem 2. Non-example: $x = (1, 1, 0)$ also solves $Ax = b$, but $\norm{x}_0 = 2$ is not minimal, so it is not a solution of problem 2. Replacing $\norm{x}_0$ by the convex norm $\norm{x}_1 = \sum_j \abs{x_j}$ gives basis pursuit, a linear program; a penalized form of it is the Lasso.