Claire Launay

Postdoctoral researcher - Albert Einstein College of Medicine

Exact Sampling of Determinantal Point Processes without Eigendecomposition

Claire Launay, Bruno Galerne, Agnès Desolneux

The repulsion of a DPP is encoded in its 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. We present an alternative exact algorithm in the discrete setting that avoids the eigenvalues and the eigenvectors computation. Instead, it relies on the Cholesky decomposition of the matrix K. 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.

Paper

This sequential thinning algorithm is presented in the paper "Exact Sampling of Determinantal Point Processes without Eigendecomposition" (C.L., Bruno Galerne, Agnès Desolneux), published in December 2020 in Journal of Applied Probability, Volume 57 / Issue 4 which is available here.

Source codes (Python and Matlab)

The following files contain a matlab source code and a python source code to apply the sequential thinning algorithm: If you have any question or if you find some bugs in these codes, don't hesitate to send me an email, we will be happy to answer them.