We live in exciting times indeed. The following paper tries to give some theoretical framework to the issue of expanding compressive sensing beyond the lookng glass of sparsity. We already had a discussion with Dror Baron and Marco Duarte on the subject when they came out with Universal MAP Estimation in Compressed Sensing (implementation of their code is here, see also here for another related paper) in this Q&A with Marco Duarte and Dror Baron. Go read it, it is worthwhile, I'll wait. Today, the authors provide some framework, beyond the approach of Dror and Marco. The paper is Minimum Complexity Pursuit for Universal Compressed Sensing by Shirin Jalali, Arian Maleki, Richard Baraniuk. The abstract reads:
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-rankedness. 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(k log n) randomized samples to recover a signal of complexity k and ambient dimension n. We also discuss the performance of MCP in the presence of measurement noise and with approximately simple signals.
From the conclusion
In this paper, we have considered the problem of recovering structured signals from their linear measurements. We have used the Komogorov complexity of the quantized signal as a universal measure of complexity to both cover many of the examples explored in the CS literature and also provide a framework to analyze future structured signal models. We have shown that, if we consider low-complexity signals, then the minimum complexity pursuit (MCP) scheme inspired by Occam’s razor recovers the simplest solution of a set of random linear measurements. In fact, we have proved that the number of measurements required is proportional to the complexity and logarithmically to the ambient dimension of the signal. We have also considered more practical scenarios where the signal is not exactly low complexity but rather is “close” to a low complexity signal. We have shown that, even in such cases, the MCP algorithm provides a good estimate of the signal from much fewer samples than the ambient dimension of the signal. As mentioned above, Kolmogorov complexity of a sequence is not computable. However, currently we are working on deriving implementable schemes by replacing the Kolmogorov complexity by computable measures such as minimum description length [51].
......[51] J. Rissanen. Stochastic complexity and modeling. Ann. Stat., 14(3):1080–1100, Mar. 1986.
This is a synthesis based approach, I can't wait to see somebody taking a stab at the analysis approach.
Image Credit: NASA/JPL/Space Science Institute Full-Res: W00075371.jpg W00075371.jpg was taken on September 03, 2012 and received on Earth September 06, 2012. The camera was pointing toward SATURN at approximately 294,626 miles (474,154 kilometers) away, and the image was taken using the CB2 and CL2 filters. T |
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.
No comments:
Post a Comment