CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

被引：2821

作者：

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 [J].