Computer Science – Information Theory
Scientific paper
2011-10-17
Computer Science
Information Theory
presented at 2011 Allerton Conference on Communication, Control and Computing
Scientific paper
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'? Do 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 Ocam's 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.
Jalali Shirin
Maleki Arian
No associations
LandOfFree
Minimum Complexity Pursuit does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Minimum Complexity Pursuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Complexity Pursuit will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-317186