Abstract
Least-squares approximation is one of the most important methods forrecovering an unknown function from data. While in many applications the datais fixed, in many others there is substantial freedom to choose where tosample. In this paper, we review recent progress on near-optimal randomsampling strategies for (weighted) least-squares approximation in arbitrarylinear spaces. We introduce the Christoffel function as a key quantity in theanalysis of (weighted) least-squares approximation from random samples, thenshow how it can be used to construct a random sampling strategy, termedChristoffel sampling, that possesses near-optimal sample complexity: namely,the number of samples scales log-linearly in the dimension of the approximationspace $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, motivatedby various contemporary applications, we consider a generalization of theclassical setting where the samples need not be pointwise samples of ascalar-valued function, and the approximation space need not be linear. We showthat, even in this significantly more general setting, suitable generalizationsof Christoffel function still determine the sample complexity. Consequently,these can be used to design enhanced, Christoffel sampling strategies in aunified way for general recovery problems. This article is largelyself-contained, and intended to be accessible to nonspecialists.