On the convergence of greedy algorithms for initial segments of the Haar basis
Preprint
Abstract
We consider the $X$-Greedy Algorithm and the Dual Greedy Algorithm in a finite-dimensional Banach space with a strictly monotone basis as the dictionary. We show that when the dictionary is an initial segment of the Haar basis in $L_p[0,1]$ ($1 < p < \infty$) then the algorithms terminate after finitely many iterations and that the number of iterations is bounded by a function of the length of the initial segment. We also prove a more general result for a class of strictly monotone bases.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Weak Convergence of Greedy Algorithms in Banach SpacesJournal of Fourier Analysis and Applications, 2008
- Relaxation in Greedy ApproximationConstructive Approximation, 2007
- Convergence of the weak dual greedy algorithm in L-spacesJournal of Approximation Theory, 2003
- Convergence of Greedy Algorithms in Banach SpacesMathematical Notes, 2003
- Convergence of Some Greedy Algorithms in Banach SpacesJournal of Fourier Analysis and Applications, 2002
- Greedy algorithms in Banach spacesAdvances in Computational Mathematics, 2001
- Weak greedy algorithms[*]This research was supported by National Science Foundation Grant DMS 9970326 and by ONR Grant N00014‐96‐1‐1003.Advances in Computational Mathematics, 2000
- On a Conjecture of Huber Concerning the Convergence of Projection Pursuit RegressionThe Annals of Statistics, 1987