Approximation of periodic functions: lattices rule

Abstract

I will discuss the approximation of multivariate functions which can be expressed as absolutely converging Fourier series from a class of periodic Sobolev spaces over $[0, 1]^d$ and with the error of such method measured in the $L_2$ norm. For such spaces we know that quadrature/cubature rules based on lattice points are a particular good choice and actually achieve a near optimal rate of convergence. We could hence try to approximate the $m$ most important Fourier coefficients with indices collected in the set $\Lambda_m$ (determined by the function space) by using such a good lattice point set to approximate the integrals defining those Fourier coefficients. Unfortunately, such a "lattice approximation method" only achieves half of the theoretical optimal rate of convergence for $d \ge 2$ --- if measured in the number of function evaluations $n$, see [2, 4, 6, 7]. This also happens for the "lattice kernel approximation method" as this is a defect from the structure in the lattice points (when using the full point set) [4], see also [1].

Surprisingly it was shown that, with high probability, point sets sampled uniformly at random from $[0, 1]^d$, in combination with a least squares methods to determine the Fourier coefficients in $\Lambda_m$ based on these samples, will converge with the optimal rate in $n$, see [3, 5]. Note that this is not necessarily a randomised algorithm as the points could be tested and saved. Moreover, recently it was also shown that a lattice point set with roughly $m^2$ points can be subsampled to the right order to get close to the optimal rate in $n$ as well, see [1].

In the narrative above I used the convergence in terms of the "information complexity" in which the number of function evaluations $n$ is used as the main contributor to the computational complexity. However, the cost of an algorithm in "information-based complexity" is defined as the sum of the information complexity and the algorithmic/combinatorial cost to compute that approximation, see [8]. While often the algorithmic/combinatorial cost can be ignored, it makes quite a difference here as the algorithms from [1, 3, 5] are faced with solving a least squares system of size $n \times m$, with $n$ of comparable size to $m$, to find their $m$ Fourier coefficients, which could be solved with pre-computations say in roughly $O(n^2)$, depending on the method, having some logarithmic factors (which are actually the topic of study in those papers). On the other hand, the algorithms in [4, 6, 7] can leverage the FFT to compute their Fourier coefficients in time $O(n \log n)$. Suddenly lattice points are not so bad anymore as all these methods have similar complexities...

[1] Bartel, Kammerer, Potts, T. Ullrich (2024). On the reconstruction of functions from values at subsampled quadrature points. Mathematics of Computation 93:785–809, 2024.

[2] Byrenheid, Kammerer, T. Ullrich, Volkmer (2017). Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness. Numerische Mathematik 136:993–1034, 2017.

[3] Dolbeault, Krieg, M. Ullrich (2023). A sharp upper bound for sampling numbers in $L_2$. Applied and Computational Harmonic Analysis 63:114-134, 2023.

[4] Kaarnioja, Kazashi, Kuo, Nobile, Sloan (2022). Fast approximation by periodic kernel-based lattice-point interpolation with application in uncertainty quantification. Numerische Mathematik 150:33–77, 2022.

[5] Krieg, M. Ullrich (2021). Function values are enough for $L_2$ approximation. Foundations of Computational Mathematics, 21(4):1141–1151, 2021.

[6] Kuo, Migliorati, Nobile, Nuyens (2021). Function integration, reconstruction and approximation using rank-1 lattice rules. Mathematics of Computation 90(330):1861-1897, 2021.

[7] Kuo, Mo, Nuyens (2024). Constructing embedded lattice-based algorithms for multivariate function approximation with a composite number of points. Constructive Approximation, published online 2024.

[8] Traub, Wasilkowski, Wozniakowski (1988). Information-Based Complexity. Academic Press. 1988.