Minimum Complexity Pursuit

After writing up the conversation with Dror and Marco that featured their earlier work ([1],[2]), I came across the following arxiv preprint, that aims at producing performance guarantees (even though no algorithm is proposed) for a similar approach, woohoo! Minimum Complexity Pursuit by Shirin Jalali and Arian Maleki. The abstract reads:

The fast growing field of compressed sensing is founded on the fact that if a signal is simple and has some ‘structure’, then it can be reconstructed accurately with far fewer samples than its ambient dimension. Many different plausible structures have been explored in this field, ranging from sparsity to low-rankness and to finite rate of innovation. However, there are important abstract questions that are yet to be answered. For instance, what are the general abstract meanings of structure and simplicity? Does there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we aim to address these two questions. Using algorithmic information theory tools such as Kolmogorov complexity, we provide a unified method of describing simplicity and structure. We then explore the performance of an algorithm motivated by Ocams Razor (called MCP for minimum complexity pursuit) and show that it requires O(k log n) number of samples to recover a signal, where k and n represent its complexity and ambient dimension, respectively. Finally, we discuss more general classes of signals and provide guarantees on the performance of MCP.

We now have a working algorithm and some interesting performance bounds. It looks like the next thing is to increase the speed of these solvers. Let us recall that once the community focused on that aspect of things back in 2005, we had a generic 10-fold improvement every year for the next three years. 

In other news, but still related to decreasing the number of measurements to less than required by the Donoho-Tanner transition (since this also what the Kolmogorov complexity approach is doing) Florent Krzakala will make a presentation of his recent findings on November 7th from 11:15 till 12:15 at ESPCI ( Bibliothèque PCT - F3.04). I hope I'll be able to get in time this time. Last time, the guards at the fence asked me to show IDs, sign some registry and name a contact person while they were waving the pretty girls in. I need to be in the habit of smiling more often.

[1] Universal MAP Estimation in Compressed Sensing by Dror Baron, Marco Duarte. The universal compressed sensing estimation software is here.

[2] D. Baron, "Information complexity and estimation," Fourth Workshop Inf. Theoretic Methods Science Eng. (WITMSE 2011), Helsinki, Finland, August 2011 (pdf, arxiv, talk)

Image Credit: NASA/JPL/Space Science Institute, N00177233.jpg was taken on October 19, 2011 and received on Earth October 19, 2011. The camera was pointing toward ENCELADUS at approximately 55,786 kilometers away, and the image was taken using the CL1 and CL2 filters. This image has not been validated or calibrated. A validated/calibrated image will be archived with the NASA Planetary Data System in 2012.



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.