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

Integration and approximation in cosine space

Ronald F. A. Cools, Frances Y. Kuo, Dirk Nuyens, Gowri Suryanarayana

Published Jul 7, 2015• 0 citations
OpenAlex

Abstract

We analyse the worst case error (w.c.e) for approximation of d-variate non-periodic functions belonging to the weighted half-period cosine space. We use the so called "tent-transformation" on rank-1 lattice rules for the same. We briefly present some known results about cubature in these spaces and then present the results for approximation. We will start with the analysis of the approximation operator App:H_d -> L_2 where H_d is the half period cosine space. It can be shown that the w.c.e in these spaces can be related to the w.c.e in the Korobov space.

Related papers

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 ∞ 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 < α ≤ 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•Journal of Complexity•May 12, 2026•4 citations

Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate

Josef Dick, Takashi Goda, Kosuke Suzuki

We study a randomized quadrature algorithm to approximate the integral of periodic functions defined over the high-dimensional unit cube. Recent work by Kritzer, Kuo, Nuyens and Ullrich [J. Approx. Theory 240 (2019), pp. 96–113] shows that rank-1 lattice rules with a randomly chosen number of points and good generating vector achieve almost the optimal order of the randomized error in weighted Korobov spaces, and moreover, that the error is bounded independently of the dimension if the weight parameters, γ j \gamma _j , satisfy the summability condition ∑ j = 1 ∞ γ j 1 / α > ∞ \sum _{j=1}^{\infty }\gamma _j^{1/\alpha }>\infty , where α \alpha is a smoothness parameter. The argument is based on the existence result that at least half of the possible generating vectors yield almost the optimal order of the worst-case error in the same function spaces. In this paper we provide a component-by-component construction algorithm of such randomized rank-1 lattice rules, without any need to check whether the constructed generating vectors satisfy a desired worst-case error bound. Similarly to the above-mentioned work, we prove that our algorithm achieves almost the optimal order of the randomized error and that the error bound is independent of the dimension if the same condition ∑ j = 1 ∞ γ j 1 / α > ∞ \sum _{j=1}^{\infty }\gamma _j^{1/\alpha }>\infty holds. We also provide analogous results for tent-transformed lattice rules for weighted half-period cosine spaces and for polynomial lattice rules in weighted Walsh spaces, respectively.

arXiv:2109.11694•Mathematics of Computation•Jun 15, 2022•16 citations

Advanced Quasi-Monte Carlo Algorithms for High-dimensional Integration and Approximation

Gowri Suryanarayana

The aim of this research is to develop algorithms to approximate the solutions of problems defined on spaces of d-variate functions, where d can be arbitrarily large. We study quasi-Monte Carlo methods, which in contrast to Monte Carlo methods, use deterministic point sets. These methods converge significantly faster with well chosen points that minimize deterministic error bounds. Additionally, we require that the computational hardness of these methods has only a moderate or no dependence on d. We study this using the information complexity n(d, epsilon), the minimal number of information operations required to achieve an approximation with an error of epsilon or less. If n(d, epsilon) grows exponentially in d, the problem is said to have the 'curse of dimension' and the goal is to vanquish this curse. Our research resulted in several contributions. We studied multivariate integration for a Hilbert space of functions that are invariant under permutations of the variables; this is inspired from the symmetry constraints induced on solutions of the Schrödinger equation for indistinguishable particles. We showed that there exist quasi-Monte Carlo methods that achieve a convergence rate of O(n^−1/2) with the implied constant depending only polynomially on d and under some conditions independent of d (and that shifted rank-1 lattice rules can attain the same). We then provided a construction algorithm for a shifted rank-1 lattice that obtains the (almost) optimal rate of convergence. Next, we extended the use of rank-1 lattice points, traditionally used for the cubature and approximation of periodic functions, to the non-periodic setting. We did this in the cosine space setting, where we extensively studied the use of tent-transformed lattice points for cubature and approximation of nonperiodic functions. We were able to reuse algorithms from the periodic setting by establishing relations between the cosine space and the Korobov space of periodic functions. Finally we studied some special cases of approximation in two dimensions. We derived explicit expressions for various degrees of exactness for the Fibonacci lattice points. We end the thesis with an insight on the Lebesgue constant of trigonometric interpolation using lattice points as interpolation nodes.

•May 27, 2016•0 citations

Worst-case Lp-approximation of periodic functions using median lattice algorithms

Zexin Pan, Mou Cai, Josef Dick +2 more

We study the worst-case approximation of multivariate periodic functions from weighted Korobov spaces H d , α , γ with smoothness α > 1 / 2 and weights γ in L p ( [ 0 , 1 ] d ) , 1 ≤ p ≤ ∞ . We analyze a median lattice algorithm that reconstructs a truncated Fourier series by estimating coefficients on a hyperbolic-cross-type index set using R rank-1 lattice sampling rules with independent randomly chosen generating vectors, and then aggregating the coefficient estimators via the componentwise median. For odd R and odd prime lattice size N , where R depends logarithmically on N , we prove high-probability error bounds in both L ∞ and L 2 . Interpolation then yields the result for all p ∈ [ 1 , ∞ ] . In particular, with high probability, the worst-case L p -error is bounded, for any β > 0 , by C d , α , β , γ , τ , p R 1 2 + ( 1 2 − 1 p ) + N − α + ( 1 2 − 1 p ) + + β , where ( x ) + = max ⁡ { x , 0 } , and the constant C d , α , β , γ , τ , p is independent of N and R . For p = ∞ , the constant is dimension-independent under the summability condition ∑ j = 1 ∞ γ j 1 / ( 2 α ) < ∞ .

arXiv:2603.05271•Journal of Complexity•Oct 30, 2026•1 citation

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

L2-approximation using randomized lattice algorithms

Mou Cai, Takashi Goda, Yoshihito Kazashi

We propose a randomized lattice algorithm for approximating multivariate periodic functions over the d -dimensional unit cube from the weighted Korobov space with mixed smoothness α > 1 / 2 and product weights γ 1 , γ 2 , … ∈ [ 0 , 1 ] . Building upon the deterministic lattice algorithm by Kuo et al. (2006), we incorporate a randomized quadrature rule by Dick et al. (2022) to accelerate the convergence rate. This randomization involves drawing the number of points for function evaluations randomly, and selecting a good generating vector for rank-1 lattice points using the randomized component-by-component algorithm. We prove that our randomized algorithm achieves a worst-case root mean squared L 2 -approximation error of order ɛ M − α ( 2 α + 1 ) / ( 4 α + 1 ) + ɛ for an arbitrarily small ɛ ɛ > 0 , where M denotes the maximum number of function evaluations, and that the error bound is independent of the dimension d if the weights satisfy ∑ j = 1 ∞ γ j 1 / α < ∞ . Our upper bound converges faster than a lower bound on the worst-case L 2 -approximation error for deterministic rank-1 lattice-based approximation proved by Byrenheid et al. (2017). We also show a lower error bound of order M − α / 2 − 1 / 2 for our randomized algorithm, leaving a slight gap between the upper and lower bounds open for future research.

arXiv:2409.18757•Journal of Approximation Theory•Apr 1, 2026•7 citations
We analyse the worst case error (w.c.e) for approximation of d-variate non-periodic functions belonging to the weighted half-period cosine space. We use the so called "tent-transformation" on rank-1 lattice rules for the same. We briefly present some known results about cubature in these spaces and then present the results for approximation. We will start with the analysis of the approximation operator App:H_d -> L_2 where H_d is the half period cosine space. It can be shown that the w.c.e in these spaces can be related to the w.c.e in the Korobov space.
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 ∞ 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 < α ≤ 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.
We study a randomized quadrature algorithm to approximate the integral of periodic functions defined over the high-dimensional unit cube. Recent work by Kritzer, Kuo, Nuyens and Ullrich [J. Approx. Theory 240 (2019), pp. 96–113] shows that rank-1 lattice rules with a randomly chosen number of points and good generating vector achieve almost the optimal order of the randomized error in weighted Korobov spaces, and moreover, that the error is bounded independently of the dimension if the weight parameters, γ j \gamma _j , satisfy the summability condition ∑ j = 1 ∞ γ j 1 / α > ∞ \sum _{j=1}^{\infty }\gamma _j^{1/\alpha }>\infty , where α \alpha is a smoothness parameter. The argument is based on the existence result that at least half of the possible generating vectors yield almost the optimal order of the worst-case error in the same function spaces. In this paper we provide a component-by-component construction algorithm of such randomized rank-1 lattice rules, without any need to check whether the constructed generating vectors satisfy a desired worst-case error bound. Similarly to the above-mentioned work, we prove that our algorithm achieves almost the optimal order of the randomized error and that the error bound is independent of the dimension if the same condition ∑ j = 1 ∞ γ j 1 / α > ∞ \sum _{j=1}^{\infty }\gamma _j^{1/\alpha }>\infty holds. We also provide analogous results for tent-transformed lattice rules for weighted half-period cosine spaces and for polynomial lattice rules in weighted Walsh spaces, respectively.
The aim of this research is to develop algorithms to approximate the solutions of problems defined on spaces of d-variate functions, where d can be arbitrarily large. We study quasi-Monte Carlo methods, which in contrast to Monte Carlo methods, use deterministic point sets. These methods converge significantly faster with well chosen points that minimize deterministic error bounds. Additionally, we require that the computational hardness of these methods has only a moderate or no dependence on d. We study this using the information complexity n(d, epsilon), the minimal number of information operations required to achieve an approximation with an error of epsilon or less. If n(d, epsilon) grows exponentially in d, the problem is said to have the 'curse of dimension' and the goal is to vanquish this curse. Our research resulted in several contributions. We studied multivariate integration for a Hilbert space of functions that are invariant under permutations of the variables; this is inspired from the symmetry constraints induced on solutions of the Schrödinger equation for indistinguishable particles. We showed that there exist quasi-Monte Carlo methods that achieve a convergence rate of O(n^−1/2) with the implied constant depending only polynomially on d and under some conditions independent of d (and that shifted rank-1 lattice rules can attain the same). We then provided a construction algorithm for a shifted rank-1 lattice that obtains the (almost) optimal rate of convergence. Next, we extended the use of rank-1 lattice points, traditionally used for the cubature and approximation of periodic functions, to the non-periodic setting. We did this in the cosine space setting, where we extensively studied the use of tent-transformed lattice points for cubature and approximation of nonperiodic functions. We were able to reuse algorithms from the periodic setting by establishing relations between the cosine space and the Korobov space of periodic functions. Finally we studied some special cases of approximation in two dimensions. We derived explicit expressions for various degrees of exactness for the Fibonacci lattice points. We end the thesis with an insight on the Lebesgue constant of trigonometric interpolation using lattice points as interpolation nodes.
We study the worst-case approximation of multivariate periodic functions from weighted Korobov spaces H d , α , γ with smoothness α > 1 / 2 and weights γ in L p ( [ 0 , 1 ] d ) , 1 ≤ p ≤ ∞ . We analyze a median lattice algorithm that reconstructs a truncated Fourier series by estimating coefficients on a hyperbolic-cross-type index set using R rank-1 lattice sampling rules with independent randomly chosen generating vectors, and then aggregating the coefficient estimators via the componentwise median. For odd R and odd prime lattice size N , where R depends logarithmically on N , we prove high-probability error bounds in both L ∞ and L 2 . Interpolation then yields the result for all p ∈ [ 1 , ∞ ] . In particular, with high probability, the worst-case L p -error is bounded, for any β > 0 , by C d , α , β , γ , τ , p R 1 2 + ( 1 2 − 1 p ) + N − α + ( 1 2 − 1 p ) + + β , where ( x ) + = max ⁡ { x , 0 } , and the constant C d , α , β , γ , τ , p is independent of N and R . For p = ∞ , the constant is dimension-independent under the summability condition ∑ j = 1 ∞ γ j 1 / ( 2 α ) < ∞ .
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 propose a randomized lattice algorithm for approximating multivariate periodic functions over the d -dimensional unit cube from the weighted Korobov space with mixed smoothness α > 1 / 2 and product weights γ 1 , γ 2 , … ∈ [ 0 , 1 ] . Building upon the deterministic lattice algorithm by Kuo et al. (2006), we incorporate a randomized quadrature rule by Dick et al. (2022) to accelerate the convergence rate. This randomization involves drawing the number of points for function evaluations randomly, and selecting a good generating vector for rank-1 lattice points using the randomized component-by-component algorithm. We prove that our randomized algorithm achieves a worst-case root mean squared L 2 -approximation error of order ɛ M − α ( 2 α + 1 ) / ( 4 α + 1 ) + ɛ for an arbitrarily small ɛ ɛ > 0 , where M denotes the maximum number of function evaluations, and that the error bound is independent of the dimension d if the weights satisfy ∑ j = 1 ∞ γ j 1 / α < ∞ . Our upper bound converges faster than a lower bound on the worst-case L 2 -approximation error for deterministic rank-1 lattice-based approximation proved by Byrenheid et al. (2017). We also show a lower error bound of order M − α / 2 − 1 / 2 for our randomized algorithm, leaving a slight gap between the upper and lower bounds open for future research.