CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

被引：2780

作者：

Needell, D. ^{[1
]}

Tropp, J. A. ^{[2
]}

机构：

[1] Univ Calif Davis, Dept Math, Davis, CA 95616 USA

[2] CALTECH, Pasadena, CA 91125 USA

来源：

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS | 2009年 / 26卷 / 03期

关键词：

Algorithms; Approximation; Basis pursuit; Compressed sensing; Orthogonal matching pursuit; Restricted isometry property; Signal recovery; Sparse approximation; Uncertainty principle; RECONSTRUCTION;

D O I：

10.1016/j.acha.2008.07.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Compressive sampling offers a new paradigm for acquiring signals that are compressible with respect to an orthonormal basis. The major algorithmic challenge in compressive sampling is to approximate a compressible signal from noisy samples. This paper describes a new iterative recovery algorithm called CoSaMP that delivers the same guarantees as the best optimization-based approaches. Moreover, this algorithm offers rigorous bounds on computational cost and storage. It is likely to be extremely efficient for practical problems because it requires only matrix-vector multiplies with the sampling matrix. For compressible signals, the running time is just C(N log(2) N), where N is the length of the signal. Published by Elsevier Inc.

引用

页码：301 / 321

页数：21

共 40 条

[1] [Anonymous], 1996, Numerical Methods for Least Squares Problems, DOI DOI 10.1137/1.9781611971484
[2] Robust uncertainty principles:: Exact signal reconstruction from highly incomplete frequency information
Candès, EJ
Romberg, J
Tao, T
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (02) : 489 - 509
[3] Decoding by linear programming
Candes, EJ
Tao, T
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (12) : 4203 - 4215
[4] The restricted isometry property and its implications for compressed sensing
Candes, Emmanuel J.
[J]. COMPTES RENDUS MATHEMATIQUE, 2008, 346 (9-10) : 589 - 592
[5] Near-optimal signal recovery from random projections: Universal encoding strategies?
Candes, Emmanuel J.
Tao, Terence
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (12) : 5406 - 5425
[6] Stable signal recovery from incomplete and inaccurate measurements
Candes, Emmanuel J.
Romberg, Justin K.
Tao, Terence
[J]. COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2006, 59 (08) : 1207 - 1223
[7] Cohen A., 2006, COMPRESSED SENSING B
[8] Cormen TH., 2001, Introduction to Algorithms
[9] Cormode G., 2005, COMBINATORIAL ALGORI
[10] Dai W., 2009, Subspace pursuit for compressive sensing signal reconstruction

← 1 2 3 4 →