Examples


The central idea in compressive sampling is that the number of samples we need to capture a signal depends primarily on its structural content, rather than its bandwidth.

As a concrete example, suppose that f is a discrete signal (of length 256) composed of 16 complex sinusoids of whose frequencies, phases, and amplitudes are unknown.  As such, the discrete Fourier transform (DFT) of f has 16 nonzero components (illustrated below).

Fourier transform of f

How many time-domain samples do we need to capture f?  As there are no restriction on the frequencies in f, it is not at all bandlimited; any of the 256 components of the DFT can be nonzero.  The Shannon/Nyquist theory then says that to recover this signal (via linear "sinc'' interpolation), we will need to have all 256 samples in the time domain.

Now suppose that we are given only 80 samples.  Below is a plot of f in the time domain, the observed samples are in red.

f in the time domain

Of course, we will not be able to "fill in" the missing samples using sinc interpolation (or any other kind of linear method). 
But since we know that the signal we wish to recover is "sparse", we can take a different approach to the problem.  Given these 80 observed samples, the set of length-256 signals that have samples that match our observations is an affine subspace of dimension 256-80=176.  From the candidate signals in this set, we choose the one whose DFT has minimum L1 norm; that is, the sum of the magnitudes of the Fourier transform is the smallest.  In doing this, we are able to recover the signal exactly!

Recovered signal, time domain