A Polynomial Time MCMC Method for Sampling from Continuous DPPs
This provides an efficient algorithm for sampling from continuous DPPs, which is incremental as it builds on existing Gibbs sampling methods but improves computational complexity.
The paper tackles the problem of sampling from continuous determinantal point processes (DPPs) by showing that Gibbs sampling with a warm start requires only polynomial steps in k, and applies this to sample from spherical Gaussian kernel DPPs on the unit sphere in polynomial time in k and d.
We study the Gibbs sampling algorithm for continuous determinantal point processes. We show that, given a warm start, the Gibbs sampler generates a random sample from a continuous $k$-DPP defined on a $d$-dimensional domain by only taking $\text{poly}(k)$ number of steps. As an application, we design an algorithm to generate random samples from $k$-DPPs defined by a spherical Gaussian kernel on a unit sphere in $d$-dimensions, $\mathbb{S}^{d-1}$ in time polynomial in $k,d$.