Compressed Sensing
Suppose you want to acquire data in 
, then
Nyquist’s sampling theorem places a lower bound on the number of
samples required. Mathematically, with a basis set
we can represent any function as an infinite
sum:
where for an orthonormal basis, the coefficients are given as:
In reality, we represent the samples in an appropriate basis and ignore values below some threshold. So, if we are going to approximate signals anyway, why not make a smaller number of measurements rather than each point as required by the sampling theorem? This is exactly the point of Compressed Sensing.
One of the pioneers of Compressed Sampling, David Donobo gives an example:
For certain classes of images with m pixels, choosing an appropriate set of linear functions, with a reasonable margin of reconstruction error lets us get away with only n non-adaptive non-pixel samples for faithful recovery. The size of n is dramatically smaller than m.
The bound on n is 
.
A news article in SIAM News further explains how this
reconstruction is accomplished by a 
norm
minimization. It also talks about how cutting down the number
of samples required has profound advantages — savings in money,
time or even tissue damage (as in the case of X-rays.) It also has an example of a numerical experiment where they perfectly
reconstruct a 512×512 image from just 512 Fourier coefficients,
that is with over 95% of the data missing.
The compressed sensing website at Rice is a great resource.
April 22nd, 2007 at 12:39 pm
Terence Tao’s excellent article on compressed sensing.
http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/