Compressed sensing, also known as compressive sensing, compressive sampling and sparse sampling, is a technique for acquiring and reconstructing a signal utilizing the prior knowledge that it is sparse or compressible. The field has existed for at least four decades, but recently the field has exploded, in part due to several important results by David Donoho, Emmanuel Candes, Justin Romberg and Terence Tao.
The ideas behind compressive sensing came together in 2004 when Emmanuel J. Candès, a mathematician at Caltech, was working on a problem in magnetic resonance imaging. He discovered that a test image could be reconstructed exactly even with data deemed insufficient by the Nyquist-Shannon criterion. Also, a precursor of compressed sensing was seen 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.[1]
The main idea behind compressed sensing is to exploit that there is some structure and redundancy in most interesting signals—they are not pure noise. In particular, most signals are sparse, that is, they contain many coefficients close to or equal to zero, when represented in some domain[2]. (This is the same insight used in many forms of lossy compression.)
Compressed sensing typically starts with taking a limited (possibly randomized) number of samples in a basis different from the basis in which the signal is known to be sparse. Since the number of samples are limited, the task of converting the image back into the intended domain would involve solving an underdetermined matrix equation—that is, there are a huge number of different candidate images that could all result in the given samples, since the number of samples taken is smaller than the number of coefficients in the full image. Thus, one must introduce some additional constraint to select the “best” candidate.
The classical solution to such problems would be minimizing the L2 norm—that is, minimizing the amount of energy in the system. This is usually simple mathematically (involving only a matrix multiplication by the pseudo-inverse of the basis sampled in). However, this leads to poor results for most practical applications, as the unknown (not sampled) coefficients seldom have zero energy.
A more attractive solution would be minimizing the L0 norm, or equivalently maximize the number of zero coefficients in the new basis. However, this is NP-hard (it contains the subset-sum problem), and so is computationally infeasible for all but the tiniest data sets. Thus, following Tao et al., the L1 norm, or the sum of the absolute values, is usually what is minimized. Finding the candidate with the smallest L1 norm can be expressed relatively easily as a linear program, for which efficient solution methods already exist. This leads to comparable results as using the L0 norm, often yielding results with many coefficients being zero.
References
- ^ Hayes, Brian, The Best Bits, American Scientist, July 2009 [1]
- ^ Candès, E.J., & Wakin, M.B., An Introduction To Compressive Sampling, IEEE Signal Processing Magazine, V.21, March 2008 [2]
Further reading
- Compressive Sensing Resources at Rice University.
- Compressed Sensing: The Big Picture
- Compressed Sensing 2.0
- Compressed Sensing Makes Every Pixel Count - article in the AMS What's Happening in the Mathematical Sciences series
 |
This signal processing-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
