Determinantal sampling on general spaces: fast approximation via diffusion geometry
Abstract
Determinantal point processes (DPPs) have recently emerged as a kernel-based alternative to standard independent sampling for constructing efficient minibatches, coresets, and other compact representations of large-scale datasets. One of the key strengths of DPP based samplers is that they can be deployed over very general spaces, in contrast to more classical sampling methods beyond i.i.d. which tend to be tailored to particular well-structured settings, principally Euclidean spaces. In this work, we establish explicit rate guarantees for determinantal sampling in spaces that extend far beyond known Euclidean setups, focussing on spectral kernels obtained from eigenspaces of naturally associated Markov diffusion operators, including in particular the Laplacian on manifolds and nearest-neighbour type graphs on data point clouds and the discrete Schrodinger operator on large scale networks. This covers, in particular, the settings of Riemannian manifolds and discrete networks, as well as the problem of batch sampling from discrete datasets. Overall, our approach achieves guarantees comparable to (sample size)−1/2−1/2dint , which match with the rates for well-known determinantal samplers on Euclidean spaces of comparable dimension. In terms of techniques, we connect to the celebrated Weyl's Law for spectra on general spaces, and leverage tools from the theory of Markov diffusion operators and Dirichlet forms, which could be of independent interest in this area. Our approach is applicable to a very wide plethora of ambient spaces beyond Euclidean as soon as these ingredients are available, including e.g. fractals, leading to guarantees that will be governed by the intrinsic structural constants of such spaces.
Related
- Fluid and Diffusion Approximation of a Multiclass Proportional Processor Sharing Queue with Reneging and General Distributions
- Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling
- Geometry of some determinantal arrangements
- Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling
- General Frequency Principle for Linear Approximation Classes
BibTeX
@misc{tran2026determinantal,
title = {{Determinantal sampling on general spaces: fast approximation via diffusion geometry}},
author = {Hoang-Son Tran and Pranav Gupta and Subhroshekhar Ghosh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.06644},
eprint = {2607.06644},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.06644},
}
RIS
TY - UNPB
TI - Determinantal sampling on general spaces: fast approximation via diffusion geometry
AU - Hoang-Son Tran
AU - Pranav Gupta
AU - Subhroshekhar Ghosh
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2607.06644
UR - https://arxiv.org/abs/2607.06644
AB - Determinantal point processes (DPPs) have recently emerged as a kernel-based alternative to standard independent sampling for constructing efficient minibatches, coresets, and other compact representations of large-scale datasets. One of the key strengths of DPP based samplers is that they can be deployed over very general spaces, in contrast to more classical sampling methods beyond i.i.d. which tend to be tailored to particular well-structured settings, principally Euclidean spaces. In this work, we establish explicit rate guarantees for determinantal sampling in spaces that extend far beyond known Euclidean setups, focussing on spectral kernels obtained from eigenspaces of naturally associated Markov diffusion operators, including in particular the Laplacian on manifolds and nearest-neighbour type graphs on data point clouds and the discrete Schrodinger operator on large scale networks. This covers, in particular, the settings of Riemannian manifolds and discrete networks, as well as the problem of batch sampling from discrete datasets. Overall, our approach achieves guarantees comparable to (sample size)^−1/2−1/2d_int , which match with the rates for well-known determinantal samplers on Euclidean spaces of comparable dimension. In terms of techniques, we connect to the celebrated Weyl's Law for spectra on general spaces, and leverage tools from the theory of Markov diffusion operators and Dirichlet forms, which could be of independent interest in this area. Our approach is applicable to a very wide plethora of ambient spaces beyond Euclidean as soon as these ingredients are available, including e.g. fractals, leading to guarantees that will be governed by the intrinsic structural constants of such spaces.
ER -