# Exact Sampling of Determinantal Point Processes without Eigendecomposition

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2018.

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

- [A Faster Sampler for Discrete Determinantal Point Processes](https://mlsanity.com/paper/2210.17358/) (2022)
- [Lazy and Fast Greedy MAP Inference for Determinantal Point Process](https://mlsanity.com/paper/2206.05947/) (2022)
- [Hardness of Maximum Likelihood Learning of DPPs](https://mlsanity.com/paper/2205.12377/) (2022)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [A simple estimator of the correlation kernel matrix of a determinantal point process](https://mlsanity.com/paper/2505.14529/) (2025)
- [On two ways to use determinantal point processes for Monte Carlo integration](https://mlsanity.com/paper/2604.19698/) (2026)
- [Ensemble Diversity Optimization for Subjective Supervision](https://mlsanity.com/paper/2607.08493/) (2026)

## Abstract (arXiv)

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.