Spectral Certificates and Projection-DPP Rounding for Determinantal MAP Selection

Excerpt

arXiv:2606.19411v3 Announce Type: replace Abstract: 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 continu