Abstract. The following problem is considered: given a matrix A in Rm'', (m rows and n columns), a vector b in Rm, and 6 > 0, compute a vector x satisfying IIAx bl[2 <_ 6 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(6/Z)llA + I1 ln(llbl12/6)] non-zero entries, where Opt(6/2) is the optimum number of nonzero entries at error 6/2, A is the matrix obtained by normalizing each column of A with respect to the L2 norm, and A + is its pseudo-inverse. Key words, sparse solutions, linear systems AMS subject classification. 68Q25 1. Introduction. The problem of computing a sparse approximate solution to a linear system is a fundamental problem in matrix computation. For matrices over the reals, the problem (variant thereof) has been studied under the name "subset selection" in statistical modeling by Golub and Van Loan (1983) . For binary matrices, the problem has been studied as "minimum weight solution" in error corrective coding by Gallager (1968). The related "sparse null-space" problem is of interest in nonlinear optimization; see Coleman and Pothen (1986) . Also, the "minimum set cover" problem can be viewed as computing a sparse solution to Ax >_ b, where all the entries are binary and the inequality is entry-wise; see Garey and Johnson (1979) , Johnson (1974). Our specific motivation for studying the problem is as follows. A widely used technique for the interpolation of irregularly spaced samples in higher dimensions is that of radial basis interpolation; see Hardy (1988). In brief, assign each of the given sample points a coefficient. The value of the interpolant at a new point is the weighted sum of these coefficients, where the weights are the distances of the respective samples from the new point. The coefficients themselves are the solution to the linear system of equations obtained by evaluating the interpolant at the each of the given points and equating them to the respective sample values; Michelli (1986) has shown that the linear system is always nonsingular. In solving the above linear system, two issues are of interest. (1) The cost of evaluating the interpolant at a general point grows with the number of nonzero coefficients in the solution. Hence, it is desirable to have as few nonzeros as possible, while tolerating some error in the
This is called optimal sparse approximation of y using dictionary A, and it is NP-hard REF .
Sparse Approximate Solutions to Linear Systems
SIAM J. Comput.
SIAM J. Comput.
Computer Science Mathematics