SPARSE APPROXIMATE SOLUTIONS TO LINEAR-SYSTEMS

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