Minimum Complexity Pursuit for Universal Compressed Sensing

Abstract

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, namely: What are the general abstract meanings of "structure" and "simplicity"? And 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 just O(3κ) randomized samples to recover a signal of complexity κand ambient dimension n. We also discuss the performance of MCP in the presence of measurement noise and with approximately simple signals.

References in corpus (9)

• Message Passing Algorithms for Compressed Sensing
• High-Resolution Radar via Compressed Sensing
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Sampling and Recovery of Pulse Streams
• Compressed Sensing over ${\ell }_p$-balls: Minimax Mean Square Error
• Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP)
• An MCMC Approach to Universal Lossy Compression of Analog Sources
• Recovery from Linear Measurements with Complexity-Matching Universal Signal Estimation
• Signal Recovery on Incoherent Manifolds

Cited by in corpus (1)

• From compression to compressed sensing