Accelerating convergence and tractability of multivariate integration for infinitely differentiable functions

Kosuke Suzuki

Published May 8, 2015• 2 citations

Abstract

We investigate multivariate integration for a space of infinitely differentiable functions $ \mathcal{F}_{s, \boldsymbol{u}} := \{f \in C^\infty [0,1]^s \mid \| f \|_{\mathcal{F}_{s, \boldsymbol{u}} } := \sup_{(\alpha_1, \dots, \alpha_s) \in \mathbb{N}_0^s} \|f^{(\alpha_1, \dots, \alpha_s)}\|_{L^1}/\prod_{j=1}^s u_j^{\alpha_j} 1$ such that $e(n,s) \in O(q^{(\log{n})^{p}})$ holds as $n$ goes to infinity, where $e(n,s)$ may depend on $s$ in an arbitrary way. We prove that accelerating convergence holds for $p=2$ for any $\boldsymbol{u}$ and $s$ considered. We also study a sufficient condition for accelerating convergence with strong tractability (AC-ST), which means that there exist constants $C>0$, $0 1$ independent of $s$ such that $e(n,s) \leq C q^{(\log{n})^{p}}$ holds for all $s$ and $n$. We prove that AC-ST holds if the weights $\boldsymbol{u}$ decay sufficiently fast. These results come from the convergence and tractability results for the Walsh space into which $\mathcal{F}_{s, \boldsymbol{u}}$ is embedded.

Related papers

Exponential convergence and tractability of multivariate integration for Korobov spaces

Josef Dick, Gerhard Larcher, Friedrich Pillichshammer +1 more

Mathematics of ComputationNov 2, 201055 citations

Exponential convergence for integration over R^s

Dong Nguyen, Dirk Nuyens

Jul 1, 20150 citations

Multivariate integration in C^\infty([0,1]^d) is not strongly tractable

Jakub Onufry Wojtaszczyk

arXiv:0803.0441Mar 4, 20080 citations

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

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

Mathematics of ComputationNov 20, 201344 citations

Strong tractability of multivariate integration using quasi–Monte Carlo algorithms

Xiaoqun Wang

Mathematics of ComputationJun 25, 200256 citations

Tractability of multivariate analytic problems

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

arXiv:1407.1615De Gruyter eBooksJul 25, 201425 citations

Accelerating convergence and tractability of multivariate integration for infinitely differentiable functions

Kosuke Suzuki

Published May 8, 2015• 2 citations

OpenAlex

Abstract

We investigate multivariate integration for a space of infinitely differentiable functions

\mathcal{F}_{s, \boldsymbol{u}} := \{f \in C^\infty [0,1]^s \mid \| f \|_{\mathcal{F}_{s, \boldsymbol{u}} } := \sup_{(\alpha_1, \dots, \alpha_s) \in \mathbb{N}_0^s} \|f^{(\alpha_1, \dots, \alpha_s)}\|_{L^1}/\prod_{j=1}^s u_j^{\alpha_j} 1

such that

e(n,s) \in O(q^{(\log{n})^{p}})

holds as

n

goes to infinity, where

e(n,s)

may depend on

s

in an arbitrary way. We prove that accelerating convergence holds for

p=2

for any

\boldsymbol{u}

and

s

considered. We also study a sufficient condition for accelerating convergence with strong tractability (AC-ST), which means that there exist constants

C>0

0 1

independent of

s

such that

e(n,s) \leq C q^{(\log{n})^{p}}

holds for all

s

and

n

. We prove that AC-ST holds if the weights

\boldsymbol{u}

decay sufficiently fast. These results come from the convergence and tractability results for the Walsh space into which

\mathcal{F}_{s, \boldsymbol{u}}

is embedded.

Related papers

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.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 ComputationNov 2, 201055 citations

Exponential convergence for integration over R^s

Dong Nguyen, Dirk Nuyens

In this talk we study multivariate integration over R^s for weighted function space of infinitely many times differentiable functions for which the Fourier transform decays exponentially fast. The weights allows us to define the different influence of each variables. We prove that we can achieve the exponential convergence rate using a classical quasi-Monte Carlo method. More specific, we prove two convergence rates of $\mathcal{O}(e^{-N^{\frac{1}{D+B}}})$ and $\mathcal{O} (e^{-\frac{N^{\frac{1}{B}}}{\ln^{\frac{1}{D}} N}})$ , where D and B are respectively defined by the exponential decay of the Fourier coefficients and of the integrand, for two different function spaces. We also show some numerical results that prove our theorems.In this talk we study multivariate integration over R^s for weighted function space of infinitely many times differentiable functions for which the Fourier transform decays exponentially fast. The weights allows us to define the different influence of each variables. We prove that we can achieve the exponential convergence rate using a classical quasi-Monte Carlo method. More specific, we prove two convergence rates of $\mathcal{O}(e^{-N^{\frac{1}{D+B}}})$ and $\mathcal{O} (e^{-\frac{N^{\frac{1}{B}}}{\ln^{\frac{1}{D}} N}})$, where D and B are respectively defined by the exponential decay of the Fourier coefficients and of the integrand, for two different function spaces. We also show some numerical results that prove our theorems.

Jul 1, 20150 citations

Multivariate integration in C^\infty([0,1]^d) is not strongly tractable

Jakub Onufry Wojtaszczyk

It has long been known that the multivariate integration problem for the unit ball in $C^r([0,1]^d)$ is intractable for fixed finite $r$ . H. Woźniakowski has recently conjectured that this is true even if $r=\infty$ . This paper establishes a partial result in this direction. We prove that the multivariate integration problem, for infinitely differential functions all of whose variables are bounded by one, is not strongly tractable.It has long been known that the multivariate integration problem for the unit ball in $C^r([0,1]^d)$ is intractable for fixed finite $r$. H. Woźniakowski has recently conjectured that this is true even if $r=\infty$. This paper establishes a partial result in this direction. We prove that the multivariate integration problem, for infinitely differential functions all of whose variables are bounded by one, is not strongly tractable.

arXiv:0803.0441Mar 4, 20080 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 haveWe 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 ComputationNov 20, 201344 citations

Strong tractability of multivariate integration using quasi–Monte Carlo algorithms

Xiaoqun Wang

We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })

Mathematics of ComputationJun 25, 200256 citations

Tractability of multivariate analytic problems

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which $s$ -variate problems can be approximated to within $\varepsilon$ by using, say, polynomially many in $s$ and $\varepsilon^{-1}$ function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with $\varepsilon^{-1}$ replaced by $1+\log \varepsilon^{-1}$ . In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of $s$ and $1+\log \varepsilon^{-1}$ . The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which $s$-variate problems can be approximated to within $\varepsilon$ by using, say, polynomially many in $s$ and $\varepsilon^{-1}$ function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with $\varepsilon^{-1}$ replaced by $1+\log \varepsilon^{-1}$. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of $s$ and $1+\log \varepsilon^{-1}$. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.

arXiv:1407.1615De Gruyter eBooksJul 25, 201425 citations

We investigate multivariate integration for a space of infinitely differentiable functions

\mathcal{F}_{s, \boldsymbol{u}} := \{f \in C^\infty [0,1]^s \mid \| f \|_{\mathcal{F}_{s, \boldsymbol{u}} } := \sup_{(\alpha_1, \dots, \alpha_s) \in \mathbb{N}_0^s} \|f^{(\alpha_1, \dots, \alpha_s)}\|_{L^1}/\prod_{j=1}^s u_j^{\alpha_j} 1

such that

e(n,s) \in O(q^{(\log{n})^{p}})

holds as

n

goes to infinity, where

e(n,s)

may depend on

s

in an arbitrary way. We prove that accelerating convergence holds for

p=2

for any

\boldsymbol{u}

and

s

considered. We also study a sufficient condition for accelerating convergence with strong tractability (AC-ST), which means that there exist constants

C>0

0 1

independent of

s

such that

e(n,s) \leq C q^{(\log{n})^{p}}

holds for all

s

and

n

. We prove that AC-ST holds if the weights

\boldsymbol{u}

decay sufficiently fast. These results come from the convergence and tractability results for the Walsh space into which

\mathcal{F}_{s, \boldsymbol{u}}

is embedded.

\mathcal{O}(e^{-N^{\frac{1}{D+B}}})

and

\mathcal{O} (e^{-\frac{N^{\frac{1}{B}}}{\ln^{\frac{1}{D}} N}})

, where D and B are respectively defined by the exponential decay of the Fourier coefficients and of the integrand, for two different function spaces. We also show some numerical results that prove our theorems.

It has long been known that the multivariate integration problem for the unit ball in

C^r([0,1]^d)

is intractable for fixed finite

r

. H. Woźniakowski has recently conjectured that this is true even if

r=\infty

. This paper establishes a partial result in this direction. We prove that the multivariate integration problem, for infinitely differential functions all of whose variables are bounded by one, is not strongly tractable.

In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which

s

-variate problems can be approximated to within

\varepsilon

by using, say, polynomially many in

s

and

\varepsilon^{-1}

function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with

\varepsilon^{-1}

replaced by

1+\log \varepsilon^{-1}

. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of

s

and

1+\log \varepsilon^{-1}

. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.