  This paper provides an extension of compressed sensing which bridges a
substantial gap between existing theory and its current use in real-world
applications. It introduces a mathematical framework that generalizes the three
standard pillars of compressed sensing - namely, sparsity, incoherence and
uniform random subsampling - to three new concepts: asymptotic sparsity,
asymptotic incoherence and multilevel random sampling. The new theorems show
that compressed sensing is also possible, and reveals several advantages, under
these substantially relaxed conditions. The importance of this is threefold.
First, inverse problems to which compressed sensing is currently applied are
typically coherent. The new theory provides the first comprehensive
mathematical explanation for a range of empirical usages of compressed sensing
in real-world applications, such as medical imaging, microscopy, spectroscopy
and others. Second, in showing that compressed sensing does not require
incoherence, but instead that asymptotic incoherence is sufficient, the new
theory offers markedly greater flexibility in the design of sensing mechanisms.
Third, by using asymptotic incoherence and multi-level sampling to exploit not
just sparsity, but also structure, i.e. asymptotic sparsity, the new theory
shows that substantially improved reconstructions can be obtained from fewer
measurements.
