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

arXiv:1808.01470

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

Heping Wang

Published Aug 4, 2018• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1808.01470

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

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

Heping Wang

Journal of Complexity•Jul 2, 2019•14 citations

Average Case (s, t)-Weak Tractability of L2-Approximation with Weighted Covariance Kernels

Jia Chen, Huichao Yan

We study the multivariate L2-approximation problem APPd defined over a Banach space in the average case setting. The space is equipped with a zero-mean Gaussian measure with a weighted covariance kernel, which depends on parameter sequences α={αj}j∈N and β={βj}j∈N with 1<α1≤α2≤⋯ and 1≥β1≥β2≥⋯>0. In this paper, two interesting weighted covariance kernels are considered, which model the importance of the covariance kernels. Under the absolute error criterion or the normalized error criterion, we discuss (s,t)-weak tractability of the L2-approximation problem APP={APPd}d∈N from a Banach space whose zero-mean Gaussian measure has the above two weighted covariance kernels for some positive numbers s and t in the average case setting. Here, (s,t)-weak tractability means how the information complexity behaves as a function of dt and ε−s for large dimension d and small threshold ε. In particular, for all s>0 and t∈(0,1), we find the matching sufficient and necessary condition on the parameter sequences α={αj}j∈N and β={βj}j∈N to obtain (s,t)-weak tractability under the absolute error criterion or the normalized error criterion in the average case setting. We describe (s,t)-weak tractability by the matching sufficient and necessary condition, which reflects symmetry.

Symmetry•Nov 14, 2024•0 citations

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 +1 more

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.

Electronic Research Archive•Jan 1, 2025•0 citations

A note on approximation in weighted Korobov spaces via multiple rank-1 lattices

Mou Cai, Takashi Goda

This paper studies the multivariate approximation of functions in weighted Korobov spaces using multiple rank-1 lattice rules. It has been shown by Kämmerer and Volkmer (2019) that algorithms based on multiple rank-1 lattices achieve the optimal convergence rate for the $L_{\infty}$ error in Wiener-type spaces, up to logarithmic factors. While this result was translated to weighted Korobov spaces in the recent monograph by Dick, Kritzer, and Pillichshammer (2022), the analysis requires the smoothness parameter $α$ to be greater than $1$ and is restricted to product weights. In this paper, we extend this result for multiple rank-1 lattice-based algorithms to the case where $1/2<α\le 1$ and for general weights, covering a broader range of periodic functions with low smoothness and general relative importance of variables. We also provide a summability condition on the weights to ensure strong polynomial tractability for any $α>1/2$. Furthermore, by incorporating random shifts into multiple rank-1 lattice-based algorithms, we prove that the resulting randomized algorithm achieves a nearly optimal convergence rate in terms of the worst-case root mean squared $L_2$ error, while retaining the same tractability property.

arXiv:2601.20290•Jan 28, 2026•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
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.
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\}.$$
We study the multivariate L2-approximation problem APPd defined over a Banach space in the average case setting. The space is equipped with a zero-mean Gaussian measure with a weighted covariance kernel, which depends on parameter sequences α={αj}j∈N and β={βj}j∈N with 1<α1≤α2≤⋯ and 1≥β1≥β2≥⋯>0. In this paper, two interesting weighted covariance kernels are considered, which model the importance of the covariance kernels. Under the absolute error criterion or the normalized error criterion, we discuss (s,t)-weak tractability of the L2-approximation problem APP={APPd}d∈N from a Banach space whose zero-mean Gaussian measure has the above two weighted covariance kernels for some positive numbers s and t in the average case setting. Here, (s,t)-weak tractability means how the information complexity behaves as a function of dt and ε−s for large dimension d and small threshold ε. In particular, for all s>0 and t∈(0,1), we find the matching sufficient and necessary condition on the parameter sequences α={αj}j∈N and β={βj}j∈N to obtain (s,t)-weak tractability under the absolute error criterion or the normalized error criterion in the average case setting. We describe (s,t)-weak tractability by the matching sufficient and necessary condition, which reflects symmetry.
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.
This paper studies the multivariate approximation of functions in weighted Korobov spaces using multiple rank-1 lattice rules. It has been shown by Kämmerer and Volkmer (2019) that algorithms based on multiple rank-1 lattices achieve the optimal convergence rate for the L∞L_{\infty}L∞​ error in Wiener-type spaces, up to logarithmic factors. While this result was translated to weighted Korobov spaces in the recent monograph by Dick, Kritzer, and Pillichshammer (2022), the analysis requires the smoothness parameter ααα to be greater than 111 and is restricted to product weights. In this paper, we extend this result for multiple rank-1 lattice-based algorithms to the case where 1/2<α≤11/2<α\le 11/2<α≤1 and for general weights, covering a broader range of periodic functions with low smoothness and general relative importance of variables. We also provide a summability condition on the weights to ensure strong polynomial tractability for any α>1/2α>1/2α>1/2. Furthermore, by incorporating random shifts into multiple rank-1 lattice-based algorithms, we prove that the resulting randomized algorithm achieves a nearly optimal convergence rate in terms of the worst-case root mean squared L2L_2L2​ error, while retaining the same tractability property.
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.