  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-rankness. 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(3\kappa) randomized
samples to recover a signal of complexity \kappa and ambient dimension n. We
also discuss the performance of MCP in the presence of measurement noise and
with approximately simple signals.
