Signal reconstruction using determinantal sampling

Abstract

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 $L^2$ 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.

References in corpus (15)

• Determinantal Processes and Independence
• Kernel Mean Embedding of Distributions: A Review and Beyond
• Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks
• Breaking the Curse of Dimensionality with Convex Neural Networks
• Determinantal point process models and statistical inference : Extended version
• Random matrices and determinantal processes
• Coherence Motivated Sampling and Convergence Analysis of Least-Squares Polynomial Chaos Regression
• Marcinkiewicz-Zygmund inequalities
• Optimal pointwise sampling for $L^2$ approximation
• Determinantal Probability: Basic Properties and Conjectures
• On two ways to use determinantal point processes for Monte Carlo integration
• Detailed analysis of prolate quadratures and interpolation formulas
• Kernel interpolation with continuous volume sampling
• On the mean projection theorem for determinantal point processes
• Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling