Universal L₂-approximation using median lattice algorithms

2025/09/29 by Zexin Pan, Pan, Zexin, Takashi Goda +3
Mathematics · #FOS: Mathematics #Numerical Analysis (math.NA) #Statistical and numerical algorithms

paper · pdf · doi:10.48550/arxiv.2509.24582

openalex publication_date 2025/09/29 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28

Abstract

We study the problem of multivariate L₂-approximation of functions in a weighted Korobov space using a median lattice-based algorithm recently proposed by the authors. In the original work, the algorithm requires knowledge of the smoothness and weights of the Korobov space to construct the hyperbolic cross index set, where each coefficient is estimated via the median of approximations obtained from randomly shifted, randomly chosen rank-1 lattice rules. In this paper, we introduce a universal median lattice-based algorithm, which eliminates the need for any prior information on smoothness and weights. Although the tractability property of the algorithm slightly deteriorates, we prove that, for individual functions in the Korobov space with arbitrary smoothness and (downward-closed) weights, it achieves an L₂-approximation error arbitrarily close to the optimal rate with respect to the number of function evaluations. Numerical experiments are conducted to support our theoretical claim.

Citations

• Minimal Subsampled Rank-1 Lattices for Multivariate Approximation with Optimal Convergence Rate
• L₂-approximation using median lattice algorithms
• L₂-approximation using randomized lattice algorithms
• Randomized least-squares with minimal oversampling and interpolation in general spaces
• Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
• Lattice algorithms for multivariate approximation in periodic spaces with general weight parameters
• Optimal confidence for Monte Carlo integration of smooth functions
• Solvable Integration Problems and Optimal Sample Size Selection
• Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices
• Optimal Monte Carlo Methods for L²-Approximation
• Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform
• Optimal weighted least-squares methods
• Hyperbolic Cross Approximation
• Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness

Related

• L₂-approximation using median lattice algorithms
• L₂-approximation using randomized lattice algorithms
• A lattice algorithm with multiple shifts for function approximation in Korobov spaces
• Lattice algorithms for multivariate approximation in periodic spaces with general weight parameters
• Constructing Embedded Lattice-based Algorithms for Multivariate Function Approximation with a Composite Number of Points