Exact Sampling of Determinantal Point Processes without Eigendecomposition

Abstract

Determinantal point processes (DPPs) enable the modeling of repulsion: they provide diverse sets of points. The repulsion is encoded in a kernel $K$ that can be seen as a matrix storing the similarity between points. The diversity comes from the fact that the inclusion probability of a subset is equal to the determinant of a submatrice of $K$. The exact algorithm to sample DPPs uses the spectral decomposition of $K$, a computation that becomes costly when dealing with a high number of points. Here, we present an alternative exact algorithm in the discrete setting that avoids the eigenvalues and the eigenvectors computation. Instead, it relies on Cholesky decompositions. This is a two steps strategy: first, it samples a Bernoulli point process with an appropriate distribution, then it samples the target DPP distribution through a thinning procedure. Not only is the method used here innovative, but this algorithm can be competitive with the original algorithm or even faster for some applications specified here.

arXiv commentLast update: Correction of typos and journal reference

References in corpus (16)

• Determinantal point processes for machine learning
• Determinantal Processes and Independence
• Eynard-Mehta theorem, Schur process, and their pfaffian analogs
• Determinantal point process models and statistical inference : Extended version
• Statistical properties of determinantal point processes in high-dimensional Euclidean spaces
• Efficient Sampling for k-Determinantal Point Processes
• Exact Sampling of Determinantal Point Processes without Eigendecomposition
• High-performance sampling of generic Determinantal Point Processes
• Optimized Algorithms to Sample Determinantal Point Processes
• Determinantal Point Processes for Mini-Batch Diversification
• Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes
• Exact sampling of determinantal point processes with sublinear time preprocessing
• Learning Determinantal Point Processes in Sublinear Time
• Zonotope hit-and-run for efficient sampling from projection DPPs
• Rates of estimation for determinantal point processes
• Fast Mixing Markov Chains for Strongly Rayleigh Measures, DPPs, and Constrained Sampling

Cited by in corpus (4)

• Exact Sampling of Determinantal Point Processes without Eigendecomposition
• The non-stabilizerness of fermionic Gaussian states
• On determinantal point processes with nonsymmetric kernels
• A note on the exact simulation of a random eigenvalue of a GUE matrix