Abstract. Conventional wisdom and common practice in acquisition and reconstruction of images from frequency data follow the basic principle of the Nyquist density sampling theory. This principle states that to reconstruct an image, the number of Fourier samples we need to acquire must match the desired resolution of the image, i.e. the number of pixels in the image. This paper surveys an emerging theory which goes by the name of “compressive sampling” or “compressed sensing,” and which says that this conventional wisdom is inaccurate. Perhaps surprisingly, it is possible to reconstruct images or signals of scientiﬁc interest accurately and sometimes even exactly from a number of samples which is far smaller than the desired resolution of the image/signal, e.g. the number of pixels in the image.
It is believed that compressive sampling has far reaching implications. For example, it suggests the possibility of new data acquisition protocols that translate analog information into digital form with fewer sensors than what was considered necessary. This new sampling theory may come to underlie procedures for sampling and compressing data simultaneously.
In this short survey, we provide some of the key mathematical insights underlying this new theory, andexplainsomeoftheinteractionsbetweencompressivesamplingandotherﬁeldssuch as statistics, information theory, coding theory, and theoretical computer science.
One of the central tenets of signal processing is the Nyquist/Shannon sampling theory: the number of samples needed to reconstruct a signal without error is dictated by its bandwidth – the length of the shortest interval which contains the support of the spectrum of the signal under study. In the last two years or so, an alternative theory of“compressive sampling” has emerged which shows that super-resolved signals and images can be reconstructed from far fewer data/measurements than what is usually considered necessary. The purpose of this paper is to survey and provide some of the key mathematical insights underlying this new theory. An enchanting aspect of compressive sampling it that it has signiﬁcant interactions and bearings on some ﬁelds in the applied sciences and engineering such as statistics, information theory, coding theory, theoretical computer science, and others as well. We will try to explain these connections via a few selected examples.
From a general viewpoint,sparsity and,more generally,compressibility has played and continues to play a fundamental role in many ﬁelds of science. Sparsity leads to efﬁcient estimations;forexample,the quality of estimation by thresholding or shrinkage algorithms depends on the sparsity of the signal we wish to estimate. Sparsity leads to efﬁcient compression;for example,the precision of a transform coder depends on the sparsity of the signal we wish to encode . Sparsity leads to dimensionality reduction and efﬁcient modeling. The novelty here is that sparsity has bearings on the data acquisition process itself, and leads to efﬁcient data acquisition protocols.
Infact,compressive sampling suggests ways to economically translate analog data into already compressed digital form, . The key word here is “economically.” Everybody knows that because typical signals have some structure, they can be compressed efﬁciently without much perceptual loss. For instance, modern transform coders such as JPEG2000 exploit the fact that many signals have a sparse representation in a ﬁxed basis, meaning that one can store or transmit only a small number of adaptively chosen transform coefﬁcients rather than all the signal samples. The way this typically works is that one acquires the full signal, computes the complete set of transform coefﬁcients, encode the largest coefﬁcients and discard all the others. This process of massive data acquisition followed by compression is extremely wasteful (one can think about a digital camera which has millions of imaging sensors, the pixels, but eventually encodes the picture on a few hundred kilobytes). This raises a fundamental question: becausemostsignalsarecompressible,whyspendsomucheffort acquiring all the data when we know that most of it will be discarded? Wouldn’t it be possible to acquire the data in already compressed form so that one does not need to throw away anything? “Compressive sampling” also known as “compressed sensing”  shows that this is indeed possible.
This paper is by no means an exhaustive survey of the literature on compressive sampling. Rather this is merely an account of the author’s own work and thinking in this area which also includes a fairly large number of references to other people’s work and occasionally discusses connections with these works. We have done our best to organize the ideas into a logical progression starting with the early papers which launched this subject. Before we begin, we would like to invite the interested reader to also check the article  by Ronald DeVore – also in these proceedings – for a complementary survey of the ﬁeld (Section 5).
Consider the general problem of reconstructing a vector x ∈ RN from linear measurements y about x of the form yk =x,ϕk,k=1,...,K, or y = x. (2.1)
That is, we acquire information about the unknown signal by sensing x against K vectors ϕk ∈ RN. We are interested in the “underdetermined” case K N, where we have many fewer measurements than unknown signal values. Problems of this type ariseina countless number of applications. Inradiologyandbiomedicalimaging for i nstance, one is typically able to collect far fewer measurements about an image of interest than the number of unknown pixels. In wideband radio frequency signal analysis, one may only be able to acquire a signal at a rate which is far lower than the Nyquist rate because of current limitations in Analog-to-Digital Converter technology. Finally, gene expression studies also provide examples of this kind. Here, one would like to infer the gene expression level of thousands of genes–that is,thedimension N of the vector x is in the thousands – from a low number of observations, typically in the tens.