Compressed sensing is a signal processing technique for efficiently acquiring and reconstructing
a signal, by finding solutions to underdetermined linear systems. This takes advantage of the
signal's sparseness or compressibility in some domain, allowing the entire signal to
be determined from relatively few measurements. MRI is a prominent application.
Overview A common goal of signal processing is to reconstruct
a signal from a series of sampling measurements. In general, this task is impossible because
there is no way to reconstruct a signal during the times that the signal is not measured.
Nevertheless, with prior knowledge or assumptions about the signal, it turns out to be possible
to perfectly reconstruct a signal from a series of measurements. Over time, mathematicians
have improved their understanding of which assumptions are practical and how they can
be generalized. An early breakthrough in signal processing
was the Nyquist–Shannon sampling theorem. It proved that a signal can be perfectly reconstructed
from sampling if the signal’s highest frequency is less than half of the sampling rate.
Around 2004, Emmanuel Candès, Terence Tao, and David Donoho proved that given knowledge
about a signal's sparsity, the signal may be reconstructed with even fewer samples than
the sampling theorem requires. This idea is the basis of compressed sensing.
History Compressed sensing relies on L1 techniques,
which several other scientific fields have used historically. In statistics, the least
squares method was complemented by the -norm, which was introduced by Laplace. Following
the introduction of linear programming and Dantzig's simplex algorithm, the -norm was
used in computational statistics. In statistical theory, the -norm was used by George W. Brown
and later writers on median-unbiased estimators. It was used by Peter Huber and others working
on robust statistics. The -norm was also used in signal processing, for example, in the
1970s, when seismologists constructed images of reflective layers within the earth based
on data that did not seem to satisfy the Nyquist–Shannon criterion. It was used in matching pursuit
in 1993, the LASSO estimator by Robert Tibshirani in 1996 and basis pursuit in 1998. There were
theoretical results describing when these algorithms recovered sparse solutions, but
the required type and number of measurements were sub-optimal and subsequently greatly
improved by compressed sensing. At first glance, compressed sensing might
seem to violate the sampling theorem, because compressed sensing depends on the sparsity
of the signal in question and not its highest frequency. This is a misconception, because
the sampling theorem guarantees perfect reconstruction given sufficient, not necessary, conditions.
A sampling method different from the classical fixed-rate sampling therefore cannot "violate"
the sampling theorem. Sparse signals with high frequency components can be highly under-sampled
using compressed sensing compared to classical fixed-rate sampling.
Method Underdetermined linear system
An underdetermined system of linear equations has more unknowns than equations and generally
has an infinite number of solutions. In order to choose a solution to such a system, one
must impose extra constraints or beliefs as appropriate.
In compressed sensing, one adds the constraint of sparsity, allowing only solutions which
have a small number of nonzero coefficients. Not all underdetermined systems of linear
equations have a sparse solution. However, if there is a unique sparse solution to the
underdetermined system, then the compressed sensing framework allows the recovery of that
solution. Solution / reconstruction method
Compressed sensing takes advantage of the redundancy in many interesting signals—they
are not pure noise. In particular, many signals are sparse, that is, they contain many coefficients
close to or equal to zero, when represented in some domain. This is the same insight used
in many forms of lossy compression. Compressed sensing typically starts with taking
a weighted linear combination of samples also called compressive measurements in a basis
different from the basis in which the signal is known to be sparse. The results found by
Emmanuel Candès, Justin Romberg, Terence Tao and David Donoho, showed that the number
of these compressive measurements can be small and still contain nearly all the useful information.
Therefore, the task of converting the image back into the intended domain involves solving
an underdetermined matrix equation since the number of compressive measurements taken is
smaller than the number of pixels in the full image. However, adding the constraint that
the initial signal is sparse enables one to solve this underdetermined system of linear
equations. The least-squares solution to such problems
is to minimize the norm—that is, minimize the amount of energy in the system. This is
usually simple mathematically. However, this leads to poor results for many practical applications,
for which the unknown coefficients have nonzero energy.
To enforce the sparsity constraint when solving for the underdetermined system of linear equations,
one can minimize the number of nonzero components of the solution. The function counting the
number of non-zero components of a vector was called the "norm" by David Donoho.
Candès. et al., proved that for many problems it is probable that the norm is equivalent
to the norm, in a technical sense: This equivalence result allows one to solve the problem, which
is easier than the problem. Finding the candidate with the smallest norm can be expressed relatively
easily as a linear program, for which efficient solution methods already exist. When measurements
may contain a finite amount of noise, basis pursuit denoising is preferred over linear
programming, since it preserves sparsity in the face of noise and can be solved faster
than an exact linear program. Applications
The field of compressive sensing is related to other topics in signal processing and computational
mathematics, such as underdetermined linear-systems, group testing, heavy hitters, sparse coding,
multiplexing, sparse sampling, and finite rate of innovation. Imaging techniques having
a strong affinity with compressive sensing include coded aperture and computational photography.
Implementations of compressive sensing in hardware at different technology readiness
levels is available. Photography
Compressed sensing is used in a mobile phone camera sensor. The approach allows a reduction
in image acquisition energy per image by as much as a factor of 15 at the cost of complex
decompression algorithms; the computation may require an off-device implementation.
Compressed sensing is used in single-pixel cameras from Rice University. Bell Labs employed
the technique in a lensless single-pixel camera that takes stills using repeated snapshots
of randomly chosen apertures from a grid. Image quality improves with the number of
snapshots, and generally requires a small fraction of the data of conventional imaging,
while eliminating lens/focus-related aberrations. Holography
Compressed sensing can be used to improve image reconstruction in holography by increasing
the number of voxels one can infer from a single hologram. It is also used for image
retrieval from undersampled measurements in optical and millimeter-wave holography.
Facial recognition Compressed sensing is being used in facial
recognition applications. Magnetic resonance imaging
Compressed sensing has been used to shorten magnetic resonance imaging scanning sessions
on conventional hardware. Reconstruction methods includes ISTA, FISTA, SISTA, etc.
Network tomography Compressed sensing has showed outstanding
results in the application of network tomography to network management. Network delay estimation
and network congestion detection can both be modeled as underdetermined systems of linear
equations where the coefficient matrix is the network routing matrix. Moreover, in the
Internet, network routing matrices usually satisfy the criterion for using compressed
sensing. Shortwave-infrared cameras
Commercial shortwave-infrared cameras based upon compressed sensing are available. These
cameras have light sensitivity from 0.9 µm to 1.7 µm, which are wavelengths invisible
to the human eye. Notes
See also Noiselet
Sparse approximation References
Further reading "The Fundamentals of Compressive Sensing"
Part 1, Part 2 and Part 3: video tutorial by Mark Davenport, Georgia Tech. at SigView,
the IEEE Signal Processing Society Tutorial Library.
Using Math to Turn Lo-Res Datasets Into Hi-Res Samples Wired Magazine article
Compressive Sensing Resources at Rice University. Compressed Sensing: The Big Picture
A list of different hardware implementation of Compressive Sensing
Compressed Sensing 2.0 Compressed Sensing Makes Every Pixel Count
– article in the AMS What's Happening in the Mathematical Sciences series
Nuit Blanche A blog on Compressive Sensing featuring the most recent information on the
subject Online Talks focused on Compressive Sensing
Wiki on sparse reconstruction Intuitive Compressive Sensing
CSS Lablanche & Company