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

G. Harikumar, Christophe Couvreur, Yoram Bresler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationProceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 1998
Pages1877-1880
Number of pages4
DOIs
StatePublished - Dec 1 1998
Event1998 23rd IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 1998 - Seattle, WA, United States
Duration: May 12 1998May 15 1998

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume3
ISSN (Print)1520-6149

Other

Other1998 23rd IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 1998
CountryUnited States
CitySeattle, WA
Period5/12/985/15/98

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Fast optimal and suboptimal algorithms for sparse solutions to linear inverse problems'. Together they form a unique fingerprint.

  • Cite this

    Harikumar, G., Couvreur, C., & Bresler, Y. (1998). Fast optimal and suboptimal algorithms for sparse solutions to linear inverse problems. In Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 1998 (pp. 1877-1880). [681830] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 3). https://doi.org/10.1109/ICASSP.1998.681830