Skip to content

Compressed sensing

David L. Donoho

IEEE Transactions on Information Theory · 2006 · 24,429 citations

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Donoho, D. L. (2006). Compressed sensing. IEEE Transactions on Information Theory, 52(4), 1289–1306. https://doi.org/10.1109/tit.2006.871582

In text: (Donoho, 2006)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

Abstract

Suppose x is an unknown vector in Ropfm(a digital image or signal); we plan to measure n general linear functionals of x and then reconstruct. If x is known to be compressible by transform coding with a known transform, and we reconstruct via the nonlinear procedure defined here, the number of measurements n can be dramatically smaller than the size m. Thus, certain natural classes of images with m pixels need only n=O(m1/4log5/2(m)) nonadaptive nonpixel samples for faithful recovery, as opposed to the usual m pixel samples. More specifically, suppose x has a sparse representation in some orthonormal basis (e.g., wavelet, Fourier) or tight frame (e.g., curvelet, Gabor)-so the coefficients belong to an lscrpball for 02error O(N1/2-1p/). It is possible to design n=O(Nlog(m)) nonadaptive measurements allowing reconstruction with accuracy comparable to that attainable with direct knowledge of the N most important coefficients. Moreover, a good approximation to those N important coefficients is extracted from the n measurements by solving a linear program-Basis Pursuit in signal processing. The nonadaptive measurements have the character of "random" linear combinations of basis/frame elements. Our results use the notions of optimal recovery, of n-widths, and information-based complexity. We estimate the Gel'fand n-widths of lscrpballs in high-dimensional Euclidean space in the case 0<ples1, and give a criterion identifying near- optimal subspaces for Gel'fand n-widths. We show that "most" subspaces are near-optimal, and show that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces

  1. A Computational Approach to Edge Detection1986
  2. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images1984
  3. Scale-space and edge detection using anisotropic diffusion1990
  4. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems2009
  5. Active contours without edges2001

Metadata from OpenAlex (CC0). Citations are generated from the published record.