A unified way of analyzing some greedy algorithms
From MaRDI portal
Publication:2329295
Abstract: 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.
Recommendations
Cites work
- Approximate weak greedy algorithms
- Approximation and learning by greedy algorithms
- Convergence of some greedy algorithms in Banach spaces
- Convergence of the weak dual greedy algorithm in \(L_{p}\)-spaces.
- Generalized approximate weak greedy algorithms
- Greedy algorithms in Banach spaces
- Greedy approximation with regard to non-greedy bases
- Greedy-type approximation in Banach spaces and applications
- scientific article; zbMATH DE number 3772323 (Why is no real title available?)
- Matching pursuits with time-frequency dictionaries
- Nonlinear methods of approximation
- On the approximate weak Chebyshev greedy algorithm in uniformly smooth Banach spaces
- On the convergence of approximate weak gready algorithms
- On the generalized approximate weak Chebyshev greedy algorithm
- Orthogonality in linear metric spaces
- Rates of convex approximation in non-Hilbert spaces
- Relaxation in greedy approximation
- Rescaled pure greedy algorithm for Hilbert and Banach spaces
- Some remarks on greedy algorithms
- Weak greedy algorithms
Cited in
(15)- Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem
- Duality gap estimates for a class of greedy optimization algorithms in Banach spaces
- Biorthogonal greedy algorithms in convex optimization
- Sparse approximation of individual functions
- Rescaled pure greedy algorithm for convex optimization
- Efficiency of the weak Rescaled Pure Greedy Algorithm
- Unified error estimate for weak biorthogonal greedy algorithms
- Entropy-based convergence rates of greedy algorithms
- Brief introduction in greedy approximation
- Randomized greedy algorithms for neural network optimization in solving partial differential equations
- -Rescaled Pure Super Greedy Algorithm with respect to Riesz dictionary
- On greedy approximation in complex Banach spaces
- A new analysis of empirical interpolation methods and Chebyshev greedy algorithms
- Approximation properties of some vector weak biorthogonal greedy algorithms
- Some theoretical and practical results on noisy signals recovery
This page was built for publication: A unified way of analyzing some greedy algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2329295)
