Sparse Approximate Solutions to Linear Systems

The following problem is considered: given a matrix $A$ in ${\bf R}^{m \times n}$, ($m$ rows and $n$ columns), a vector $b$ in ${\bf R}^m$, and ${\bf \epsilon} 0$, compute a vector $x$ satisfying $\| Ax - b \|_2 \leq {\bf \epsilon}$ if such exists, such that $x$ has the fewest number of non-zero entries over all such vectors. It is shown that the problem is NP-hard, but that the well-known greedy heuristic is good in that it computes a solution with at most $\left\lceil 18 \mbox{ Opt} ({\bf \epsilon}/2) \|{\bf A}^+\|^2_2 \ln(\|b\|_2/{\bf \epsilon}) \right\rceil$ non-zero entries, where $\mbox{Opt}({\bf \epsilon}/2)$ is the optimum number of nonzero entries at error ${\bf \epsilon}/2$, ${\bf A}$ is the matrix obtained by normalizing each column of $A$ with respect to the $L_2$ norm, and ${\bf A}^+$ is its pseudo-inverse.