Approximate weak greedy algorithms
Let \(H\) be a real Hilbert space with inner product \(\langle \cdot, \cdot\rangle\). A subset \({\mathcal D}\) in \(H\) is called the dictionary if each \(g\in{\mathcal D}\) has norm one and \(Spann \{g: g\in {\mathcal D}\}\) is a dense subset of \(H\). Given \(\{t_m\}_{m=1}^{\infty}\subset [0, 1]\) and \(\{\epsilon_m\}_{m=1}^{\infty}\subset[-1, 1]\) the Approximate Weak Greedy Algorithm (AWGA) provides an \(m\)-term approximation of \(f_0\in H\) by constructing a sequence \(f_m\in H\), \(m\geq 1\), such that at each step \(f_m=f_{m-1}-(1+\epsilon_m)\langle f_{m-1}, g_m\rangle g_m\), \(g_m\in {\mathcal D}\), with \(|\langle f_{m-1}, g_m\rangle|\geq t_m\sup_{g\in{\mathcal D}}|\langle f_{m-1}, g\rangle|\). The \(m\)-term approximant of \(f_0\) is then defined as \(G_m=f_0-f_m=\sum_{j=1}^m (1+\epsilon_j)\langle f_{j-1}, g_j\rangle g_j\). The authors give sufficient conditions on \(\{\epsilon_m\}\) and \(\{t_m\}\) for AWGA to converge with any dictionary \({\mathcal D}\), i.e. whether \(G_m\to f_0\) for every \(f_0\in H\) (or equivalently, \(f_m\to 0\)). They provide two counter-examples to show that the condition cannot be relaxed in general. For a class of dictionaries with more structure a more relaxed necessary and sufficient condition for convergence of the algorithm are also given.
- Generalized approximate weak greedy algorithms
- Weak greedy algorithms
- On convergence of weak greedy algorithms
- Efficiency of weak greedy algorithms for m-term approximations
- On the generalized approximate weak Chebyshev greedy algorithm
- A criterion for convergence of weak greedy algorithms
- Greedy approximations
- Greedy in Approximation Algorithms
- On the convergence of approximate weak gready algorithms
- Efficiency of the weak Rescaled Pure Greedy Algorithm
- Weakly adaptive comparison searching
- A criterion for convergence of weak greedy algorithms
- Weak greedy algorithms
- Biorthogonal greedy algorithms in convex optimization
- Sharp sufficient condition for the convergence of greedy expansions with errors in coefficient computation
- Conical greedy algorithm
- A unified way of analyzing some greedy algorithms
- Generalized approximate weak greedy algorithms
- On convergence of weak greedy algorithms
- The absolute stability of orthorecursive expansions in redundant systems of subspaces
- On the generalized approximate weak Chebyshev greedy algorithm
- Rescaled pure greedy algorithm for Hilbert and Banach spaces
- On the convergence of approximate weak gready algorithms
- Convergence of orthogonal greedy algorithm with errors in projectors
- On greedy algorithms for dictionaries with bounded cumulative coherence
- scientific article; zbMATH DE number 2111760 (Why is no real title available?)
- Efficiency of the weak Rescaled Pure Greedy Algorithm
- Simultaneous greedy approximation in Banach spaces
- A counter-example to the general convergence of partially greedy algorithms
- Adaptive greedy approximations
- Vector greedy algorithms
- Error bounds of approximate weak rescaled pure greedy algorithms
- \(L^p\)-convergence of greedy algorithm by generalized Walsh system
- Greedy expansions in Banach spaces
- On the approximate weak Chebyshev greedy algorithm in uniformly smooth Banach spaces
- On \(n\)-term approximation with positive coefficients
This page was built for publication: Approximate weak greedy algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5950886)
