Suppose $x$ is an unknown vector in $\bR^m$ (depending on context, a digital image or signal); we plan to acquire data and then reconstruct. Nominally this `should' require $m$ samples. But suppose we know {\it a priori} that $x$ is compressible by transform coding with a known transform, and we are allowed to acquire data about $x$ by measuring $n$ general linear functionals -- rather than the usual pixels. If the collection of linear functionals is well-chosen, and we allow for a degree of reconstruction error, the size of $n$ can be dramatically smaller than the size $m$ usually considered necessary. Thus, certain natural classes of images with $m$ pixels need only $n = O(m^{1/4} \log(m))$ nonadaptive nonpixel samples for faithful recovery, as opposed to the usual $m$ pixel samples.

Our approach is abstract and general. We suppose that the object has a sparse representation in some orthonormal basis (eg. wavelet, Fourier) or tight frame (eg curvelet, Gabor), meaning that the coefficients belong to an $\ell^p$ ball for $0 < p \leq 1$. This implies that the $N$ most important coefficients in the expansion allow a reconstruction with $\ell^2$ error $O(N^{1/2-1/p})$. It is possible to design $n = O(N \log(N))$ {\it nonadaptive} measurements which contain the information necessary to reconstruct any such object with accuracy comparable to that which would be possible if the $N$ most important coefficients of that object were directly observable. Indeed, a good approximation to those $N$ important coefficients may be extracted from the $n$ measurements by solving a convenient linear program, called by the name Basis Pursuit in the signal processing literature. The nonadaptive measurements have the character of `random' linear combinations of basis/frame elements.

Underlying our results is a theoretical framework based on the theory of optimal recovery, the theory of $n$-widths, and information-based complexity. Our basic results concern properties of $\ell^p$ balls in high-dimensional Euclidean space in the case $0 < p \leq 1$. We estimate the Gel'fand $n$-widths of such balls, give a criterion for near-optimal subspaces for Gel'fand $n$-widths, show that `most' subspaces are near-optimal, and show that convex optimization can be used for processing information derived from these near-optimal subspaces. The techniques for deriving near-optimal subspaces include the use of almost-spherical sections in Banach space theory.