Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic Research Archive

Tractability of $ L_2 $-approximation and integration over weighted Korobov spaces of increasing smoothness in the worst case setting

Weiran Ding, Jiansong Li, Yumeng Jia, Wanru Yang

Published Jan 1, 2025• 0 citations
Publisher

Abstract

This paper is devoted to the study of tractability of the $ L_2 $-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class $ \Lambda^{\rm all} $, including all continuous linear functionals, and from the class $ \Lambda^{\rm std} $, including function evaluations. Necessary and sufficient conditions on the weights of the function space for strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability, weak tractability and $ (\sigma, \tau) $-weak tractability, are provided. Our results give a comprehensive picture of the weight conditions for all standard notions of algebraic tractability. It may be helpful to study the tractability of nonhomogeneous tensor product spaces.

DOI
10.3934/era.2025052

Related papers

Worst case tractability of $L_2$-approximation for weighted Korobov spaces

Huichao Yan, Jia Chen

We study $L_2$-approximation problems $\text{APP}_d$ in the worst case setting in the weighted Korobov spaces $H_{d,\a,{\bm \ga}}$ with parameter sequences ${\bm \ga}=\{\ga_j\}$ and $\a=\{\az_j\}$ of positive real numbers $1\ge \ga_1\ge \ga_2\ge \cdots\ge 0$ and $\frac1 2<\az_1\le \az_2\le \cdots$. We consider the minimal worst case error $e(n,\text{APP}_d)$ 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,\text{APP}_d)$ converges to zero polynomially fast with increasing $n$. We recall the notions of polynomial, strongly polynomial, weak and $(t_1,t_2)$-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:=\liminf_{j\to\infty}\frac{\ln \ga_j^{-1}}{\ln j}>0,$$ and the exponent of strongly polynomial tractability is $$p^{\text{str}}=2\max\big\{\frac 1 \dz, \frac 1 {2\az_1}\big\}.$$

arXiv:2308.13753•Aug 26, 2023•0 citations

Tractability of $\mathbb{L}_2$-approximation in hybrid function spaces

Peter Kritzer, Helene Laimer, Friedrich Pillichshammer

We consider multivariate $\mathbb{L}_2$-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error $e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)$ of all algorithms that use $N$ information evaluations from the class $Λ$ in the $d$-dimensional case. The two classes $Λ$ considered in this paper are the class $Λ^{\rm all}$ consisting of all linear functionals and the class $Λ^{\rm std}$ consisting only of function evaluations. The focus lies on the dependence of $e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)$ on the dimension $d$. The main results are conditions for weak, polynomial, and strong polynomial tractability.

arXiv:1701.02910•Jan 11, 2017•0 citations

Tractability of $\mathbb{L}_2$-approximation in hybrid function spaces

Peter Kritzer, Helene Laimer, Friedrich Pillichshammer

We consider multivariate $\mathbb{L}_2$-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error $e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)$ of all algorithms that use $N$ information evaluations from the class $\Lambda$ in the $d$-dimensional case. The two classes $\Lambda$ considered in this paper are the class $\Lambda^{{\rm all}}$ consisting of all linear functionals and the class $\Lambda^{{\rm std}}$ consisting only of function evaluations. The focus lies on the dependence of $e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)$ on the dimension $d$. The main results are conditions for weak, polynomial, and strong polynomial tractability.

Functiones et Approximatio Commentarii Mathematici•May 4, 2017•1 citation

A note about EC-$(s,t)$-weak tractability of multivariate approximation with analytic Korobov kernels

Heping Wang

This note is devoted to discussing multivariate approximation of continuous functions on $[0,1]^d$ with analytic Korobov kernels in the worst and average case settings. We only consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We study EC-$(s, t)$-weak tractability under the absolute or normalized error criterion, and obtain necessary and sufficient conditions for $0<\min(s,t)<1$ and $\max(s,t)\le 1$ in the worst case setting and for $s,t>0$ in the average case setting.

arXiv:1808.01470•Aug 4, 2018•0 citations

$\boldsymbol{L}_{\infty}$-approximation in Korobov spaces with Exponential Weights

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

We study multivariate $\boldsymbol{L}_{\infty}$-approximation for a weighted Korobov space of periodic functions for which the Fourier coefficients decay exponentially fast. The weights are defined, in particular, in terms of two sequences $\boldsymbol{a}=\{a_j\}$ and $\boldsymbol{b}=\{b_j\}$ of positive real numbers bounded away from zero. We study the minimal worst-case error $e^{\boldsymbol{L}_{\infty}\mathrm{-app},Λ}(n,s)$ of all algorithms that use $n$ information evaluations from a class $Λ$ in the $s$-variate case. We consider two classes $Λ$ in this paper: the class $Λ^{\rm all}$ of all linear functionals and the class $Λ^{\rm std}$ of only function evaluations. We study exponential convergence of the minimal worst-case error, which means that $e^{\boldsymbol{L}_{\infty}\mathrm{-app},Λ}(n,s)$ converges to zero exponentially fast with increasing $n$. Furthermore, we consider how the error depends on the dimension $s$. To this end, we define the notions of $κ$-EC-weak, EC-polynomial and EC-strong polynomial tractability, where EC stands for "exponential convergence". In particular, EC-polynomial tractability means that we need a polynomial number of information evaluations in $s$ and $1+\log\,\varepsilon^{-1}$ to compute an $\varepsilon$-approximation. We derive necessary and sufficient conditions on the sequences $\boldsymbol{a}$ and $\boldsymbol{b}$ for obtaining exponential error convergence, and also for obtaining the various notions of tractability. The results are the same for both classes $Λ$.

arXiv:1602.02572•Feb 8, 2016•0 citations

Exponential convergence and tractability of multivariate integration for Korobov spaces

Josef Dick, Gerhard Larcher, Friedrich Pillichshammer +1 more

In this paper we study multivariate integration for a weighted Korobov space for which the Fourier coefficients of the functions decay exponentially fast. This implies that the functions of this space are infinitely times differentiable. Weights of the Korobov space monitor the influence of each variable and each group of variables. We show that there are numerical integration rules which achieve an exponential convergence of the worst-case integration error. We also investigate the dependence of the worst-case error on the number of variables s s , and show various tractability results under certain conditions on weights of the Korobov space. Tractability means that the dependence on s s is never exponential, and sometimes the dependence on s s is polynomial or there is no dependence on s s at all.

Mathematics of Computation•Nov 2, 2010•55 citations
This paper is devoted to the study of tractability of the L2L_2L2​-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class Λall\Lambda^{\rm all}Λall, including all continuous linear functionals, and from the class Λstd\Lambda^{\rm std}Λstd, including function evaluations. Necessary and sufficient conditions on the weights of the function space for strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability, weak tractability and (σ,τ)(\sigma, \tau)(σ,τ)-weak tractability, are provided. Our results give a comprehensive picture of the weight conditions for all standard notions of algebraic tractability. It may be helpful to study the tractability of nonhomogeneous tensor product spaces.
Worst case tractability of L2L_2L2​-approximation for weighted Korobov spaces
We study L2L_2L2​-approximation problems APPd\text{APP}_dAPPd​ in the worst case setting in the weighted Korobov spaces $H_{d,\a,{\bm \ga}}$ with parameter sequences ${\bm \ga}=\{\ga_j\}$ and $\a=\{\az_j\}$ of positive real numbers $1\ge \ga_1\ge \ga_2\ge \cdots\ge 0$ and $\frac1 2<\az_1\le \az_2\le \cdots$. We consider the minimal worst case error e(n,APPd)e(n,\text{APP}_d)e(n,APPd​) of algorithms that use nnn arbitrary continuous linear functionals with ddd variables. We study polynomial convergence of the minimal worst case error, which means that e(n,APPd)e(n,\text{APP}_d)e(n,APPd​) converges to zero polynomially fast with increasing nnn. We recall the notions of polynomial, strongly polynomial, weak and (t1,t2)(t_1,t_2)(t1​,t2​)-weak tractability. In particular, polynomial tractability means that we need a polynomial number of arbitrary continuous linear functionals in ddd 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:=\liminf_{j\to\infty}\frac{\ln \ga_j^{-1}}{\ln j}>0,$$ and the exponent of strongly polynomial tractability is $$p^{\text{str}}=2\max\big\{\frac 1 \dz, \frac 1 {2\az_1}\big\}.$$
Tractability of L2\mathbb{L}_2L2​-approximation in hybrid function spaces
We consider multivariate L2\mathbb{L}_2L2​-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)eL2​−app,Λ(N,d) of all algorithms that use NNN information evaluations from the class ΛΛΛ in the ddd-dimensional case. The two classes ΛΛΛ considered in this paper are the class ΛallΛ^{\rm all}Λall consisting of all linear functionals and the class ΛstdΛ^{\rm std}Λstd consisting only of function evaluations. The focus lies on the dependence of eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)eL2​−app,Λ(N,d) on the dimension ddd. The main results are conditions for weak, polynomial, and strong polynomial tractability.
Tractability of L2\mathbb{L}_2L2​-approximation in hybrid function spaces
We consider multivariate L2\mathbb{L}_2L2​-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)eL2​−app,Λ(N,d) of all algorithms that use NNN information evaluations from the class Λ\LambdaΛ in the ddd-dimensional case. The two classes Λ\LambdaΛ considered in this paper are the class Λall\Lambda^{{\rm all}}Λall consisting of all linear functionals and the class Λstd\Lambda^{{\rm std}}Λstd consisting only of function evaluations. The focus lies on the dependence of eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)eL2​−app,Λ(N,d) on the dimension ddd. The main results are conditions for weak, polynomial, and strong polynomial tractability.
A note about EC-(s,t)(s,t)(s,t)-weak tractability of multivariate approximation with analytic Korobov kernels
This note is devoted to discussing multivariate approximation of continuous functions on [0,1]d[0,1]^d[0,1]d with analytic Korobov kernels in the worst and average case settings. We only consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We study EC-(s,t)(s, t)(s,t)-weak tractability under the absolute or normalized error criterion, and obtain necessary and sufficient conditions for 0<min⁡(s,t)<10<\min(s,t)<10<min(s,t)<1 and max⁡(s,t)≤1\max(s,t)\le 1max(s,t)≤1 in the worst case setting and for s,t>0s,t>0s,t>0 in the average case setting.
L∞\boldsymbol{L}_{\infty}L∞​-approximation in Korobov spaces with Exponential Weights
We study multivariate L∞\boldsymbol{L}_{\infty}L∞​-approximation for a weighted Korobov space of periodic functions for which the Fourier coefficients decay exponentially fast. The weights are defined, in particular, in terms of two sequences a={aj}\boldsymbol{a}=\{a_j\}a={aj​} and b={bj}\boldsymbol{b}=\{b_j\}b={bj​} of positive real numbers bounded away from zero. We study the minimal worst-case error eL∞−app,Λ(n,s)e^{\boldsymbol{L}_{\infty}\mathrm{-app},Λ}(n,s)eL∞​−app,Λ(n,s) of all algorithms that use nnn information evaluations from a class ΛΛΛ in the sss-variate case. We consider two classes ΛΛΛ in this paper: the class ΛallΛ^{\rm all}Λall of all linear functionals and the class ΛstdΛ^{\rm std}Λstd of only function evaluations. We study exponential convergence of the minimal worst-case error, which means that eL∞−app,Λ(n,s)e^{\boldsymbol{L}_{\infty}\mathrm{-app},Λ}(n,s)eL∞​−app,Λ(n,s) converges to zero exponentially fast with increasing nnn. Furthermore, we consider how the error depends on the dimension sss. To this end, we define the notions of κκκ-EC-weak, EC-polynomial and EC-strong polynomial tractability, where EC stands for "exponential convergence". In particular, EC-polynomial tractability means that we need a polynomial number of information evaluations in sss and 1+log⁡ ε−11+\log\,\varepsilon^{-1}1+logε−1 to compute an ε\varepsilonε-approximation. We derive necessary and sufficient conditions on the sequences a\boldsymbol{a}a and b\boldsymbol{b}b for obtaining exponential error convergence, and also for obtaining the various notions of tractability. The results are the same for both classes ΛΛΛ.
In this paper we study multivariate integration for a weighted Korobov space for which the Fourier coefficients of the functions decay exponentially fast. This implies that the functions of this space are infinitely times differentiable. Weights of the Korobov space monitor the influence of each variable and each group of variables. We show that there are numerical integration rules which achieve an exponential convergence of the worst-case integration error. We also investigate the dependence of the worst-case error on the number of variables s s , and show various tractability results under certain conditions on weights of the Korobov space. Tractability means that the dependence on s s is never exponential, and sometimes the dependence on s s is polynomial or there is no dependence on s s at all.