×

Lower bounds for multivariate approximation by affine-invariant dictionaries. (English) Zbl 1029.41017

Let \(I^d\) be the \(d\)-dimensional cube \([0,1]^d\). If \(F\) and \(H\) are nonempty subsets of \(L_q(I^d)\), then \[ \text{dist} (F,H,L_q)=\sup_{f\in F} \inf_{h\in H}\|f-h|_{L_q} \] is said to be the approximation error in approximating \(F\) by \(H\). The aim of the present paper is to find a lower bound for \(\text{dist} (F,H,L_q)\) when \(F\) is the classic Sobolev space \(W_p^{r,d}\) and \(H\) is the set \(H_n^\ell (\varphi)\) of all functions of the form \(c_1\varphi (A_1x+b_1)+ \cdots+c_n \varphi(A_nx+ b_n)\). Here \(A_1,\dots,A_n\) are real-valued \(\ell\times d\) matrices, \(c_1,\dots, c_n\in\mathbb{R}\) and \(b_1,\dots,b_n \in \mathbb{R}^\ell\). Under appropriate conditions on the real-valued function \(\varphi\) it is shown that \[ \text{dist}\bigl(W_p^{r,d},H_n^\ell (\varphi),L_q\bigr)\geq c(n \log n)^{-r/d}, \] where the constant \(c\) does not depend on \(n\). The result is established by using an upper bound for the pseudodimension of \(H_n^\ell (\varphi)\) with respect to a finite subset of \(I^d\).

MSC:

41A50 Best approximation, Chebyshev systems
41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
PDFBibTeX XMLCite
Full Text: DOI Link