# Signal reconstruction using determinantal sampling

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 90 references that are in the map.
- First posted on arXiv 13 Oct 2023.

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

- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Kernel quadrature with DPPs](https://mlsanity.com/paper/1906.07832/) (2019)
- [Monte Carlo with Determinantal Point Processes](https://mlsanity.com/paper/1605.00361/) (2016)
- [Kernel interpolation with continuous volume sampling](https://mlsanity.com/paper/2002.09677/) (2020)
- [A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms](https://mlsanity.com/paper/1812.08723/) (2018)
- [Relating Leverage Scores and Density using Regularized Christoffel Functions](https://mlsanity.com/paper/1805.07943/) (2018)

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

- [Optimal sampling for least-squares approximation](https://mlsanity.com/paper/2409.02342/) (2024)
- [Weighted least-squares approximation with determinantal point processes and generalized volume sampling](https://mlsanity.com/paper/2312.14057/) (2023)

## Abstract (arXiv)

We study the approximation of a square-integrable function from a finite number of evaluations on a random set of nodes according to a well-chosen distribution. This is particularly relevant when the function is assumed to belong to a reproducing kernel Hilbert space (RKHS). This work proposes to combine several natural finite-dimensional approximations based two possible probability distributions of nodes. These distributions are related to determinantal point processes, and use the kernel of the RKHS to favor RKHS-adapted regularity in the random design. While previous work on determinantal sampling relied on the RKHS norm, we prove mean-square guarantees in L2 norm. We show that determinantal point processes and mixtures thereof can yield fast convergence rates. Our results also shed light on how the rate changes as more smoothness is assumed, a phenomenon known as superconvergence. Besides, determinantal sampling generalizes i.i.d. sampling from the Christoffel function which is standard in the literature. More importantly, determinantal sampling guarantees the so-called instance optimality property for a smaller number of function evaluations than i.i.d. sampling.