Reviews: Exact sampling of determinantal point processes with sublinear time preprocessing

Review of "Exact sampling of determinantal point processes with sublinear time preprocessing." Summary: the paper proposes a new algorithm for exact sampling from determinantal point processes (DPP). A DPP sampling problem involves an n x n matrix L; the probability of selecting some subset S of k n indices is given by the determinant of a k x k matrix subset divided by the determinant of L I. The proposed algorithm has preprocessing which is sublinear in matrix size n and polynomial in subset size k; sampling is polynomial in k and independent of n. Previous algorithms which require eigen-decomposition or MCMC are O(n 3). The main idea is to downsample the index set using a regularzed DPP and then run a DPP on this downsample.