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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 34 references that are in the map.
- First posted on arXiv 21 Dec 2023.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Kernel interpolation with continuous volume sampling](https://mlsanity.com/paper/2002.09677/) (2020)
- [Unbiased estimators for random design regression](https://mlsanity.com/paper/1907.03411/) (2019)
- [A Faster Sampler for Discrete Determinantal Point Processes](https://mlsanity.com/paper/2210.17358/) (2022)
- [Efficient Rectangular Maximal-Volume Algorithm for Rating Elicitation in Collaborative Filtering](https://mlsanity.com/paper/1610.04850/) (2016)
- [Signal reconstruction using determinantal sampling](https://mlsanity.com/paper/2310.09437/) (2023)

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

- [Optimal sampling for least-squares approximation](https://mlsanity.com/paper/2409.02342/) (2024)
- [Natural gradient descent with momentum](https://mlsanity.com/paper/2604.15554/) (2026)

## Abstract (arXiv)

We consider the problem of approximating a function from L2 by an element of a given m-dimensional space Vm, associated with some feature map boldsymbolvarphi, using evaluations of the function at random points x1, dots,xn. 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 boldsymbolvarphi(xi). We first provide a generalized version of volume-rescaled sampling yielding quasi-optimality results in expectation with a number of samples n = O(mlog(m)), that means that the expected L2 error is bounded by a constant times the best approximation error in L2. Also, further assuming that the function is in some normed vector space H continuously embedded in L2, we further prove that the approximation error in L2 is almost surely bounded by the best approximation error measured in the H-norm. This includes the cases of functions from L^∞ 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.