# Fast determinantal point processes via distortion-free intermediate sampling

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

## Key facts

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

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

- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs](https://mlsanity.com/paper/2206.10291/) (2022)
- [Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2207.00486/) (2022)
- [RD-DPP: Rate-Distortion Theory Meets Determinantal Point Process to Diversify Learning Data Samples](https://mlsanity.com/paper/2304.04137/) (2023)
- [FedSSO: A Federated Server-Side Second-Order Optimization Algorithm](https://mlsanity.com/paper/2206.09576/) (2022)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [Learning on Bandwidth Constrained Multi-Source Data with MIMO-inspired DPP MAP Inference](https://mlsanity.com/paper/2306.02497/) (2023)
- [On two ways to use determinantal point processes for Monte Carlo integration](https://mlsanity.com/paper/2604.19698/) (2026)
- [Spectral Certificates and Projection-DPP Rounding for Determinantal MAP Selection](https://mlsanity.com/paper/2606.19411/) (2026)

## Abstract (arXiv)

Given a fixed n× d matrix X, where ngg d, we study the complexity of sampling from a distribution over all subsets of rows where the probability of a subset is proportional to the squared volume of the parallelepiped spanned by the rows (a.k.a. a determinantal point process). In this task, it is important to minimize the preprocessing cost of the procedure (performed once) as well as the sampling cost (performed repeatedly). To that end, we propose a new determinantal point process algorithm which has the following two properties, both of which are novel: (1) a preprocessing step which runs in time O(number-of-non-zeros(X)·log n)+poly(d), and (2) a sampling step which runs in poly(d) time, independent of the number of rows n. We achieve this by introducing a new regularized determinantal point process (R-DPP), which serves as an intermediate distribution in the sampling procedure by reducing the number of rows from n to poly(d). Crucially, this intermediate distribution does not distort the probabilities of the target sample. Our key novelty in defining the R-DPP is the use of a Poisson random variable for controlling the probabilities of different subset sizes, leading to new determinantal formulas such as the normalization constant for this distribution. Our algorithm has applications in many diverse areas where determinantal point processes have been used, such as machine learning, stochastic optimization, data summarization and low-rank matrix reconstruction.