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:1602.02572

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

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

Published Feb 8, 2016• 0 citations
arXivHTMLPDF

Abstract

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 $Λ$.

DOI
10.48550/arxiv.1602.02572

Related papers

Approximation of analytic functions in Korobov spaces

Josef Dick, Peter Kritzer, Friedrich Pillichshammer +1 more

We study multivariate $L_2$-approximation for a weighted Korobov space of analytic 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 numbers no less than one. Let $e^{L_2-\mathrm{app},Λ}(n,s)$ be the minimal worst-case error of all algorithms that use $n$ information functionals from the class $Λ$ in the $s$-variate case. We consider two classes $Λ$: the class $Λ^{\rm all}$ consists of all linear functionals and the class $Λ^{\rm std}$ consists of only function valuations. We study (EXP) exponential convergence. This means that $$ e^{L_2-\mathrm{app},Λ}(n,s) \le C(s)\,q^{\,(n/C_1(s))^{p(s)}}\quad{for all}\quad n, s \in \mathbb{N} $$ where $q\in(0,1)$, and $C,C_1,p:\mathbb{N} \rightarrow (0,\infty)$. If we can take $p(s)=p>0$ for all $s$ then we speak of (UEXP) uniform exponential convergence. We also study EXP and UEXP with (WT) weak, (PT) polynomial and (SPT) strong polynomial tractability. These concepts are defined as follows. Let $n(\e,s)$ be the minimal $n$ for which $e^{L_2-\mathrm{app},Λ}(n,s)\le \e$. Then WT holds iff $\lim_{s+\log\,\e^{-1}\to\infty}(\log n(\e,s))/(s+\log\,\e^{-1})=0$, PT holds iff there are $c,τ_1,τ_2$ such that $n(\e,s)\le cs^{τ_1}(1+\log\,\e^{-1})^{τ_2}$ for all $s$ and $\e\in(0,1)$, and finally SPT holds iff the last estimate holds for $τ_1=0$. The infimum of $τ_2$ for which SPT holds is called the exponent $τ^*$ of SPT. We prove that the results are the same for both classes $Λ$, and obtain conditions for WT, PT, SPT with and without EXP and UEXP.

arXiv:1211.5822•Nov 25, 2012•0 citations

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

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

Multivariate integration of infinitely many times differentiable functions in weighted Korobov spaces

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

We study multivariate integration for a weighted Korobov space of periodic infinitely many times differentiable functions for which the Fourier coefficients decay exponentially fast. The weights are defined in terms of two non-decreasing sequences a = { a i } \mathbf {a}=\{a_i\} and b = { b i } \mathbf {b}=\{b_i\} of numbers no less than one and a parameter ω ∈ ( 0 , 1 ) \omega \in (0,1) . Let e ( n , s ) e(n,s) be the minimal worst-case error of all algorithms that use n n function values in the s s -variate case. We would like to check conditions on a \mathbf {a} , b \mathbf {b} and ω \omega such that e ( n , s ) e(n,s) decays exponentially fast, i.e., for some q ∈ ( 0 , 1 ) q\in (0,1) and p > 0 p>0 we have

Mathematics of Computation•Nov 20, 2013•44 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

On the power of standard information for tractability for $L_\infty$ approximation of periodic functions in the worst case setting

Jiaxin Geng, Heping Wang

We study multivariate approximation of periodic function in the worst case setting with the error measured in the $L_\infty$ norm. We consider algorithms that use standard information $Λ^{\rm std}$ consisting of function values or general linear information $Λ^{\rm all}$ consisting of arbitrary continuous linear functionals. We investigate the equivalences of various notions of algebraic and exponential tractability for $Λ^{\rm std}$ and $Λ^{\rm all}$ under the absolute or normalized error criterion, and show that the power of $Λ^{\rm std}$ is the same as the one of $Λ^{\rm all}$ for some notions of algebraic and exponential tractability. Our result can be applied to weighted Korobov spaces and Korobov spaces with exponential weight. This gives a special solution to Open problem 145 as posed by Novak and Woźniakowski (2012).

arXiv:2304.14748•Apr 28, 2023•0 citations
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 ΛΛΛ.
We study multivariate L2L_2L2​-approximation for a weighted Korobov space of analytic 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 numbers no less than one. Let eL2−app,Λ(n,s)e^{L_2-\mathrm{app},Λ}(n,s)eL2​−app,Λ(n,s) be the minimal worst-case error of all algorithms that use nnn information functionals from the class ΛΛΛ in the sss-variate case. We consider two classes ΛΛΛ: the class ΛallΛ^{\rm all}Λall consists of all linear functionals and the class ΛstdΛ^{\rm std}Λstd consists of only function valuations. We study (EXP) exponential convergence. This means that eL2−app,Λ(n,s)≤C(s) q (n/C1(s))p(s)foralln,s∈N e^{L_2-\mathrm{app},Λ}(n,s) \le C(s)\,q^{\,(n/C_1(s))^{p(s)}}\quad{for all}\quad n, s \in \mathbb{N} eL2​−app,Λ(n,s)≤C(s)q(n/C1​(s))p(s)foralln,s∈N where q∈(0,1)q\in(0,1)q∈(0,1), and C,C1,p:N→(0,∞)C,C_1,p:\mathbb{N} \rightarrow (0,\infty)C,C1​,p:N→(0,∞). If we can take p(s)=p>0p(s)=p>0p(s)=p>0 for all sss then we speak of (UEXP) uniform exponential convergence. We also study EXP and UEXP with (WT) weak, (PT) polynomial and (SPT) strong polynomial tractability. These concepts are defined as follows. Let $n(\e,s)$ be the minimal nnn for which $e^{L_2-\mathrm{app},Λ}(n,s)\le \e$. Then WT holds iff $\lim_{s+\log\,\e^{-1}\to\infty}(\log n(\e,s))/(s+\log\,\e^{-1})=0$, PT holds iff there are c,τ1,τ2c,τ_1,τ_2c,τ1​,τ2​ such that $n(\e,s)\le cs^{τ_1}(1+\log\,\e^{-1})^{τ_2}$ for all sss and $\e\in(0,1)$, and finally SPT holds iff the last estimate holds for τ1=0τ_1=0τ1​=0. The infimum of τ2τ_2τ2​ for which SPT holds is called the exponent τ∗τ^*τ∗ of SPT. We prove that the results are the same for both classes ΛΛΛ, and obtain conditions for WT, PT, SPT with and without EXP and UEXP.
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\}.$$
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.
We study multivariate integration for a weighted Korobov space of periodic infinitely many times differentiable functions for which the Fourier coefficients decay exponentially fast. The weights are defined in terms of two non-decreasing sequences a = { a i } \mathbf {a}=\{a_i\} and b = { b i } \mathbf {b}=\{b_i\} of numbers no less than one and a parameter ω ∈ ( 0 , 1 ) \omega \in (0,1) . Let e ( n , s ) e(n,s) be the minimal worst-case error of all algorithms that use n n function values in the s s -variate case. We would like to check conditions on a \mathbf {a} , b \mathbf {b} and ω \omega such that e ( n , s ) e(n,s) decays exponentially fast, i.e., for some q ∈ ( 0 , 1 ) q\in (0,1) and p > 0 p>0 we have
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.
On the power of standard information for tractability for L∞L_\inftyL∞​ approximation of periodic functions in the worst case setting
We study multivariate approximation of periodic function in the worst case setting with the error measured in the L∞L_\inftyL∞​ norm. We consider algorithms that use standard information ΛstdΛ^{\rm std}Λstd consisting of function values or general linear information ΛallΛ^{\rm all}Λall consisting of arbitrary continuous linear functionals. We investigate the equivalences of various notions of algebraic and exponential tractability for ΛstdΛ^{\rm std}Λstd and ΛallΛ^{\rm all}Λall under the absolute or normalized error criterion, and show that the power of ΛstdΛ^{\rm std}Λstd is the same as the one of ΛallΛ^{\rm all}Λall for some notions of algebraic and exponential tractability. Our result can be applied to weighted Korobov spaces and Korobov spaces with exponential weight. This gives a special solution to Open problem 145 as posed by Novak and Woźniakowski (2012).