Minimum complexity pursuit: Stability analysis

Shirin Jalali, Arian Maleki, Richard Baraniuk

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

4 Scopus citations


A host of problems involve the recovery of structured signals from a dimensionality reduced representation such as a random projection; examples include sparse signals (compressive sensing) and low-rank matrices (matrix completion). Given the wide range of different recovery algorithms developed to date, it is natural to ask whether there exist "universal" algorithms for recovering "structured" signals from their linear projections. We recently answered this question in the affirmative in the noise-free setting. In this paper, we extend our results to the case of noisy measurements.

Original languageEnglish (US)
Title of host publication2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012
Number of pages5
StatePublished - Oct 22 2012
Event2012 IEEE International Symposium on Information Theory, ISIT 2012 - Cambridge, MA, United States
Duration: Jul 1 2012Jul 6 2012


Other2012 IEEE International Symposium on Information Theory, ISIT 2012
Country/TerritoryUnited States
CityCambridge, MA

ASJC Scopus subject areas

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


Dive into the research topics of 'Minimum complexity pursuit: Stability analysis'. Together they form a unique fingerprint.

Cite this