Weighted least-squares approximation with determinantal point processes and generalized volume sampling

Anthony Nouy, Bertrand MichelarXiv 2023 · DOI · arXiv

Introduction

In many scientific and engineering domains, reconstructing a complex function—such as a climate model or a physical simulation—is a fundamental task. However, these functions are often expensive to evaluate, meaning we can only afford to "probe" them at a limited number of points. The standard mathematical approach is to project the target function onto a simpler $m$-dimensional space (e.g., polynomials) using Weighted Least-Squares (WLS).

Traditionally, WLS relies on independent and identically distributed (i.i.d.) random sampling. While theoretically sound, i.i.d. sampling suffers from a significant practical flaw: points can accidentally cluster together. When samples are too close, the "Gram matrix"—which tracks the relationships between basis functions at those points—becomes nearly singular or unstable. To guarantee stability, current theory suggests we need roughly $O(m \log m)$ points, which is often significantly more than the $m$ points we would ideally want to use. This paper introduces a more efficient sampling paradigm using Determinantal Point Processes (DPP) and volume sampling to achieve stable, quasi-optimal approximations with fewer samples.

The Stability Challenge in Sampling

The core difficulty in function approximation is ensuring that the chosen sample points provide a well-conditioned representation of the underlying space. In i.i.d. sampling, the lack of coordination between points leads to a high probability of poor coverage. The authors propose moving toward dependent sampling strategies, where the choice of one point influences the likelihood of choosing another, specifically to promote "repulsion" between samples.

Proposed Methodologies

The research explores several dependent sampling strategies designed to maintain the stability of the Gram matrix:

  1. Projection Determinantal Point Processes (DPP): This method acts as a "repulsive" sampling mechanism. The probability of selecting a specific set of points is proportional to the volume of the parallelepiped spanned by their feature vectors. If two points are similar (collinear in feature space), the probability of picking both drops to zero, naturally promoting diversity across the sample set.
  2. Generalized Volume Sampling: The authors extend the concept of "volume-rescaled sampling" to more general measures. In this distribution, the density is proportional to the determinant of the empirical Gram matrix, ensuring that sets of points that would lead to instability are avoided.
  3. Mixture Measures: To achieve stronger "almost sure" error bounds—rather than just average-case performance—the authors propose sampling from a mixture of optimal leverage score distributions and densities related to specific function spaces (such as Reproducing Kernel Hilbert Spaces).
  4. Independent Repetitions of DPP: A key practical contribution of the paper is the suggestion to take $r$ independent sets of $m$ points from a projection DPP. This "Repeated DPP" approach is computationally more manageable than complex volume sampling and demonstrates excellent stability in practice.

Experimental Framework

The authors evaluated these methods using controlled numerical experiments focusing on polynomial approximation. They tested the methods on the interval $[-1, 1]$ with a uniform measure and on the real line $\mathbb{R}$ with a Gaussian measure. A primary target was the Runge-like function $f(x) = (1 + 2x^2)^{-1}$, which is notoriously difficult to approximate due to its behavior near the poles.

Key Insights and Results

Repulsion and Stability

The core insight is that by forcing points to be diverse via DPPs, one directly controls the eigenvalues of the Gram matrix. This prevents the matrix from becoming unstable, which is the primary driver of high error in least-squares approximations. Numerical results indicate that for repeated DPP sampling, the stability condition is satisfied with a much lower number of samples compared to standard i.i.d. leverage score sampling.

Performance in Small Oversampling Regimes

When the number of samples $n$ is only slightly larger than the dimension $m$ (e.g., $n=2m$), the repeated DPP method significantly outperforms both volume-rescaled and i.i.d. sampling. This holds true for both the expected error and the "worst-case" (95th percentile) error, making it a robust choice for resource-constrained scenarios.

Theoretical Convergence and Unbiasedness

Volume-rescaled sampling produces an unbiased estimator of the best possible approximation. The authors provide a generalized version of this sampling that achieves quasi-optimality in expectation with $n = O(m \log m)$ samples, matching the best-known theoretical rates while offering potentially better constants.

Limitations and Future Directions

While promising, the computational complexity of sampling from a DPP remains a hurdle. For a discrete set of $N$ possible points, the cost is $O(m^3 + Nm^2)$. Although faster algorithms exist, scaling these techniques to very high-dimensional problems remains a challenge. Additionally, some of the strongest results for the "Repeated DPP" strategy currently rely on a mathematical conjecture regarding eigenvalue concentration. While numerical evidence is compelling, a formal proof is still required. Future work will likely focus on extending these dependent sampling techniques to high-dimensional manifolds and large-scale machine learning applications.

Summary updated

Abstract

We consider the problem of approximating a function from $L^2$ by an element of a given $m$-dimensional space $V_m$, associated with some feature map $\boldsymbolφ$, using evaluations of the function at random points $x_1, \dots,x_n$. After recalling some results on optimal weighted least-squares using independent and identically distributed points, we consider weighted least-squares using projection determinantal point processes (DPP) or volume sampling. These distributions introduce dependence between the points that promotes diversity in the selected features $\boldsymbolφ(x_i)$. We first provide a generalized version of volume-rescaled sampling yielding quasi-optimality results in expectation with a number of samples $n = O(m\log(m))$, that means that the expected $L^2$ error is bounded by a constant times the best approximation error in $L^2$. Also, further assuming that the function is in some normed vector space $H$ continuously embedded in $L^2$, we further prove that the approximation error in $L^2$ is almost surely bounded by the best approximation error measured in the $H$-norm. This includes the cases of functions from $L^\infty$ or reproducing kernel Hilbert spaces. Finally, we present an alternative strategy consisting in using independent repetitions of projection DPP (or volume sampling), yielding similar error bounds as with i.i.d. or volume sampling, but in practice with a much lower number of samples. Numerical experiments illustrate the performance of the different strategies.
BibTeX
@misc{nouy2023weighted,
  author = {Anthony Nouy and Bertrand Michel},
  title = {{Weighted least-squares approximation with determinantal point processes and generalized volume sampling}},
  year = {2023},
  eprint = {2312.14057},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.14057},
}
Figure