Title :
Fast optimal and suboptimal algorithms for sparse solutions to linear inverse problems
Author :
Harikumar, G. ; Couvreur, Christophe ; Bresler, Yoram
Author_Institution :
Coordinated Sci. Lab., Illinois Univ., Urbana, IL, USA
Abstract :
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⊂Rmx. 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 ε is small enough, then the algorithm will find the sparsest x satisfying ||Ax-b||⩽ε, if such exists
Keywords :
approximation theory; computational complexity; convergence of numerical methods; extrapolation; filtering theory; inverse problems; iterative methods; polynomials; NP-hard problem; bandlimited extrapolation; best subset selection; convergence; fast optimal algorithm; fast suboptimal algorithm; full column rank; heuristic approach; iterative algorithm; linear inverse problems; maximally sparse approximate solution; polynomial-time greedy sequential backward elimination; sparse filter design; sparse solutions; Convergence; Extrapolation; Filters; Inverse problems; Iterative algorithms; Linear approximation; NP-hard problem; Polynomials; Signal processing; Signal processing algorithms;
Conference_Titel :
Acoustics, Speech and Signal Processing, 1998. Proceedings of the 1998 IEEE International Conference on
Conference_Location :
Seattle, WA
Print_ISBN :
0-7803-4428-6
DOI :
10.1109/ICASSP.1998.681830