Function integration, reconstruction and approximation using rank-1 lattices

Kuo, Frances; Migliorati, Giovanni; Nobile, Fabio; Nuyens, Dirk

doi:10.1090/mcom/3595

Function integration, reconstruction and approximation using rank-$1$ lattices
HTML articles powered by AMS MathViewer

by Frances Y. Kuo, Giovanni Migliorati, Fabio Nobile and Dirk Nuyens HTML | PDF

Math. Comp. 90 (2021), 1861-1897 Request permission

Abstract:

We consider rank-$1$ lattices for integration and reconstruction of functions with series expansion supported on a finite index set. We explore the connection between the periodic Fourier space and the non-periodic cosine space and Chebyshev space, via tent transform and then cosine transform, to transfer known results from the periodic setting into new insights for the non-periodic settings. Fast discrete cosine transform can be applied for the reconstruction phase. To reduce the size of the auxiliary index set in the associated component-by-component (CBC) construction for the lattice generating vectors, we work with a bi-orthonormal set of basis functions, leading to three methods for function reconstruction in the non-periodic settings. We provide new theory and efficient algorithmic strategies for the CBC construction. We also interpret our results in the context of general function approximation and discrete least-squares approximation.

References

Glenn Byrenheid, Lutz Kämmerer, Tino Ullrich, and Toni Volkmer, Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness, Numer. Math. 136 (2017), no. 4, 993–1034. MR 3671595, DOI 10.1007/s00211-016-0861-7
Abdellah Chkifa, Albert Cohen, Giovanni Migliorati, Fabio Nobile, and Raul Tempone, Discrete least squares polynomial approximation with random evaluations—application to parametric and stochastic elliptic PDEs, ESAIM Math. Model. Numer. Anal. 49 (2015), no. 3, 815–837. MR 3342229, DOI 10.1051/m2an/2014050
Albert Cohen, Mark A. Davenport, and Dany Leviatan, On the stability and accuracy of least squares approximations, Found. Comput. Math. 13 (2013), no. 5, 819–834. MR 3105946, DOI 10.1007/s10208-013-9142-3
Ronald Cools, Frances Y. Kuo, and Dirk Nuyens, Constructing lattice rules based on weighted degree of exactness and worst case error, Computing 87 (2010), no. 1-2, 63–89. MR 2601775, DOI 10.1007/s00607-009-0076-1
Ronald Cools, Frances Y. Kuo, Dirk Nuyens, and Gowri Suryanarayana, Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions, J. Complexity 36 (2016), 166–181. MR 3530643, DOI 10.1016/j.jco.2016.05.004
Ronald Cools and Koen Poppe, Chebyshev lattices, a unifying framework for cubature with Chebyshev weight function, BIT 51 (2011), no. 2, 275–288. MR 2806531, DOI 10.1007/s10543-010-0300-6
Josef Dick, Dirk Nuyens, and Friedrich Pillichshammer, Lattice rules for nonperiodic smooth integrands, Numer. Math. 126 (2014), no. 2, 259–291. MR 3150223, DOI 10.1007/s00211-013-0566-0
Fred J. Hickernell, Obtaining $O(N^{-2+\epsilon })$ convergence for lattice quadrature rules, Monte Carlo and quasi-Monte Carlo methods, 2000 (Hong Kong), Springer, Berlin, 2002, pp. 274–289. MR 1958860
Lutz Kämmerer, Reconstructing hyperbolic cross trigonometric polynomials by sampling along rank-1 lattices, SIAM J. Numer. Anal. 51 (2013), no. 5, 2773–2796. MR 3115464, DOI 10.1137/120871183
Lutz Kämmerer, Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices, Approximation theory XIV: San Antonio 2013, Springer Proc. Math. Stat., vol. 83, Springer, Cham, 2014, pp. 255–271. MR 3218580, DOI 10.1007/978-3-319-06404-8_{1}4
Lutz Kämmerer, Daniel Potts, and Toni Volkmer, Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling, J. Complexity 31 (2015), no. 4, 543–576. MR 3348081, DOI 10.1016/j.jco.2015.02.004
Lutz Kämmerer, Stefan Kunis, and Daniel Potts, Interpolation lattices for hyperbolic cross trigonometric polynomials, J. Complexity 28 (2012), no. 1, 76–92. MR 2871786, DOI 10.1016/j.jco.2011.05.002
Lutz Kämmerer and Toni Volkmer, Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices, J. Approx. Theory 246 (2019), 1–27. MR 3959171, DOI 10.1016/j.jat.2019.05.001
Frances Y. Kuo, Ian H. Sloan, and Henryk Woźniakowski, Lattice rules for multivariate approximation in the worst case setting, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 289–330. MR 2208715, DOI 10.1007/3-540-31186-6_{1}8
Frances Y. Kuo, Ian H. Sloan, and Henryk Woźniakowski, Lattice rule algorithms for multivariate approximation in the average case setting, J. Complexity 24 (2008), no. 2, 283–323. MR 2400322, DOI 10.1016/j.jco.2006.10.006
Frances Y. Kuo, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, Multivariate $L_\infty$ approximation in the worst case setting over reproducing kernel Hilbert spaces, J. Approx. Theory 152 (2008), no. 2, 135–160. MR 2422145, DOI 10.1016/j.jat.2007.11.006
Frances Y. Kuo, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, On the power of standard information for multivariate approximation in the worst case setting, J. Approx. Theory 158 (2009), no. 1, 97–125. MR 2523723, DOI 10.1016/j.jat.2008.01.011
Frances Y. Kuo, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, Lattice algorithms for multivariate $L_\infty$ approximation in the worst-case setting, Constr. Approx. 30 (2009), no. 3, 475–493. MR 2558690, DOI 10.1007/s00365-009-9075-x
Dong Li and Fred J. Hickernell, Trigonometric spectral collocation methods on lattices, Recent advances in scientific computing and partial differential equations (Hong Kong, 2002) Contemp. Math., vol. 330, Amer. Math. Soc., Providence, RI, 2003, pp. 121–132. MR 2011715, DOI 10.1090/conm/330/05887
S. A. Martucci, Symmetric convolution and the discrete sine and cosine transforms, IEEE Transactions on Signal Processing, 42:1038–1051, 1994.
G. Migliorati, F. Nobile, E. von Schwerin, and R. Tempone, Analysis of discrete $L^2$ projection on polynomial spaces with random evaluations, Found. Comput. Math. 14 (2014), no. 3, 419–456. MR 3201952, DOI 10.1007/s10208-013-9186-4
Giovanni Migliorati and Fabio Nobile, Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets, J. Complexity 31 (2015), no. 4, 517–542. MR 3348080, DOI 10.1016/j.jco.2015.02.001
Giovanni Migliorati, Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets, J. Approx. Theory 189 (2015), 137–159. MR 3280676, DOI 10.1016/j.jat.2014.10.010
Hans Munthe-Kaas and Tor Sørevik, Multidimensional pseudo-spectral methods on lattice grids, Appl. Numer. Math. 62 (2012), no. 3, 155–165. MR 2878018, DOI 10.1016/j.apnum.2011.11.002
D. Potts, T. Volkmer, Fast and exact reconstruction of arbitratry multivariate algebraic polynomials in Chebyshev form, 2015 International Conference on Sampling Theory and Applications (SampTA), IEEE, 392–396, 2015.
Daniel Potts and Toni Volkmer, Sparse high-dimensional FFT based on rank-1 lattice sampling, Appl. Comput. Harmon. Anal. 41 (2016), no. 3, 713–748. MR 3546427, DOI 10.1016/j.acha.2015.05.002
I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994. MR 1442955
Gowri Suryanarayana, Dirk Nuyens, and Ronald Cools, Reconstruction and collocation of a class of non-periodic functions by sampling along tent-transformed rank-1 lattices, J. Fourier Anal. Appl. 22 (2016), no. 1, 187–214. MR 3448919, DOI 10.1007/s00041-015-9412-3
Yuya Suzuki, Gowri Suryanarayana, and Dirk Nuyens, Strang splitting in combination with rank-1 and rank-$r$ lattices for the time-dependent Schrödinger equation, SIAM J. Sci. Comput. 41 (2019), no. 6, B1254–B1283. MR 4031477, DOI 10.1137/18M1207879
Y. Suzuki, D. Nuyens, Rank-$1$ lattices and higher-order exponential splitting for the time-dependent Schrödinger equation, in B. Tuffin, and P. L’Ecuyer (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2018, Springer, 485–502, 2020.
T. Volkmer, sparseFFTr1l software library, https://www-user.tu-chemnitz.de/~tovo/software.php.en
G. W. Wasilkowski and H. Woźniakowski, Weighted tensor product algorithms for linear multivariate problems, J. Complexity 15 (1999), no. 3, 402–447. Dagstuhl Seminar on Algorithms and Complexity for Continuous Problems (1998). MR 1716741, DOI 10.1006/jcom.1999.0512
G. W. Wasilkowski and H. Woźniakowski, On the power of standard information for weighted approximation, Found. Comput. Math. 1 (2001), no. 4, 417–434. MR 1857723, DOI 10.1007/s102080010016
Xiaoyan Zeng, King-Tai Leung, and Fred J. Hickernell, Error analysis of splines for periodic problems using lattice designs, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 501–514. MR 2208728, DOI 10.1007/3-540-31186-6_{3}1
Xiaoyan Zeng, Peter Kritzer, and Fred J. Hickernell, Spline methods using integration lattices and digital nets, Constr. Approx. 30 (2009), no. 3, 529–555. MR 2558692, DOI 10.1007/s00365-009-9072-0
Tao Zhou, Akil Narayan, and Zhiqiang Xu, Multivariate discrete least-squares approximations with a new type of collocation grid, SIAM J. Sci. Comput. 36 (2014), no. 5, A2401–A2422. MR 3270030, DOI 10.1137/130950434