Greedy algorithm for functions with low mixed smoothness (Q2581445): Difference between revisions

Let \(\{\phi_j\}_{j=1}^\infty\) be a basis of a Banach space \(X\) and for some \(f \in X\) and some real coefficients \(c_j\) let \(f=\sum_{j=1}^\infty c_j\phi_j\). The aim of the \(m\)-term approximation is to find a good approximation to \(f\) by a \(g\) of the form \(g=\sum_k a_k \phi_k\), with at most \(m\) non-zero coefficients. A possible approach is greedy approximation, in which one retains \(m\) terms with the largest values of \(\| c_j \phi_j\| \) in the initial expansion of \(f\) and drops the rest. In this paper, \(X\) is the space \(L_q=L_q(T^d)\) of 1-periodic functions of \(d\) variables on the torus. A special family of bases in \(L_q\), called wavelet-type bases and associated with the dyadic subdivision of the cube \([0,1]^d\), is introduced. If \(\Psi^d\) is such a basis, let \(G_m^q(f, \Psi^d)\) be the approximation to \(f\) obtained by applying the greedy algorithm to its exansion in \(\Psi^d\). It is assumed that \(f\) belongs to the Sobolev class \(MW_p^r\) of functions with a bounded mixed derivative of order \(r\). The focus is on the small values of \(r\) because the case of larger \(r\) has been studied earlier by other authors. Theorem 1. Let \(1 <p,q<\infty\). Then for \((1/p-1/q)_+ < r \leq 1/2-1/q\), \(p,q>2\), \[ \sup_{f \in MW_p^r} \| f-G_m^q(f, \Psi^d)\| _q \asymp m^{-r} (\log m)^\lambda, \quad \lambda={(d-1)r \over 2(r-1/q)}. \] For \((1/p-1/q)_+ < r \leq (\max(2/p, 2/q)-1)/q\), \(q<2\), \[ \sup_{f \in MW_p^r} \| f-G_m^q(f, \Psi^d)\| _q \asymp m^{-r} (\log m)^{(d-1)r}. \] Upper estimates for approximation by \(G_m^q(f, \Psi^d)\) are also found in the case of the Hölder-Nikolski classes \(MH_p^r\) with the small \(r\).