A unified way of analyzing some greedy algorithms
This work provides a theoretical unification for analyzing greedy algorithms, which is valuable for researchers in approximation theory and signal processing, but the results are theoretical and no concrete numerical improvements are demonstrated.
The paper proposes a unified framework for analyzing a class of greedy algorithms in Banach spaces, showing that several known algorithms belong to this class and deriving convergence, rate of convergence, and numerical stability properties. It also introduces a new algorithm, the Rescaled Weak Relaxed Greedy Algorithm, and obtains convergence results without explicit analysis.
In this paper we propose a unified way of analyzing a certain kind of greedy-type algorithms in Banach spaces. We define a class of the Weak Biorthogonal Greedy Algorithms that contains a wide range of greedy algorithms. In particular, we show that the following well-known algorithms --- the Weak Chebyshev Greedy Algorithm and the Weak Greedy Algorithm with Free Relaxation --- belong to this class. We investigate the properties of convergence, rate of convergence, and numerical stability of the Weak Biorthogonal Greedy Algorithms. Numerical stability is understood in the sense that the steps of the algorithm are allowed to be performed with controlled computational inaccuracies. We carry out a thorough analysis of the connection between the magnitude of those inaccuracies and the convergence properties of the algorithm. To emphasize the advantage of the proposed approach, we introduce here a new greedy algorithm --- the Rescaled Weak Relaxed Greedy Algorithm --- from the above class, and derive the convergence results without analyzing the algorithm explicitly. Additionally, we explain how the proposed approach can be extended to some other types of greedy algorithms.