Sparse Approximate Solutions to Linear Systems

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 at most $\left\lceil 18 \mbox{ Opt} ({\bf \epsilon}/2) \|{\bf A}^+\|^2_2 \ln(\|b\|_2/{\bf

Abstract

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 $\epsilon > 0$, compute a vector x satisfying $\|Ax - b\|_{2} \leq \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 $\lceil 18 \operatorname{Opt}(\epsilon/2)\|{\bf A}^{+}\|_{2}^{2} \ln ({\| b \|_{2}/\epsilon})\rceil$ non-zero entries, where $\operatorname{Opt}(\epsilon/2)$ is the optimum number of nonzero entries at error $\epsilon/2$, ${\textbf{A}}$ is the matrix obtained by normalizing each column of A with respect to the $L_{2}$ norm, and $\textbf{A}^{+}$ is its pseudo-inverse.