Signal recovery from random measurements via orthogonal matching pursuit

被引：7236

作者：

Tropp, Joel A. ^{[1
,2
]}

Gilbert, Anna C. ^{[1
]}

机构：

[1] Univ Michigan, Dept Math, Ann Arbor, MI 48109 USA

[2] CALTECH, Pasadena, CA 91125 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2007年 / 53卷 / 12期

基金：

美国国家科学基金会;

关键词：

algorithms; approximation; basis pursuit; compressed sensing; group testing; orthogonal matching pursuit; signal recovery; sparse approximation;

D O I：

10.1109/TIT.2007.909108

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with m nonzero entries in dimension d given O(m 1n d) random linear measurements of that signal. This is a massive improvement over previous results, which require O(m(2)) measurements. The new results for OMP are comparable with recent results for another approach called Basis Pursuit (BP). In some settings, the OMP algorithm is faster and easier to implement, so it is an attractive alternative to BP for signal recovery problems.

引用

页码：4655 / 4666

页数：12

共 35 条

[1]

Ball K, 2001, HANDBOOK OF THE GEOMETRY OF BANACH SPACES, VOL 1, P161, DOI 10.1016/S1874-5849(01)80006-1

[2]

BARANIUK R, 2007, IN PRESS CONSTR APPR

[3]

Bjorck A., 1996, NUMERICAL METHODS LE, DOI DOI 10.1137/1.9781611971484

[4] Robust uncertainty principles:: Exact signal reconstruction from highly incomplete frequency information [J].

Candès, EJ ;

Romberg, J ;

Tao, T .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (02) :489-509

[5] Decoding by linear programming [J].

Candes, EJ ;

Tao, T .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (12) :4203-4215

[6] Near-optimal signal recovery from random projections: Universal encoding strategies? [J].

Candes, Emmanuel J. ;

Tao, Terence .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (12) :5406-5425

[7]

Chen SSB, 2001, SIAM REV, V43, P129, DOI [10.1137/S003614450037906X, 10.1137/S1064827596304010]

[8] An iterative thresholding algorithm for linear inverse problems with a sparsity constraint [J].

Daubechies, I ;

Defrise, M ;

De Mol, C .

COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2004, 57 (11) :1413-1457

[9] Adaptive greedy approximations [J].

Davis, G ;

Mallat, S ;

Avellaneda, M .

CONSTRUCTIVE APPROXIMATION, 1997, 13 (01) :57-98

[10]

DeVore R. A., 1998, Acta Numerica, V7, P51, DOI 10.1017/S0962492900002816

← 1 2 3 4 →