×

Analysis of the self projected matching pursuit algorithm. (English) Zbl 1458.94120

Summary: The convergence and numerical analysis of a low memory implementation of the orthogonal matching pursuit greedy strategy, which is termed self projected matching pursuit, is presented. This approach renders an iterative way of solving the least squares problem with much less storage requirement than direct linear algebra techniques. Hence, it is appropriate for solving large linear systems. The analysis highlights its suitability within the class of well posed problems.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)

Software:

CoSaMP; PDCO
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 33-61 (1998) · Zbl 0919.94002
[2] Donoho, D. L.; Tanner, J., Sparse nonnegative solution of underdetermined linear equations by linear programming, Proc. Natl. Acad. Sci. USA, 102, 9446-9451 (2005) · Zbl 1135.90368
[3] Elad, M., Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing (2010), Springer · Zbl 1211.94001
[4] Mallat, S. G.; Zhang, Z., Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41, 3397-3415 (1993) · Zbl 0842.94004
[5] Pati, Y. C.; Rezaiifar, R.; Krishnaprasad, P. S., Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition, Conference Record of the 27th Asilomar Conference on Signals, Systems and Computers, 1, 40-44 (1993)
[6] Natarajan, B. K., Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 227-234 (1995) · Zbl 0827.68054
[7] DeVore, R. A.; Temlyakov, V. N., Some remarks on greedy algorithms, Adv. Comput. Math., 5, 173-187 (1996) · Zbl 0857.65016
[8] Temlyakov, V. N., Greedy algorithms and m-term approximation with regard to redundant dictionaries, J. Approx. Theory, 98, 117-145 (1999) · Zbl 0926.65050
[9] Rebollo-Neira, L.; Lowe, D., Optimized orthogonal matching pursuit approach, IEEE Signal Process. Lett., 9, 137-140 (2002)
[10] Andrle, M.; Rebollo-Neira, L.; Sagianos, E., Backward-optimized orthogonal matching pursuit approach, IEEE Signal Proc. Let., 11, 705-708 (2004)
[11] Andrle, M.; Rebollo-Neira, L., A swapping-based refinement of orthogonal matching pursuit strategies, Signal Process., 86, 480-495 (2006) · Zbl 1163.94313
[12] Tropp, J. A., Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inf. Theory, 50, 2231-2242 (2004) · Zbl 1288.94019
[13] Gribonval, R.; Vandergheynst, P., On the exponential convergence of matching pursuits in quasi-incoherent dictionaries, IEEE Trans. Inf. Theory, 255-261 (2006) · Zbl 1309.94038
[14] Donoho, D. L.; Tsaig, Y.; Drori, I.; Starck, J., Stagewise orthogonal matching pursuit, IEEE Trans. Inf. Theory, 58, 1094-1121 (2006) · Zbl 1365.94069
[15] Blumensath, T.; Davies, M. E., Gradient pursuits, IEEE Trans. Signal Process., 56, 2370-2382 (2008) · Zbl 1390.94102
[16] Needell, D.; Tropp, J. A., CosaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26, 301-321 (2009) · Zbl 1163.94003
[17] Luo, M.; Sun, F.; Liu, H.; Lid, Z., A novel TS fuzzy systems identification with block structured sparse representation, J. Frankl. Inst., 351, 3508-3523 (2014) · Zbl 1290.93109
[18] You, C.; D. Robinson, C.; Vidal, R., Scalable sparse subspace clustering by orthogonal matching pursuit, Proceedings of Conference on Computer Vision and Pattern Recognition, 3918-3927 (2016)
[19] You, J.; Liu, Y.; Chen, J.; Ding, F., Iterative identification for multiple-input systems with time-delays based on greedy pursuit and auxiliary model, J. Frankl. Inst., 356, 5819-5833 (2019) · Zbl 1415.93088
[20] Friedman, J. H.; Stuetzle, W., Projection pursuit regression, J. Am. Stat. Assoc., 76, 817-823 (1981)
[21] Jones, L. K., On a conjecture of huber concerning the convergence of projection pursuit regression, Ann. Stat., 15, 880-882 (1987) · Zbl 0664.62061
[22] Rebollo-Neira, L.; Bowley, J., Sparse representation of astronomical images, J. Opt. Soc. Am. A, 30, 758-768 (2013)
[23] Rebollo-Neira, L., Effective sparse representation of x-ray medical image, Int. J. Numer. Methods Biomed. Eng., e2886 (2017)
[24] Rebollo-Neira, L.; Whitehouse, D., Sparse representation of 3d images for piecewise dimensionality reduction with high quality reconstruction, Array, 1 (2019)
[25] Rebollo-Neira, L.; Aggarwal, G., A dedicated greedy pursuit algorithm for sparse spectral representation of music sound, J. Acoust. Soc. Am., 140, 2933 (2016)
[26] Rebollo-Neira, L., On non-orthogonal signal representation, New Topics in Mathematical Physics Research (2006), Nova Science Publisher
[27] Casazza, P. G.; Kutyniok, G.; Philipp, F., Introduction to finite frame theory, Finite Frames: Theory and Applications, 1-54 (2012), Springer · Zbl 1281.42032
[28] Bartle, R. G.; D, R. S., Introduction to Real Analysis, 2012 (1999), John Wiley & Sons
[29] Björck, A., Numerical methods for least square problems (1996), SIAM · Zbl 0847.65023
[30] Golub, G. H.; Loan, C. F.V., Matrix Computations (2012), The John Hopkins University Press: The John Hopkins University Press Baltimore
[31] Higham, N. J., Accuracy and stability of numerical algoriths (2002), SIAM · Zbl 1011.65010
[32] Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1991), Cambridge University Press · Zbl 0729.15001
[33] Björck, A., Solving linear least squares problems by gram-schmidt orthogonalization, BIT Numer. Math., 7, 1-21 (1967) · Zbl 0183.17802
[34] Björck, A., Numerics of gram-schmidt orthogonalization, Linear Algebra Appl., 197, 297-316 (1994) · Zbl 0801.65039
[35] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Clarendon Press: Clarendon Press Oxford · Zbl 0258.65037
[36] Giraud, L.; Langou, J.; Rozložník, M.; van den Eshof, J., Rounding error analysis of the classical gram-schmidt orthogonalization process, Numer. Math., 101, 87-100 (2005) · Zbl 1075.65060
[37] Giraud, L.; Langou, J.; Rozložník, M., The loss of orthogonality in the gram-schmidt orthogonalization process, Comput. Math. Appl., 50, 1069-1075 (2005) · Zbl 1085.65037
[38] Stewart, G. W., Error analysis of the quasi-gram-schmidt algorithm, SIAM J. Matrix Anal. Appl., 27, 493-506 (2005) · Zbl 1091.65039
[39] Vleck, E. S.V., On the error in the product QR decomposition, SIAM J. Matrix Anal. Appl., 31, 1775-1791 (2010) · Zbl 1206.65147
[40] Stewart, G. W., On the numerical analysis of oblique projectors, SIAM J. Matrix Anal. Appl., 32, 309-348 (2011) · Zbl 1225.65046
[41] Leon, S. J.; Björck, A.; Gander, W., Gram-schmidt orthogonalization: 100 years and more authors, Numerical Linear Algebra, Numer. Linear Algebra Appl., 20, 492-532 (2013) · Zbl 1313.65086
[42] Rebollo-Neira, L.; Matiol, R.; Bibi, S., Hierarchized block wise image approximation by greedy pursuit strategies, IEEE Signal Process. Lett., 20, 1175-1178 (2013)
[43] Rebollo-Neira, L., Cooperative greedy pursuit strategies for sparse signal representation by partitioning, Signal Proces., 125, 365-375 (2016)
[44] http://www.nonlinear-approx.info/examples/node04.html(Last access April 2020).
[45] http://www.nonlinear-approx.info/examples/node1.html(Last access April 2020).
[46] http://www.nonlinear-approx.info/examples/node09.html(Last access April 2020).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.