Randomized least-squares with minimal oversampling and interpolation in general spaces

2023/06/12 by Chkifa, Abdellah, Dolbeault, Matthieu · 2 citations
#41A05 #41A65 #41A81 #65D05 #65D15 #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2306.07435

Abstract

In approximation of functions based on point values, least-squares methods provide more stability than interpolation, at the expense of increasing the sampling budget. We show that near-optimal approximation error can nevertheless be achieved, in an expected L² sense, as soon as the sample size m is larger than the dimension n of the approximation space by a constant ratio. On the other hand, for m=n, we obtain an interpolation strategy with a stability factor of order n. The proposed sampling algorithms are greedy procedures based on arXiv:0808.0163 and arXiv:1508.03261, with polynomial computational complexity.

Cited by

• Refinement-based Christoffel sampling for least squares approximation in non-orthogonal bases
• Universal L₂-approximation using median lattice algorithms

Related

• On the stability and accuracy of least squares approximations
• Stability of Least Squares Approximation under Random Sampling
• Near-optimal sampling strategies for multivariate function approximation on general domains
• Error Guarantees for Least Squares Approximation with Noisy Samples in Domain Adaptation
• Adaptive approximation by optimal weighted least squares methods