Sparse Approximate Solutions to Linear Systems

The following problem is considered: given a matrix A in R^m n, (m rows and n columns), a vector b in Rᵐ, and > 0, compute a vector x satisfying \|Ax - b\|₂ 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 18 Opt (/2) \| A^+\|₂^2 (\| b \|₂/) non-zero entries, where Opt (/2) is the optimum number of nonzero entries at error /2, A is the matrix obtained by normalizing each column of A with respect to the L₂ norm, and A^+ is its pseudo-inverse.