Exact sampling of determinantal point processes without eigendecomposition
From MaRDI portal
Abstract: Determinantal point processes (DPPs) enable the modeling of repulsion: they provide diverse sets of points. The repulsion is encoded in a kernel 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 . The exact algorithm to sample DPPs uses the spectral decomposition of , 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.
Recommendations
- High-performance sampling of generic determinantal point processes
- Determinantal point processes in randomized numerical linear algebra
- On simulation of continuous determinantal point processes
- Determinantal point processes
- Determinantal Point Processes
- A survey on determinantal point processes
- A heuristic independent particle approximation to determinantal point processes
- Exact sampling with highly uniform point sets
- Monte Carlo with determinantal point processes
- On a few statistical applications of determinantal point processes
Cites work
- A Review of Image Denoising Algorithms, with a New One
- An Introduction to Numerical Analysis
- Asymptotic equivalence of fixed-size and varying-size determinantal point processes
- Determinantal point process models and statistical inference
- Determinantal point processes for machine learning
- Determinantal processes and independence
- Eynard-Mehta theorem, Schur process, and their Pfaffian analogs
- High-performance sampling of generic determinantal point processes
- How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 7164768 (Why is no real title available?)
- On a few statistical applications of determinantal point processes
- On the foundations of combinatorial theory I. Theory of M�bius Functions
- Parallel Cholesky factorization on a shared-memory multiprocessor
- Pattern theory. The stochastic analysis of real-world signals.
- Random point fields associated with certain Fredholm determinants. I: Fermion, Poisson and Boson point processes.
- Statistical Ensembles of Complex, Quaternion, and Real Matrices
- Stochastic geometry and its applications
- Stochastic ordering and thinning of point processes
- Two applications of random spanning forests
Cited in
(14)- A heuristic independent particle approximation to determinantal point processes
- Nyström landmark sampling and regularized Christoffel functions
- Determinantal point processes for machine learning
- scientific article; zbMATH DE number 5375044 (Why is no real title available?)
- High-performance sampling of generic determinantal point processes
- A note related to the CS decomposition and the BK inequality for discrete determinantal processes
- On simulation of continuous determinantal point processes
- On sampling determinantal and Pfaffian point processes on a quantum computer
- Probabilistic cellular automata modelling of intercellular interactions in airways: complex pattern formation in patients with chronic obstructive pulmonary disease
- Deterministic sampling based on Kullback-Leibler divergence and its applications
- The cosine-sine decomposition and conditional negative correlation inequalities for determinantal processes
- Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
- A note on the exact simulation of a random eigenvalue of a \textsc{gue} matrix
- On determinantal point processes with nonsymmetric kernels
This page was built for publication: Exact sampling of determinantal point processes without eigendecomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5139925)
