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 条

[31]

NEEDELL LD, 2008, FOUND COMPU IN PRESS

[32]

Nesterov Y, 1994, SIAM STUDIES APPL MA, V13, DOI 10.1137/1.9781611970791

[33]

RAUHUT H, 2008, THEORY SIGN IN PRESS, DOI DOI 10.1007/S10208-008-9031-3

[34]

REEVE G, 2008, P IEEE INT S INF THE