Minimum complexity pursuit for universal compressed sensing

Shirin Jalali, Arian Maleki, Richard G. Baraniuk

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


The nascent field of compressed sensing is founded on the fact that high-dimensional signals with simple structure can be recovered accurately from just a small number of randomized samples. Several specific kinds of structures have been explored in the literature, from sparsity and group sparsity to low-rankness. However, two fundamental questions have been left unanswered. What are the general abstract meanings of structure and simplicity? Do there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we address these two questions. Using algorithmic information theory tools such as the Kolmogorov complexity, we provide a unified definition of structure and simplicity. Leveraging this new definition, we develop and analyze an abstract algorithm for signal recovery motivated by Occam's Razor. Minimum complexity pursuit (MCP) requires approximately 2κ randomized samples to recover a signal of complexity κ and ambient dimension n. We also discuss the performance of the MCP in the presence of measurement noise and with approximately simple signals.

Original languageEnglish (US)
Article number6719502
Pages (from-to)2253-2268
Number of pages16
JournalIEEE Transactions on Information Theory
Issue number4
StatePublished - Apr 2014


  • Compressed sensing
  • Kolmogorov complexity
  • Structured signals
  • Universal coding

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Minimum complexity pursuit for universal compressed sensing'. Together they form a unique fingerprint.

Cite this