Kronecker Determinantal Point Processes
This work addresses scalability issues in DPPs for applications requiring diverse subset selection, though it is incremental as it builds on existing DPP frameworks.
The authors tackled the computational inefficiency of Determinantal Point Processes (DPPs) for large-scale problems by introducing KronDPP, a model with a Kronecker product kernel structure, enabling fast exact sampling and efficient learning algorithms.
Determinantal Point Processes (DPPs) are probabilistic models over all subsets a ground set of $N$ items. They have recently gained prominence in several applications that rely on "diverse" subsets. However, their applicability to large problems is still limited due to the $\mathcal O(N^3)$ complexity of core tasks such as sampling and learning. We enable efficient sampling and learning for DPPs by introducing KronDPP, a DPP model whose kernel matrix decomposes as a tensor product of multiple smaller kernel matrices. This decomposition immediately enables fast exact sampling. But contrary to what one may expect, leveraging the Kronecker product structure for speeding up DPP learning turns out to be more difficult. We overcome this challenge, and derive batch and stochastic optimization algorithms for efficiently learning the parameters of a KronDPP.