SPARSE APPROXIMATE SOLUTIONS TO LINEAR-SYSTEMS

The following problem is considered: given a matrix A in R(mxn), (m ro ws and n columns): a vector b in R(m), and epsilon > 0, compute a vect or x satisfying \\Ax - b\\(2) less than or equal to epsilon if such ex ists, such that x has the fewest number of non-zero entries over all s uch vectors. It is shown that the problem is NP-hard, but that the wel l-known greedy heuristic is good in that it computes a solution with a t most [18 Opt(epsilon/2)\\A(+)\\In-2(2)(\b\(2)/epsilon)] non-zero ent ries, 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.