We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness
α≥2 defined over the
s-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the extrapolated polynomial lattice rule, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: (i) construction of classical polynomial lattice rules over
Fb with
α consecutive sizes of nodes,
bm−α+1,…,bm, and (ii) recursive application of Richardson extrapolation to a chain of
α approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order
(s+α)NlogN, which improves the currently known result for the interlaced polynomial lattice rule, which is of order
sαNlogN. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.
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 introduce a new method to approximate integrals ∫ R d f ( x ) d x \int _{\mathbb {R}^d} f(\boldsymbol {x}) \,\mathrm {d}\boldsymbol {x} which simply scales lattice rules from the unit cube [ 0 , 1 ] d [0,1]^d to properly sized boxes on R d \mathbb {R}^d , hereby achieving higher-order convergence that matches the smoothness of the integrand function f f in a certain Sobolev space of dominating mixed smoothness. Our method only assumes that we can evaluate the integrand function f f and does not assume a particular density nor the ability to sample from it. In particular, for the theoretical analysis we show a new result that the method of adding Bernoulli polynomials to a function to make it “periodic” on a box without changing its integral value over the box is equivalent to an orthogonal projection from a well chosen Sobolev space of dominating mixed smoothness to an associated periodic Sobolev space of the same dominating mixed smoothness, which we call a Korobov space. We note that the Bernoulli polynomial method is often not used because of its excessive computational complexity and also here we only make use of it in our theoretical analysis. We show that our new method of applying scaled lattice rules to increasing boxes can be interpreted as orthogonal projections with decreasing projection error. Such a method would not work on the unit cube since then the committed error caused by non-periodicity of the integrand would be constant, but for integration on the Euclidean space we can use the certain decay towards zero when the boxes grow. Hence we can bound the truncation error as well as the projection error and show higher-order convergence in applying scaled lattice rules for integration on Euclidean space. We illustrate our theoretical analysis by numerical experiments which confirm our findings.
Abstract Motivated by considerations of pure state entanglement in quantum information, we consider the problem of finding the best rank‐1 approximation to an arbitrary r ‐th order tensor. Reformulating the problem as an optimization problem on the Lie group SU (n1) ⊗ … ⊗ SU (nr) of so‐called local unitary transformations and exploiting its intrinsic geometry yields a new approach, which finally leads to Riemannian variant of the conjugate gradient algorithm. Numerical simulations support that our method offers an alternative to the higher‐order power method for computing the best rank‐1 approximation to a tensor. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)
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)∈O(q(logn)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
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,
01 independent of
s such that
e(n,s)≤Cq(logn)p holds for all
s and
n. We prove that AC-ST holds if the weights
u decay sufficiently fast. These results come from the convergence and tractability results for the Walsh space into which
Fs,u is embedded.