Introduction
Determinantal Point Processes (DPPs) are powerful probabilistic models for selecting diverse subsets of data, widely used in machine learning for tasks like text summarization and image search. However, exact sampling from a DPP requires a full eigenvalue decomposition of an $n \times n$ kernel matrix, incurring a prohibitive $O(n^3)$ computational cost for large datasets.
The Challenge of Low-Rank Approximation
To mitigate this cost, researchers often employ low-rank approximations like the Nyström method. While effective for many kernel methods, Nyström poses a fundamental conflict for DPPs. DPP sampling is highly sensitive to the "tail" of the kernel matrix's spectrum—the small eigenvalues. Nyström methods typically discard these small eigenvalues, setting them to zero, which leads to significant errors in the resulting probability distribution.
Matrix Ridge Approximation (MRA-DPP)
The proposed MRA-DPP method addresses this by replacing the standard kernel matrix $K$ with a Matrix Ridge Approximation: $$\hat{K} = \hat{A}\hat{A}^T + \hat{\delta}I_n$$ Unlike standard Nyström or SVD, which assume the tail of the spectrum is zero, MRA assumes the tail is flat and approximates it with a "ridge" term, $\hat{\delta}$, calculated as the average of the discarded eigenvalues. This approach preserves the influence of the entire spectrum while maintaining the computational efficiency of low-rank methods.
Experimental Results
The authors evaluated MRA-DPP against Nyström (uniform and adaptive) and truncated SVD across various real-world datasets, including Letters, Wine Quality, and Satimage, using Radial Basis Function (RBF) kernels with varying scaling parameters ($\sigma$).
Key Findings
- Superior Accuracy: MRA-DPP consistently achieved lower $\ell_1$ variational distance compared to baseline methods across all tested datasets.
- Robustness to Slow Spectral Decay: In regimes where data points are highly distinct (small $\sigma$), standard low-rank methods often fail, with error distances approaching 1.0. MRA-DPP remains stable and accurate. For instance, on the Letters dataset with $\sigma=0.2$, MRA maintained an error of approximately 0.2 while Nyström and SVD failed completely.
- Theoretical Guarantees: The authors proved that MRA-DPP provides a strictly tighter error bound than Nyström-DPP, becoming provably exact if all discarded eigenvalues are equal.
Conclusion
MRA-DPP offers a significant advancement in scaling DPP sampling. By accounting for the spectral tail through a simple ridge term, it achieves high-fidelity approximations with a fraction of the cost of exact sampling. Future work includes exploring randomized SVD to further accelerate the EM algorithm used for MRA and testing the method on million-scale datasets.
Summary updated