2023/08/26 by Huichao Yan, Jia Chen, Yan, Huichao +1
Computer Science · Mathematics · #Advanced Computational Techniques in Science and Engineering #FOS: Computer and information sciences #Information Theory (cs.IT) #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.2308.13753
openalex publication_date 2023/08/26 · openalex created_date 2023/08/31 · openalex updated_date 2026/07/28
We study L2-approximation problems APPd in the worst case setting in the weighted Korobov spaces H_d,\a,\bm \ga with parameter sequences \bm \ga=\\gaj\ and \a=\\azj\ of positive real numbers 1≥ \ga1≥ \ga2≥ ⋯≥ 0 and \frac1 2<\az1≤ \az2≤ ⋯. We consider the minimal worst case error e(n,APPd) of algorithms that use n arbitrary continuous linear functionals with d variables. We study polynomial convergence of the minimal worst case error, which means that e(n,APPd) converges to zero polynomially fast with increasing n. We recall the notions of polynomial, strongly polynomial, weak and (t1,t2)-weak tractability. In particular, polynomial tractability means that we need a polynomial number of arbitrary continuous linear functionals in d and \va-1 with the accuracy \va of the approximation. We obtain that the matching necessary and sufficient condition on the sequences \bm \ga and \a for strongly polynomial tractability or polynomial tractability is \dz:=\liminfj→∞\fracln \gaj-1ln jgt;0, and the exponent of strongly polynomial tractability is pstr=2max\\frac 1 \dz, \frac 1 2\az1\.