Fast optimal and suboptimal algorithms for sparse solutions to linear inverse problems

We present two «fast» approaches to the NP-hard problem of computing a maximally sparse approximate solution to linear inverse problems, also known as the best subset selection. The first approach, a heuristic, is an iterative algorithm globally convergent to sparse elements of any given convex, compact S/spl sub/R/sup mx/. We demonstrate its effectiveness in bandlimited extrapolation and in sparse filter design. The second approach is a polynomial-time greedy sequential backward elimination algorithm. We show that if A has full column rank and /spl epsiv/ is small enough, then the algorithm will find the sparsest x satisfying /spl par/Ax-b/spl par//spl les//spl epsiv/, if such exists.