Optimum sparse approximations: A new class of algorithms

A vector in R^m is said to be sparse if a significant fraction of its components is zero. We address the problem of computing maximally sparse elements of a convex, compact set S of vectors in ]Rm. This problem arises in a wide range of engineering applications, including regularization of ill-posed problems, design of digital filters with few nonzero coefficients, and signal approximation by elements of an overcomplete set. Because the problem is N-P complete, there is a need to develop heuristic techniques that work well for specific problems. Our contribution is the development and theoretical analysis of a new class of iterative algorithms for identifying sparse elements of S. At every iteration, these algorithms compute the next point as the minimum of a convex function over S. We show that regardless of initialization, the iterates converge to a stationary point of a certain concave function over S. Thus, a connection is made to existing results about minimizing concave functions to compute sparse solutions. The very high asymptotic convergence rate derived for these algorithms for the case when S is a linear variety and the excellent performance demonstrated on some numerical examples suggest good potential in applications.