PARSIMONIOUS LEAST NORM APPROXIMATION

A theoretically justifiable fast finite successive linear approximatio n algorithm is proposed for obtaining a parsimonious solution to a cor rupted linear system Ax = b + p, where the corruption p is due to nois e or error in measurement. The proposed linear-programming-based algor ithm finds a solution x by parametrically minimizing the number of non zero elements in x and the error parallel to Ax - b - p parallel to(1) . Numerical tests on a signal-processing-based example indicate that t he proposed method is comparable to a method that parametrically minim izes the 1-norm of the solution x and the error parallel to Ax -b - p parallel to(1), and that both methods are superior, by orders of magni tude, to solutions obtained by least squares as well by combinatoriall y choosing an optimal solution with a specific number of nonzero eleme nts.