Compressed sensing

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article may be too technical for most readers to understand. Please help improve this article to make it understandable to non-experts, without removing the technical details. The talk page may contain suggestions. (October 2012)

Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) 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.[1]Tomography, such as MRI and X-ray CT, is a prominent application.[2][3]

Contents

History [edit]

Several scientific fields used L1 techniques.[4] In statistics, the least-squares method was complemented by the L_1-norm, which was introduced by Laplace. Following the introduction of linear programming and Dantzig's simplex algorithm, the L_1-norm was used in computational statistics. In statistical theory, the L_1-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 L_1-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.[5] It was used in matching pursuit in 1993, the LASSO estimator by Robert Tibshirani in 1996[6] and basis pursuit in 1998.[7] 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.

Around 2004 Emmanuel Candès, Terence Tao and David Donoho discovered important results on the minimum amount of data needed to reconstruct an image even though the amount of data would be deemed insufficient by the Nyquist–Shannon criterion.[8][9] This work is the basis of compressed sensing as currently studied[according to whom?].

Method [edit]

Underdetermined linear system [edit]

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 (such as smoothness) 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 [edit]

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.[10] 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 L^2 norm—that is, minimize 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 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 L^0 "norm" by David Donoho. The quotation marks served two warnings. First, the number-of-nonzeros L^0-"norm" is not a proper F-norm, because it is not continuous in its scalar argument: nnzs(αx) is constant as α approaches zero. Unfortunately, authors now neglect the quotation marks and abused terminology—clashing with the established use of the L^0 norm for the space of measurable functions (equipped with an appropriate metric) or for the space of sequences with F–norm (x_n) \mapsto \sum_n{2^{-n} x_n/(1+x_n)}. [11]

Candès. et al., proved that for many problems it is probable that the L^1 norm is equivalent to the L^0 norm, in a technical sense: This equivalence result allows one to solve the L^1 problem, which is easier than the L^0 problem. Finding the candidate with the smallest L^1 norm can be expressed relatively easily as a linear program, for which efficient solution methods already exist.[12] 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.

Implementations [edit]

The field of compressive sensing is related to other topics in signal processing and computational mathematics, such as to 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.

Starting with the single-pixel camera[13] from Rice University, an up-to-date list of the most recent implementations of compressive sensing in hardware at different technology readiness level is available.[14] Some hardware implementations (like the one used in MRI or compressed genotyping) do not require an actual physical change, whereas other hardware require substantial re-engineering to perform this new type of sampling. Similarly, a number of hardware implementations already existed before 2004; however, while they were acquiring signals in a compressed manner, they generally did not use compressive sensing reconstruction techniques to reconstruct the original signal. The result of these reconstruction were suboptimal and have been greatly enhanced thanks to compressive sensing.[citation needed]

Compressed sensing is used in a camera sensor developed jointly by Sony and Stanford University aimed at the mobile phone market. The approach allows a reduction in image acquisition energy per image by as much as a factor 15. This, however, comes at the cost of complex decompression algorithms; the computational load involved may require an off-device implementation.[15]

Compressive sensing in the news [edit]

Compressed sensing was in the news as part of the single-pixel camera[13] from Rice University. Some aspects of compressed sensing were featured in Wired's "Engineers Test Highly Accurate Face Recognition".[16] A more recent article in Wired described compressed sensing as a full-fledged technique in "Using Math to Turn Lo-Res Datasets Into Hi-Res Samples".[17] Because the article was talking about sampling for MRI, some confusion might have occurred.[18][19]

See also [edit]

References [edit]

  1. ^ CS: Compressed Genotyping, DNA Sudoku - Harnessing high throughput sequencing for multiplexed specimen analysis
  2. ^ Compressive sampling makes medical imaging safer
  3. ^ [1]
  4. ^ List of L1 regularization ideas from Vivek Goyal, Alyson Fletcher, Sundeep Rangan, The Optimistic Bayesian: Replica Method Analysis of Compressed Sensing
  5. ^ Hayes, Brian, The Best Bits, American Scientist, July 2009
  6. ^ The Lasso page, at Robert Tibshirani's homepage. "Regression shrinkage and selection via the lasso". J. Royal. Statist. Soc B., Vol. 58, No. 1, pages 267-288
  7. ^ "Atomic decomposition by basis pursuit", by Scott Shaobing Chen, David L. Donoho, Michael, A. Saunders. SIAM Journal on Scientific Computing
  8. ^ E. J. Candès, J. Romberg and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math., 59 1207-1223, 2006 [2]
  9. ^ Donoho, D. L., Compressed Sensing, IEEE Transactions on Information Theory, V. 52(4), 1289–1306, 2006 [3]
  10. ^ Candès, E.J., & Wakin, M.B., An Introduction To Compressive Sampling, IEEE Signal Processing Magazine, V.21, March 2008 [4]
  11. ^ Stefan Rolewicz. Metric Linear Spaces.
  12. ^ L1-MAGIC is a collection of MATLAB routines [5]
  13. ^ a b http://dsp.rice.edu/cscamera
  14. ^ Compressive Sensing Hardware, http://sites.google.com/site/igorcarron2/compressedsensinghardware
  15. ^ David Schneider (March 2013). "New Camera Chip Captures Only What It Needs". IEEE Spectrum. Retrieved 2013-03-20. 
  16. ^ Engineers Test Highly Accurate Face Recognition
  17. ^ http://www.wired.com/magazine/2010/02/ff_algorithm/all/1
  18. ^ Why Compressed Sensing is NOT a CSI "Enhance" technology ... yet !
  19. ^ Surely You Must Be Joking Mr. Screenwriter

Further reading [edit]

Retrieved from "http://en.wikipedia.org/w/index.php?title=Compressed_sensing&oldid=555310175"