This raises a simple question: For a given signal, is it possible
to directly estimate the set of large α(n)α(n)'s that will not
be discarded? While this seems improbable, Candès, Romberg,
and Tao [10], [14] and Donoho [18] have
shown that a reduced set of projections can contain enough
information to reconstruct sparse signals. An offshoot of this
work, often referred to as *Compressed Sensing* (CS)
[9], [14], [11], [12], [8], [18], [19],
has emerged that builds on this principle.

In CS, we do not measure or encode the KK significant
α(n)α(n) directly. Rather, we measure and encode M<NM<N
projections y(m)=<x,φmT>y(m)=<x,φmT> of the
signal onto a *second set* of functions
{φm},m=1,2,...,M{φm},m=1,2,...,M. In matrix notation, we measure

where

yy is an

M×1M×1 column vector and the

*measurement basis* matrix

ΦΦ is

M×NM×N with each
row a basis vector

φmφm. Since

M<NM<N, recovery of
the signal

xx from the measurements

yy is ill-posed in general;
however the additional assumption of signal

*sparsity* makes
recovery possible and practical.

The CS theory tells us that when certain conditions hold, namely
that the functions {φm}{φm} cannot sparsely represent the
elements of the basis {ψn}{ψn} (a condition known as *incoherence* of the two dictionaries
[14], [10], [18], [29]) and the number of
measurements MM is large enough, then it is indeed possible
to recover the set of large {α(n)}{α(n)} (and thus the signal
xx) from a similarly sized set of measurements yy. This
incoherence property holds for many pairs of bases, including for
example, delta spikes and the sine waves of a Fourier basis, or
the Fourier basis and wavelets. Significantly, this incoherence
also holds with high probability between an arbitrary fixed basis
and a randomly generated one.

Comments:"A resource on sparse, compressible, and manifold signal models for signals processing and compressed sensing."