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:
- 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.
- 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.
- 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).
- 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