Least favorable compressed sensing problems for first-order methods

Arian Maleki, Richard Baraniuk

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

5 Scopus citations

Abstract

Compressed sensing (CS) exploits the compressibility of natural signals to reduce the number of samples required for accurate reconstruction. The cost for sub-Nyquist sampling has been computationally expensive reconstruction algorithms, including large-scale ℓ1 optimization. Therefore, first-order optimization methods that exploit only the gradient of the reconstruction cost function have been developed; notable examples include iterative soft thresholding (IST), fast iterative soft thresholding algorithm (FISTA), and approximate message passing (AMP). The performance of these algorithms has been studied mainly in the standard framework of convex optimization, called the deterministic framework here. In this paper, we first show that the deterministic approach results in overly pessimistic conclusions that are not indicative of algorithm performance in practice. As an alternative to the deterministic framework, we second study the theoretical aspects of the statistical convergence rate, a topic that has remained unexplored in the sparse recovery literature. Our theoretical and empirical studies reveal several hallmark properties of the statistical convergence of first-order methods, including universality over the matrix ensemble and the least favorable coefficient distribution.

Original languageEnglish (US)
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages134-138
Number of pages5
DOIs
StatePublished - 2011
Event2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation
Duration: Jul 31 2011Aug 5 2011

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8104

Other

Other2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Country/TerritoryRussian Federation
CitySt. Petersburg
Period7/31/118/5/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Least favorable compressed sensing problems for first-order methods'. Together they form a unique fingerprint.

Cite this