Abstract:
This paper demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with m nonzero ent...Show MoreMetadata
Abstract:
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 {\rm O}(m \ln d) random linear measurements of that signal. This is a massive improvement over previous results, which require {\rm 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.
Published in: IEEE Transactions on Information Theory ( Volume: 53, Issue: 12, December 2007)
References is not available for this document.
Select All
1.
S. Mallat and Z. Zhang, "Matching pursuits with time-frequency dictionaries", IEEE Trans. Signal Process., vol. 41, no. 12, pp. 3397-3415, Dec. 1993.
2.
B. D. Rao and K. Kreutz-Delgado, "An affine scaling methodology for best basisselection", IEEE Trans. Signal Process., vol. 47, no. 1, pp. 187-200, Jan. 1999.
3.
S. S. Chen, D. L. Donoho and M. A. Saunders, "Atomic decomposition by basis pursuit", SIAM Rev., vol. 43, no. 1, pp. 129-159, 2001.
4.
A. J. Miller, Subset Selection in Regression, U.K., London:Chapman and Hall, 2002.
5.
V. Temlyakov, "Nonlinear methods of approximation", Foundations of Comput. Math., vol. 3, no. 1, pp. 33-107, Aug. 2002.
6.
D.-Z. Du and F. K. Hwang, Combinatorial Group Testing and its Applications, Singapore:World Scientific, 1993.
7.
E. J. CandÈs and T. Tao, "Decoding by linear programming", IEEE Trans. Inf. Theory, vol. 51, no. 12, pp. 4203-4215, Dec. 2005.
8.
M. Rudelson and R. Veshynin, "Geometric approach to error correcting codes and reconstructionof signals", Int. Math. Res. Not., vol. 64, pp. 4019-4041, 2005.
9.
E. CandÈs, J. Romberg and T. Tao, "Robust uncertainty principles: Exact signal reconstructionfrom highly incomplete Fourier information", IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489-509, Feb. 2006.
10.
D. L. Donoho, "Compressed sensing", IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289-1306, Apr. 2006.
11.
E. J. CandÈs and T. Tao, "Near-optimal signal recovery from random projections: Universalencoding strategies?", IEEE Trans. Inf. Theory, vol. 52, no. 12, pp. 5406-5425, Dec. 2006.
12.
B. Efron, T. Hastie, I. Johnstone and R. Tibshirani, "Leastangle regression", Ann. Statist., vol. 32, no. 2, pp. 407-499, 2004.
13.
I. Daubechies, M. Defrise and C. D. Mol, "An iterative thresholding algorithm for linear inverse problemswith a sparsity constraint", Commun. Pure Appl. Math., vol. 57, pp. 1413-1457, 2004.
14.
D. Malioutov, M. Çetin and A. Willsky, "Homotopy continuation for sparse signalrepresentation", Proc. IEEE Intl. Conf. Acoustics Speech and Signal Processing, vol. 5, pp. 733-736, 2005.
15.
S.-J. Kim, K. Koh, M. Lustig, S. Boyd and D. Gorinevsky, “A method for large-scale -regularized least-squares problems with applications in signal processing and statistics”, 2007.
16.
M. A. T. Figueiredo, R. D. Nowak and S. J. Wright, “Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems”, 2007.
17.
Y. C. Pati, R. Rezaiifar and P. S. Krishnaprasad, "Orthogonal matching pursuit: Recursive function approximationwith applications to wavelet decomposition", Proc. 27th Annu. Asilomar Conf. Signals Systems and Computers, vol. 1, pp. 40-44, 1993-Nov.
18.
G. Davis, S. Mallat and M. Avellaneda, "Greedyadaptive approximation", Constr. Approx., vol. 13, pp. 57-98, 1997.
19.
R. DeVore and V. N. Temlyakov, "Some remarks on greedy algorithms", Adv. Comput. Math., vol. 5, pp. 173-187, 1996.
20.
J. A. Tropp, "Greed is good: Algorithmic results for sparseapproximation", IEEE Trans. Inf. Theory, vol. 50, no. 10, pp. 2231-2242, Oct. 2004.
21.
D. L. Donoho, " For most large underdetermined systems of linear equationsthe minimal \$lsb 1\$ -normsolution is also the sparsest solution ", Commun. Pure Appl. Math., vol. 59, no. 6, pp. 797-829, 2006.
22.
Å. BjÖrck, Numerical Methods for Least Squares Problems, PA, Philadelphia:SIAM, 1996.
23.
S. Kunis and H. Rauhut, "Random sampling of sparse trigonometric polynomials II:Orthogonal matching pursuit versus basis pursuit", Found. Comp. Math..
24.
Y. E. Nesterov and A. S. Nemirovski, Interior Point Polynomial Algorithms in Convex Programming, PA, Philadelphia:SIAM, 1994.
25.
R. A. DeVore, "Nonlinear approximation", Acta Numer., vol. 7, pp. 51-150, 1998.
26.
J. A. Tropp and A. C. Gilbert, “Signal recovery from random measurements via orthogonal matching pursuit: The Gaussian case”, 2007.
27.
K. Ball, "Convex geometry and functional analysis" in Handbook of Banach Space Geometry, The Netherlands, Amsterdam:Elsevier, pp. 161-193, 2002.
28.
G. Lugosi, Concentration of Measure Inequalities, 2005, [online] Available: .
29.
R. Baraniuk, M. Davenport, R. DeVore and M. Wakin, "A simple proof of the restricted isometry property for randommatrices", Constr. Approx., 2007.
30.
X. Fernique, "RegularitÉ des trajectoires des fonctions alÉatoires gausiennes" in Ecole DEtÉ de ProbabilitÉs de Saint-Flour IV, Germany, Berlin:Springer, vol. 480, pp. 1-96, 1974.
