TY - GEN

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

AU - Harikumar, G.

AU - Couvreur, Christophe

AU - Bresler, Yoram

PY - 1998/12/1

Y1 - 1998/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0031642386&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031642386&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.1998.681830

DO - 10.1109/ICASSP.1998.681830

M3 - Conference contribution

AN - SCOPUS:0031642386

SN - 0780344286

SN - 9780780344280

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 1877

EP - 1880

BT - Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 1998

T2 - 1998 23rd IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 1998

Y2 - 12 May 1998 through 15 May 1998

ER -