# Optimal sampling for least-squares approximation

arXiv: https://arxiv.org/abs/2409.02342 · HTML: https://mlsanity.com/paper/2409.02342/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 146 references that are in the map.
- First posted on arXiv 4 Sep 2024.

## Builds on (most cited first, 28 of 28)

- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Gradient-enhanced physics-informed neural networks for forward and inverse PDE problems](https://mlsanity.com/paper/2111.02801/) (2021)
- [Sobolev Training for Neural Networks](https://mlsanity.com/paper/1706.04859/) (2017)
- [Operator Learning: Algorithms and Analysis](https://mlsanity.com/paper/2402.15715/) (2024)
- [A Mathematical Guide to Operator Learning](https://mlsanity.com/paper/2312.14688/) (2023)
- [Derivative-Informed Neural Operator: An Efficient Framework for High-Dimensional Parametric Derivative Learning](https://mlsanity.com/paper/2206.10745/) (2022)
- [Derivative-Informed Projected Neural Networks for High-Dimensional Parametric Maps Governed by PDEs](https://mlsanity.com/paper/2011.15110/) (2020)
- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [Leveraged volume sampling for linear regression](https://mlsanity.com/paper/1802.06749/) (2018)
- [A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms](https://mlsanity.com/paper/1812.08723/) (2018)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [Nystr"om landmark sampling and regularized Christoffel functions](https://mlsanity.com/paper/1905.12346/) (2019)
- [Learning smooth functions in high dimensions: from sparse polynomials to deep neural networks](https://mlsanity.com/paper/2404.03761/) (2024)
- [CAS4DL: Christoffel Adaptive Sampling for function approximation via Deep Learning](https://mlsanity.com/paper/2208.12190/) (2022)
- [A statistical perspective of sampling scores for linear regression](https://mlsanity.com/paper/1507.05870/) (2015)
- [A unified framework for learning with nonlinear model classes from arbitrary linear samples](https://mlsanity.com/paper/2311.14886/) (2023)
- [Gradient-enhanced deep neural network approximations](https://mlsanity.com/paper/2211.04226/) (2022)
- [Optimal sampling for stochastic and natural gradient descent](https://mlsanity.com/paper/2402.03113/) (2024)
- [Convergence bounds for nonlinear least squares and applications to tensor recovery](https://mlsanity.com/paper/2108.05237/) (2021)
- [Signal reconstruction using determinantal sampling](https://mlsanity.com/paper/2310.09437/) (2023)
- [Weighted least-squares approximation with determinantal point processes and generalized volume sampling](https://mlsanity.com/paper/2312.14057/) (2023)
- [Weighted Monte Carlo with least squares and randomized extended Kaczmarz for option pricing](https://mlsanity.com/paper/1910.07241/) (2019)
- [Convergence bounds for local least squares approximation](https://mlsanity.com/paper/2208.10954/) (2022)

## Built on by (most cited first, 6 of 6)

- [Learning where to learn: Training data distribution optimization for scientific machine learning](https://mlsanity.com/paper/2505.21626/) (2025)
- [Natural gradient descent with momentum](https://mlsanity.com/paper/2604.15554/) (2026)
- [Adaptivity Under Realizability Constraints: Comparing In-Context and Agentic Learning](https://mlsanity.com/paper/2605.04995/) (2026)
- [Hybrid least squares for learning functions from highly noisy data](https://mlsanity.com/paper/2507.02215/) (2025)
- [Infinite dimensional generative sensing](https://mlsanity.com/paper/2603.03196/) (2026)
- [Active Learning for Conditional Generative Compressed Sensing](https://mlsanity.com/paper/2605.05435/) (2026)

## Abstract (arXiv)

Least-squares approximation is one of the most important methods for recovering an unknown function from data. While in many applications the data is fixed, in many others there is substantial freedom to choose where to sample. In this paper, we review recent progress on near-optimal random sampling strategies for (weighted) least-squares approximation in arbitrary linear spaces. We introduce the Christoffel function as a key quantity in the analysis of (weighted) least-squares approximation from random samples, then show how it can be used to construct a random sampling strategy, termed Christoffel sampling, that possesses near-optimal sample complexity: namely, the number of samples scales log-linearly in the dimension of the approximation space n. We discuss a series of variations, extensions and further topics, and throughout highlight connections to approximation theory, machine learning, information-based complexity and numerical linear algebra. Finally, motivated by various contemporary applications, we consider a generalization of the classical setting where the samples need not be pointwise samples of a scalar-valued function, and the approximation space need not be linear. We show that, even in this significantly more general setting, suitable generalizations of Christoffel function still determine the sample complexity. Consequently, these can be used to design enhanced, Christoffel sampling strategies in a unified way for general recovery problems. This article is largely self-contained, and intended to be accessible to nonspecialists.