Complexity-Matching Universal Signal Estimation in Compressed Sensing

In light to a recent update on ArXiv, I asked Dror Baron to provide me some context on his different papers related to universal signal recovery, here is what he had to say: 

Hello Igor,

Here's a link to a recent submission: http://arxiv.org/abs/1204.2611

I know that we have multiple related algorithms recently, so let me try to explain:

1. In a compressed sensing problem, y=A*x+z, this work is trying to solve xhat = argmin_w H(w)-log(f_Z(zhat=y-A*w)), where xhat is our estimate for x given y and A, w is a hypothesized solution, H(.) is entropy (in our case empirical entropy, which serves as a sort of universal coding length), and f_Z(.) is the density function for the noise. This algorithm seems to approach the minimum mean square error (MMSE) up to 3 dB or so, which is theoretically motivated. Our optimization algorithm relies on Markov chain Monte Carlo (MCMC).

2. In our paper from last week, we used a universal denoiser within approximate message passing. We hope that with some bells and whistles the algorithm might consistently outperform MCMC by that 3 dB gap.

Please feel free to let us know if you have any questions!

Dror

--

Dror Baron, Ph.D.

Assistant Professor

Electrical and Computer Engineering Department

North Carolina State University

http://people.engr.ncsu.edu/dzbaron/

Thanks Dror ! Here is the recent update: Complexity-Matching Universal Signal Estimation in Compressed Sensing by Junan Zhu, Dror Baron, Marco F. Duarte

We study the compressed sensing (CS) signal estimation problem where an input signal is measured via a linear matrix multiplication under additive noise. While this setup usually assumes sparsity or compressibility in the input 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. Inspired by Kolmogorov complexity and minimum description length, we focus on a maximum a posteriori (MAP) estimation framework that leverages universal priors to match the complexity of the source. Our framework can also be applied to general linear inverse problems where more measurements than in CS might be needed. We provide theoretical results that support the algorithmic feasibility of universal MAP estimation using a Markov chain Monte Carlo implementation, which is computationally challenging. We incorporate some techniques to accelerate the algorithm while providing comparable and in many cases better reconstruction quality than existing algorithms. Experimental results show the promise of universality in CS, particularly for low-complexity sources that do not exhibit standard sparsity or compressibility.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.