Using The Matrix Ridge Approximation to Speedup Determinantal Point Processes Sampling Algorithms

Shusen Wang, Chao Zhang, Hui Qian, Zhihua ZhangAAAI 2014 · OpenReview

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$).

Performance comparison of MRA-DPP against baseline methods across different kernel 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

Abstract

Determinantal point process (DPP) is an important probabilistic model that has extensive applications in artificial intelligence. The exact sampling algorithm of DPP requires the full eigenvalue decomposition of the kernel matrix which has high time and space complexities. This prohibits the applications of DPP from large-scale datasets. Previous work has applied the Nystrom method to speedup the sampling algorithm of DPP, and error bounds have been established for the approximation. In this paper we employ the matrix ridge approximation (MRA) to speedup the sampling algorithm of DPP, showing that our approach MRA-DPP has stronger error bound than the Nystrom-DPP. In certain circumstances our MRA-DPP is provably exact, whereas the Nystrom-DPP is far from the ground truth. Finally, experiments on several real-world datasets show that our MRA-DPP is more accurate than the other approximation approaches.
BibTeX
@inproceedings{wang2014using,
  author = {Shusen Wang and Chao Zhang and Hui Qian and Zhihua Zhang},
  title = {{Using The Matrix Ridge Approximation to Speedup Determinantal Point Processes Sampling Algorithms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  url = {https://openreview.net/forum?id=HJbO91b_WH},
}
Figure