Greedy approximation and the multivariate Haar system
Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Multidimensional problems (41A63) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Summability and bases; functional analytic aspects of frames in Banach and Hilbert spaces (46B15)
Let \(X\) be an infinite-dimensional separable Banach space with norm \(\|\cdot\|\) and let \(\Psi= \{\psi_n\}^\infty_{n=1}\) be a normalized basis, that is \(\|\psi_n\|= 1\). For a given \(f\in X\), \[ \sigma_m(f,\Psi)= \underset{\#\Lambda= m}{}{\text{inf}}\;\underset{b_k,k\in\Lambda}{}{\text{inf}}\;\Biggl\| f-\sum_{k\in \Lambda} b_k\psi_k\Biggr\| \] measures best \(m\)-term approximation to \(f\) by \(\Psi\). The element \(f\) has an expansion \(f= \sum^\infty_{k=1} c_k\psi_k\). Consider a permutation \(\rho= \{\rho_j\}^\infty_{j=1}\) of \(\mathbb{N}\) such that \(\{|c_{\rho_j}|\}^\infty_{j=1}\) is decreasing. Then \(G_m(f,\Psi,\rho)= \sum^m_{j=1} c_{\rho_j}\psi_j\) is the \(m\)th greedy approximant to \(f\) corresponding to \(\rho\). The basis \(\Psi\) is said to be a greedy basis if there exists \(G> 0\) such that for all \(f\in X\), choice of \(\rho\) and \(m\in\mathbb{N}\), \[ \| f- G_m(f,\Psi, \rho)\|\leq G\sigma_m(f,\Psi). \] The paper considers, in place of this greedy algorithm, a weak greedy algorithm defined in the following way. A sequence \(\tau= \{t_k\}^\infty_{k=1}\), with each \(t_k\in [0,1]\), is referred to in this context as a weakness sequence. Given a weakness sequence one chooses inductively a sequence \(\{n_k\}^\infty_{k=1}\) such that \(|c_{n_1}|\geq t_1\max|c_n|\), \(|c_{n_k}|\geq t_k\max\{|c_n|: n\not\in\{n_1,\dots, n_{k-1}\}\}\) and \(n_k\not\in\{n_1,\dots, n_{k-1}\}\). Define \[ G^\tau_m(f,\Psi)= \sum^m_{k=1} c_{n_k}\psi_{n_k}, \] the dependence upon the choice of \(\{n_k\}^m_{k=1}\) being implicit. Theorem 1 contains the result that if the basis is unconditional then \(G^\tau_m(f,\Psi)\to f\) as \(m\to\infty\), always, if and only if the series \(\sum t_k \psi_k\) in \(X\) is divergent. In the case that is an unconditional basis Theorems 4 and 5 compare \(\| f- G^\tau_m(f,\Psi)\|\) and \(\sigma_m(f, \Psi)\): there exists \(C(\Psi)\) and \(\mu(\tau,m)\) such that \[ \| f- G^r_m(f, \Psi)\|\leq C(\Psi)\mu(\tau, m)\sigma_m(f,\Psi); \] and there exists \(C(\Psi)\) and a sequence \(\{\nu_m\}^\infty_{m=1}\) (which is identified) such that \[ \| f- G^\tau_{\nu_m}(f,\Psi)\|\leq C(\Psi)\sigma_m(f,\Psi). \] Let \({\mathcal H}= \{{\mathcal H}_k\}^\infty_{k=1}\) be the Haar basis on \([0, 1]\) and let \({\mathcal H}_p\) be \({\mathcal H}\) normalized in the \(L_p\) norm. Then \({\mathcal H}^d_p= {\mathcal H}_p\times\cdots\times{\mathcal H}_p\) is a multivariate Haar system on \([0,1]^d\), indexed by \(\mathbb{Z}^d\). Theorem 6 identifies, for \(1< p<\infty\), subsequences \({\mathcal M}\) of \({\mathcal H}^d_p\) such that \({\mathcal M}\) is a greedy basis for its closed linear span in \(L_p([0, 1]^d)\). There are some further related results but Section 5, concerned with rather different questions, is entitled `Some direct and inverse theorems in \(m\)-term approximation with regard to \({\mathcal H}^d_p\).
- Greedy approximation in certain subsystems of the Schauder system
- Quasi-greedy bases for sequences with gaps
- Greedy approximation with regard to non-greedy bases
- Wavelets, Orlicz spaces, and greedy bases
- Greedy bases in variable Lebesgue spaces
- General Haar systems and greedy approximation
- Results on non-linear approximation for wavelet bases in weighted function spaces
- Quasi-greedy property of subsystems of the multivariate Haar system
- Greedy algorithm with regard to Haar subsystems
- The convergence of the greedy algorithm with respect to the Haar system in the space \(L_{p}\)(0,1)
- Lebesgue-type inequalities for quasi-greedy bases
- scientific article; zbMATH DE number 1264507 (Why is no real title available?)
- On the convergence of a weak greedy algorithm for the multivariate Haar basis
- Efficiency of the weak Rescaled Pure Greedy Algorithm
- Approximation with greedy basis on the example of Haar system in Lorentz spaces
- Greedy algorithms for optimizing multivariate Horner schemes
- Greedy algorithms and best \(m\)-term approximation with respect to biorthogonal systems
- Quantifying democracy of wavelet bases in Lorentz spaces
- Best approximation with wavelets in weighted Orlicz spaces
- The best m-term approximation with respect to polynomials with constant coefficients
- Democracy functions and optimal embeddings for approximation spaces
- On left democracy function
- On the m-term approximation in L^1(0, 1) in the Haar system
This page was built for publication: Greedy approximation and the multivariate Haar system
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4811183)
