One Sketch for All: Fast Algorithms for Compressed Sensing

被引:124
作者
Gilbert, A. C. [1 ]
Strauss, M. J. [1 ]
Tropp, J. A. [1 ]
Vershynin, R.
机构
[1] Univ Michigan, Dept Math, Ann Arbor, MI 48109 USA
来源
STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING | 2007年
关键词
Approximation; embedding; group testing; sketching; sparse approximation; sublinear algorithms;
D O I
10.1145/1250790.1250824
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Compressed Sensing is a new paradigm for acquiring the compressible signals that arise in many applications. These signals can be approximated using an amount of information much smaller than the nominal dimension of the signal. Traditional approaches acquire the entire signal and process it to extract the information. The new approach acquires a small number of nonadaptive linear measurements of the signal and uses sophisticated algorithms to determine its information content. Emerging technologies can compute these general linear measurements of a signal at unit cost per measurement. This paper exhibits a randomized measurement ensemble and a signal reconstruction algorithm that satisfy four requirements: 1. The measurement ensemble succeeds for all signals, with high probability over the random choices in its construction. 2. The number of measurements of the signal is optimal, except for a factor polylogarithmic in the signal length. 3. The running time of the algorithm is polynomial in the amount of information in the signal and polylogarithmic in the signal length. 4. The recovery algorithm offers the strongest possible type of error guarantee. Moreover, it is a fully polynomial approximation scheme with respect to this type of error bound. Emerging applications demand this level of performance. Yet no other algorithm in the literature simultaneously achieves all four of these desiderata.
引用
收藏
页码:237 / 246
页数:10
相关论文
共 20 条
[1]  
[Anonymous], P 40 ANN C INF SCI S
[2]   ON THE FAST FOURIER-TRANSFORM OF FUNCTIONS WITH SINGULARITIES [J].
BEYLKIN, G .
APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 1995, 2 (04) :363-381
[3]  
CANDES EJ, 2004, NEAR OPTIMAL S UNPUB
[4]   Stable signal recovery from incomplete and inaccurate measurements [J].
Candes, Emmanuel J. ;
Romberg, Justin K. ;
Tao, Terence .
COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2006, 59 (08) :1207-1223
[5]  
COHEN A, 2006, COMPRESSED SEN UNPUB
[6]  
Cormode G, 2006, LECT NOTES COMPUT SC, V4056, P280
[7]   Compressed sensing [J].
Donoho, DL .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (04) :1289-1306
[8]   Data compression and harmonic analysis [J].
Donoho, DL ;
Vetterli, M ;
DeVore, RA ;
Daubechies, I .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1998, 44 (06) :2435-2476
[9]  
DUARTE MF, 2005, P SPARS05 RENN FRAN
[10]  
GILBERT AC, 2006, ALGORITHMIC LI UNPUB