# Spectral Certificates and Projection-DPP Rounding for Determinantal MAP Selection

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 23 references that are in the map.
- First posted on arXiv 17 Jun 2026.

## Builds on (most cited first, 8 of 8)

- [Faster Greedy MAP Inference for Determinantal Point Processes](https://mlsanity.com/paper/1703.03389/) (2017)
- [Fast determinantal point processes via distortion-free intermediate sampling](https://mlsanity.com/paper/1811.03717/) (2018)
- [Randomized Rounding for the Largest Simplex Problem](https://mlsanity.com/paper/1412.0036/) (2014)
- [A determinantal point process for column subset selection](https://mlsanity.com/paper/1812.09771/) (2018)
- [Approximation Algorithms for D-optimal Design](https://mlsanity.com/paper/1802.08372/) (2018)
- [A Faster Sampler for Discrete Determinantal Point Processes](https://mlsanity.com/paper/2210.17358/) (2022)
- [Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes](https://mlsanity.com/paper/2109.00727/) (2021)
- [Zonotope hit-and-run for efficient sampling from projection DPPs](https://mlsanity.com/paper/1705.10498/) (2017)

## Abstract (arXiv)

Selecting a fixed-size subset that maximizes the determinant of a positive semidefinite kernel is the MAP problem for a size-constrained determinantal point process and the classical maximum-entropy sampling problem. Although this discrete problem is NP-hard, a classical spectral bound gives an efficiently computable ceiling using the leading eigenvalues. The same ceiling is the exact optimum of the associated Stiefel relaxation, so the continuous problem is already solved by the leading eigenspace. We study what this eigenspace implies for discrete rounding. The leading eigenvectors induce a projection determinantal point process whose probability for a subset equals its squared coordinate volume. We prove that the gap between the determinant of any subset and the spectral ceiling is at most its negative log-probability under this distribution. Consequently, the integrality gap is bounded by the min-entropy and equals it when the kernel rank matches the subset size. Projection-DPP rounding also has an expected gap bounded by the Shannon entropy and admits a high-probability additive guarantee. These results identify leading-subspace localization, rather than eigenvalue decay alone, as the geometry controlling roundability. This analysis yields CertDPP, a matrix-free pipeline that computes the leading eigenspace, draws projection-DPP samples, optionally improves them by determinant-increasing swaps, and reports the gap from a verified spectral ceiling. Controlled experiments validate the entropy identities, compare with exact MAP on small instances, and demonstrate linear scaling in the ground-set size for the rounding stage.