Sparse approximate solutions to linear systems.

*(English)* Zbl 0827.68054
Summary: The following problem is considered: given a matrix $A$ in ${\mathbb{R}}^{m\times n}$, ($m$ rows and $n$ columns), a vector $b$ in ${\mathbb{R}}^{m}$, and $\epsilon >0$, compute a vector $x$ satisfying ${|Ax-b|}_{2}\le \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\text{Opt}(\epsilon /2)|{\mathbf{A}}^{+}{|}_{2}^{2}{\text{ln}\left(\right|b|}_{2}/\epsilon )\rceil $ non-zero entries, where $\text{Opt}(\epsilon /2)$ is the optimum number of nonzero entries at error $\epsilon /2$, $\mathbf{A}$ is the matrix obtained by normalizing each column of $A$ with respect to the ${L}_{2}$ norm, and ${\mathbf{A}}^{+}$ is its pseudo-inverse.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |