Parsimonious least norm approximation

A theoretically justifiable fast finite successive linear approximation algorithm is proposed for obtaining a parsimonious solution to a corrupted linear system Ax = b + p, where the corruption p is due to noise or error in measurement. The proposed linear-programming-based algorithm finds a solution x by parametrically minimizing the number of nonzero elements in x and the error ∥Ax – b – p∥1. Numerical tests on a signal-processing-based example indicate that the proposed method is comparable to a method that parametrically minimizes the 1-norm of the solution x and the error ∥Ax – b – p∥1, and that both methods are superior, by orders of magnitude, to solutions obained by least squares as well as by combinatorially choosing an optimal solution with a specific number of nonzero elements.