Multivariate Approximation and high-dimensional sparse FFT based on rank-1 lattice sampling

Más información sobre el libro

This work addresses the fast evaluation and reconstruction of multivariate trigonometric polynomials with frequencies on arbitrary finite index sets, utilizing rank-1 lattices for spatial discretization. It explores the approximation of multivariate smooth periodic functions through trigonometric polynomials, leveraging a one-dimensional FFT on function samples. The smoothness is characterized by the decay of Fourier coefficients, with various sampling error estimates supported by numerical tests in up to 25 dimensions. The study also examines perturbed rank-1 lattice nodes and introduces a fast Taylor expansion approximation method. A significant contribution is adapting these methods to the non-periodic case, employing multivariate algebraic polynomials in Chebyshev form and rank-1 Chebyshev lattices for spatial discretization. This approach enables the use of fast algorithms based on one-dimensional DCT, with smoothness characterized by Chebyshev coefficient decay. Estimates for sampling errors and numerical tests for up to 25 dimensions are provided. Additionally, a high-dimensional sparse FFT method based on rank-1 lattice sampling is developed, facilitating the identification of unknown frequency locations corresponding to the largest Fourier or Chebyshev coefficients of a function.