  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.
