Research PaperNo Access

Efficiency of the weak Rescaled Pure Greedy Algorithm

Bing Jiang

School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, P. R. China

Search for more papers by this author

and

Peixin Ye

School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, P. R. China

E-mail Address: yepx@nankai.edu.cn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0219691321500016Cited by:7 (Source: Crossref)

Abstract

We study the efficiency of the Weak Rescaled Pure Greedy Algorithm (WRPGA) with respect to a dictionary in a Hilbert space or more generally a Banach space. We obtain the sufficient and necessary conditions for the convergence of WRPGA for any element and any dictionary. This condition is weaker than the sufficient conditions for convergence of the Weak Pure Greedy Algorithm (WPGA). In addition, we establish the noisy version of the error estimate for the WRPGA, which implies the results on sparse classes obtained in [G. Petrova, Rescaled pure greedy algorithm for Hlibert and Banach spaces, Appl. Comput. Harmon. Anal.41(3) (2016) 852–866].

Keywords:

AMSC: 41A65, 41A50, 41A46, 94A15, 94A08

References

1. A. Baron, A. Cohen, W. Dahmen and R. DeVore , Approximation and learning by greedy algorithm, Ann. Stat. 36 (2008) 64–94. Web of Science, Google Scholar
2. R. Budinich and G. Plonka , A tree-based dictionary learning framework, Int. J. Wavelets, Multiresolut. Inf. Process. 18(5) (2020), Article ID: 20550041. Web of Science, Google Scholar
3. A. Cohen, W. Dahmen and R. DeVore , Compressed sensing and best k-term approximation, J. Am. Math. Soc. 22(1) (2009) 211–231. Crossref, Web of Science, Google Scholar
4. R. A. DeVore and V. N. Temlyakov , Some remarks on greedy algorithms, Adv. Comput. Math. 5(2–3) (1996) 173–187. Crossref, Web of Science, Google Scholar
5. R. DeVore , Nonlinear approximation, Acta. Numer. 7 (1998) 51–150. Crossref, Google Scholar
6. M. J. Donahue, C. Darken, L. Gurvits and E. Sontag , Rates of convex approximation in non-Hilbert spaces, Constr. Approx. 13 (1997) 187–220. Crossref, Web of Science, Google Scholar
7. A. V. Dereventsov and V. N. Temlyakov , A unified way of analyzing some greedy algorithms, J. Funct. Anal. 277(12) (2019), Article ID: 108286. Crossref, Web of Science, Google Scholar
8. V. V. Galatenko and E. D. Livshits , Generalized approximate weak greedy algorithms, Mat. Zametki 78(2) (2005) 186–201. Google Scholar
9. R. Gribonval and M. Nielsen , Approximate Weak Greedy algorithms, Adv. Comput. Math. 14(4) (2001) 361–378. Crossref, Web of Science, Google Scholar
10. S. V. Konyagin and V. N. Temlyakov , Rate of convergence of pure greedy algorithm, East J. Approx. 5(4) (1996) 493–499. Google Scholar
11. J. Lindenstrauss and L. Tzafriri , Classical Banach Spaces II (Springer, Berlin, 1979). Crossref, Google Scholar
12. E. D. Livshitz and V. N. Temlyakov , On the convergence of Weak Greedy algorithms, Tr. Mat. Inst. Steklov 232 (2001) 236–247. Google Scholar
13. E. D. Livshits and V. N. Temlyakov , Two lower estimates in greedy approximation, Constr. Approx. 19 (2003) 509–524. Crossref, Web of Science, Google Scholar
14. D. W. Li , Unconditional convergence constants of $g$ -frame expansions, Int. J. Wavelets, Multiresolut. Inf. Process. 18(4) (2020), Article ID: 20550022. Link, Web of Science, Google Scholar
15. S. Mallat and Z. Zhang , Matching pursuit with time-frequency dictionaries, IEEE Trans. Signal Process. 41(12) (1993) 3397–3415. Crossref, Web of Science, Google Scholar
16. G. Petrova , Rescaled pure greedy algorithm for Hlibert and Banach spaces, Appl. Comput. Harmon. Anal. 41(3) (2016) 852–866. Crossref, Web of Science, Google Scholar
17. C. F. Shao and P. X. Ye , Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries, Int. J. Wavelets, Multiresolut. Inf. Process. 15(3) (2017), Article ID: 1750029. Google Scholar
18. V. N. Temlyakov , Greedy algorithms in Banach spaces, Adv. Comp. Math. 14 (2001) 277–292. Crossref, Web of Science, Google Scholar
19. V. N. Temlyakov , Weak greedy algorithms, Adv. Comput. Math. 12 (2000) 213–227. Crossref, Web of Science, Google Scholar
20. V. N. Temlyakov , Greedy Approximation, Cambridge Monographs on Applied and Computational Mathematics (Cambridge University Press, Cambridge, 2011). Crossref, Google Scholar
21. X. Xu, X. Q. Xu and L. Y. Zhu , The convergence properties of orthogonal rational functions on the extended real line and analytic on the upper half plane, Int. J. Wavelets, Multiresolut. Inf. Process. 18(5) (2020), Article ID: 20550032. Link, Web of Science, Google Scholar
22. B. Yang, C. Yang and G. Huang , Efficient image fusion with approximate sparse representation, Int. J. Wavelets, Multiresolut. Inf. Process. 14(4) (2016), Article ID: 1650024. Web of Science, Google Scholar