Compressed sensing

被引:20728
作者
Donoho, DL [1 ]
机构
[1] Stanford Univ, Dept Stat, Stanford, CA 94305 USA
关键词
adaptive sampling; almost-spherical sections of Banach spaces; Basis Pursuit; eigenvalues of random matrices; Gel'fand n-widths; information-based complexity; integrated sensing and processing; minimum l(1)-norm decomposition; optimal recovery; Quotient-of-a-Subspace theorem; sparse solution of linear equations;
D O I
10.1109/TIT.2006.871582
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Suppose x is an unknown vector in R-m (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(m(1/4) log(5/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 l(p), ball for O < p <= 1. The N most important coefficients in that expansion allow reconstruction with l(2) error O(N1/2-1/p). It is possible to design n = O (N log (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 l(p) balls in high-dimensional Euclidean space in the case 0 < p <= 1, 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.
引用
收藏
页码:1289 / 1306
页数:18
相关论文
共 44 条
[1]  
[Anonymous], 1993, Ten Lectures of Wavelets
[2]  
[Anonymous], 1997, A Wavelet Tour of Signal Processing
[3]  
[Anonymous], CURVES SURFACES
[4]  
Bergh J., 1976, INTERPOLATION SPACES
[5]  
CANDES E, 2004, NEAR OPTIMAL SIGNAL
[6]   New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities [J].
Candès, EJ ;
Donoho, DL .
COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2004, 57 (02) :219-266
[7]  
CANDES EJ, IN PRESS IEEE T INF
[8]  
CANDES EJ, 2004, 2 INT C COMP HARM AN
[9]   ENTROPY NUMBERS, S-NUMBERS, AND EIGENVALUE PROBLEMS [J].
CARL, B .
JOURNAL OF FUNCTIONAL ANALYSIS, 1981, 41 (03) :290-306
[10]   Atomic decomposition by basis pursuit [J].
Chen, SSB ;
Donoho, DL ;
Saunders, MA .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 1998, 20 (01) :33-61