Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices. (English) Zbl 1455.65240
Summary: In this work, we consider the approximate reconstruction of high-dimensional periodic functions based on sampling values. As sampling schemes, we utilize so-called reconstructing multiple rank-1 lattices, which combine several preferable properties such as easy constructability, the existence of high-dimensional fast Fourier transform algorithms, high reliability, and low oversampling factors. Especially, we show error estimates for functions from Sobolev Hilbert spaces of generalized mixed smoothness. For instance, when measuring the sampling error in the \(L_2\)-norm, we show sampling error estimates where the exponent of the main part reaches those of the optimal sampling rate except for an offset of \(1 / 2 + {\varepsilon}\), i.e., the exponent is almost a factor of two better up to the mentioned offset compared to single rank-1 lattice sampling. Various numerical tests in medium and high dimensions demonstrate the high performance and confirm the obtained theoretical results of multiple rank-1 lattice sampling.
MSC:
| 65T40 | Numerical methods for trigonometric approximation and interpolation |
| 42B05 | Fourier series and coefficients in several variables |
| 42B35 | Function spaces arising in harmonic analysis |
| 65D30 | Numerical integration |
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
| 65Y20 | Complexity and performance of numerical algorithms |
Keywords:
approximation of multivariate periodic functions; trigonometric polynomials; generalized hyperbolic cross; generalized mixed smoothness; lattice rule; multiple rank-1 lattice; fast Fourier transformReferences:
| [2] | Byrenheid, G.; Dũng, D.; Sickel, W.; Ullrich, T., Sampling on energy-norm based sparse grids for the optimal recovery of sobolev type functions in \(H^\gamma \), J. Approx. Theory, 207, 207-231 (2016) · Zbl 1347.42003 |
| [3] | Byrenheid, G.; Kämmerer, L.; Ullrich, T.; Volkmer, T., Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness, Numer. Math., 136, 993-1034 (2017) · Zbl 1422.65467 |
| [4] | Cools, R.; Nuyens, D., Fast component-by-component construction, a reprise for different kernels, (Niederreiter, H.; Talay, D., Monte Carlo and Quasi-Monte Carlo Methods 2004 (2006), Springer Berlin Heidelberg), 373-387 · Zbl 1099.65006 |
| [5] | Dũng, D.; Temlyakov, V. N.; Ullrich, T., Hyperbolic Cross Approximation (2018), Advanced Courses in Mathematics - CRM Barcelona: Advanced Courses in Mathematics - CRM Barcelona Birkhäuser, Cham · Zbl 1414.41001 |
| [6] | Dick, J.; Kuo, F. Y.; Sloan, I. H., High-dimensional integration: The quasi-Monte Carlo way, Acta Numer., 22, 133-288 (2013) · Zbl 1296.65004 |
| [7] | M. Döhler, L. Kämmerer, S. Kunis, D. Potts, NHCFFT, \( \textsc{Matlab}{}^{\text{\circledR}}\) http://www.tu-chemnitz.de/lkae/nhcfft; M. Döhler, L. Kämmerer, S. Kunis, D. Potts, NHCFFT, \( \textsc{Matlab}{}^{\text{\circledR}}\) http://www.tu-chemnitz.de/lkae/nhcfft |
| [8] | Griebel, M.; Hamaekers, J., Fast discrete fourier transform on generalized sparse grids, (Garcke, J.; Pflüger, D., Sparse Grids and Applications - Munich 2012. Sparse Grids and Applications - Munich 2012, Lect. Notes Comput. Sci. Eng, vol. 97 (2014), Springer International Publishing) · Zbl 1316.65119 |
| [9] | Hinrichs, A.; Markhasin, L.; Oettershagen, J.; Ullrich, T., Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions, Numer. Math., 134, 163-196 (2016) · Zbl 1358.65004 |
| [10] | Kämmerer, L., Reconstructing hyperbolic cross trigonometric polynomials by sampling along rank-1 lattices, SIAM J. Numer. Anal., 51, 2773-2796 (2013) · Zbl 1291.42011 |
| [11] | Kämmerer, L., High Dimensional Fast Fourier Transform Based on Rank-1 Lattice Sampling (2014), Universitätsverlag Chemnitz, Dissertation |
| [12] | Kämmerer, L., Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices, (Fasshauer, G. E.; Schumaker, L. L., Approximation Theory XIV: San Antonio 2013 (2014), Springer International Publishing), 255-271 · Zbl 1325.65189 |
| [13] | Kämmerer, L., Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform, Appl. Comput. Harmon. Anal. (2017), in press · Zbl 1423.60012 |
| [14] | Kämmerer, L., Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials, J. Fourier Anal. Appl., 24, 17-44 (2018) · Zbl 1401.65155 |
| [15] | L. Kämmerer, D. Potts, T. Volkmer, High-dimensional sparse FFT based on sampling along multiple rank-1 lattices. ArXiv e-prints 1711.05152, 2017.; L. Kämmerer, D. Potts, T. Volkmer, High-dimensional sparse FFT based on sampling along multiple rank-1 lattices. ArXiv e-prints 1711.05152, 2017. |
| [16] | Kämmerer, L.; Potts, D.; Volkmer, T., Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling, J. Complexity, 31, 543-576 (2015) · Zbl 1320.65204 |
| [18] | Korobov, N. M., On the approximate computation of multiple integrals, Dokl. Akad. Nauk, 124, 1207-1210 (1959), In Russian · Zbl 0089.04201 |
| [19] | Korobov, N. M., Number-Theoretic Methods in Approximate Analysis (1963), Fizmatgiz: Fizmatgiz Moscow, In Russian · Zbl 0115.11703 |
| [20] | Kuo, F. Y.; Sloan, I. H.; Woźniakowski, H., Lattice rules for multivariate approximation in the worst case setting, (Niederreiter, H.; Talay, D., Monte Carlo and Quasi-MOnte Carlo Methods 2004 (2006), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin), 289-330 · Zbl 1097.65133 |
| [21] | Kuo, F. Y.; Sloan, I. H.; Woźniakowski, H., Lattice rule algorithms for multivariate approximation in the average case setting, J. Complexity, 24, 283-323 (2008) · Zbl 1141.65012 |
| [23] | Li, D.; Hickernell, F. J., Trigonometric spectral collocation methods on lattices, (Cheng, S. Y.; Shu, C.-W.; Tang, T., Recent Advances in Scientific Computing and Partial Differential Equations. Recent Advances in Scientific Computing and Partial Differential Equations, Contemp. Math, vol. 330 (2003), AMS), 121-132 · Zbl 1036.65093 |
| [24] | Sloan, I. H.; Joe, S., Lattice Methods for Multiple Integration. Oxford Science Publications (1994), The Clarendon Press Oxford University Press: The Clarendon Press Oxford University Press New York · Zbl 0855.65013 |
| [25] | Sloan, I. H.; Reztsov, A. V., Component-by-component construction of good lattice rules, Math. Comp., 71, 263-273 (2002) · Zbl 0985.65018 |
| [26] | Temlyakov, V. N., Reconstruction of periodic functions of several variables from the values at the nodes of number-theoretic nets, Anal. Math., 12, 287-305 (1986), In Russian · Zbl 0621.41004 |
| [27] | Temlyakov, V. N., (Approximation of Periodic Functions. Approximation of Periodic Functions, Computational Mathematics and Analysis Series (1993), Nova Science Publishers Inc: Nova Science Publishers Inc Commack, NY) · Zbl 0899.41001 |
| [28] | T. Volkmer, taylorR1Lnfft, \( \textsc{Matlab}{}^{\text{\circledR}}\) http://www.tu-chemnitz.de/tovo/software; T. Volkmer, taylorR1Lnfft, \( \textsc{Matlab}{}^{\text{\circledR}}\) http://www.tu-chemnitz.de/tovo/software |
| [30] | Yserentant, H., (Regularity and Approximability of Electronic Wave Functions. Regularity and Approximability of Electronic Wave Functions, Lecture Notes in Mathematics (2010), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1204.35003 |
| [31] | Zaremba, S. K., La méthode des bons treillis pour le calcul des intégrales multiples, (Applications of Number Theory To Numerical Analysis (Proc. Sympos., Univ. Montreal, Montreal, Que., 1971) (1972), Academic Press: Academic Press New York), 39-119 · Zbl 0246.65009 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
