Beyond Sparsity: Signal Recovery in Compressed Sensing via Universal Priors

Following up on a recent series of entries, here it is: Signal Recovery in Compressed Sensing via Universal Priors by  Dror Baron and Marco Duarte, The abstract reads:

We study the compressed sensing (CS) signal estimation problem where an input is measured via a linear matrix multiplication under additive noise. While this setup usually assumes sparsity or compressibility in the observed signal during recovery, the signal structure that can be leveraged is often not known a priori. In this paper, we consider universal CS recovery, where the statistics of a stationary ergodic signal source are estimated simultaneously with the signal itself. We focus on a maximum a posteriori (MAP) estimation framework that leverages universal priors such as Kolmogorov complexity and minimum description length. We provide theoretical results that support the algorithmic feasibility of universal MAP estimation through a Markov Chain Monte Carlo implementation. We also include simulation results that showcase the promise of universality in CS, particularly for low-complexity sources that do not exhibit standard sparsity or compressibility.

From the conclusion:

Our expectation is that these initial results will spur additional work to improve the computational cost of implementing universal MAP estimation from linear measurements, including techniques that accelerate the convergence of MCMC. An alternative approach to implement universal MAP estimation could be obtained by moving from MCMC to other optimization algorithm such as belief propagation.

The code is available here. The following entries are of related interest:

• A Q&A with Marco Duarte and Dror Baron
• Minimum Complexity Pursuit
• EM-BG-AMP A Compressive Sensing Algorithm

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.