Greedy algorithms with regard to multivariate systems with special structure (Q1581104)

The problem of finding an optimal dictionary \(\mathcal D\) for non-linear \(m\)-term approximation \[ \sigma_m(f,{\mathcal D})_X:=\inf\{\|f-\sum^m_{i=1}c_ig_i\|_X : {g_i\in{\mathcal D},\;c_i,\;i=1,\dots,m}\} \] is considered. The author investigates this problem in the periodic multivariate case for classes of functions with bounded mixed derivative \(MW^r_q\) and classes with restriction of Lipschitz type on the mixed difference \(MH^r_q\). Let \(F\subset X\) be a functional class, \(\mathbf O\) be a collection of orthonormal dictionaries, then \(\sigma_m(F,{\mathbf O})_p:=\inf_{{\mathcal D}\in\mathbf O} \sup_{f\in F} \sigma_m(f,{\mathcal D})_p\). The author obtains lower estimates for \(\sigma_m(MH^r_q,\mathbf O)_{2}\) and \(\sigma_m(MW^r_q,\mathbf O)_{2}\) \((1\leqslant q<\infty)\), and proves that the orthogonal dictionary \(U^d\) (consisting of trigonometric polynomials which may be represented as a tensor product of shifts of one-dimensional Dirichlet kernels) provides an optimal estimate in the sense of order among all orthogonal dictionaries for \(m\)-term approximation of the classes \(MH^r_q\), \(MW^r_q\) in \(L^p\) \((1<q<\infty\), \(2\leqslant p<\infty\), \(r\) is big enough). It is also proved that for all \(1<q,p<\infty\) the order of best \(m\)-term approximation \(\sigma_m(MH^r_q,U^d)_{p}\) and \(\sigma_m(MW^r_q,U^d)_{p}\) can be achieved by a greedy-type algorithm. Another interesting result is that the dictionary \(Y:=(U^1\times L^p)\cup (L^p\times U^1)\) provides an optimal \(m\)-term bilinear approximation for \(1<q\leqslant p\leqslant 2\) and \(1<p \leqslant q<\infty\).