High-performance sampling of generic determinantal point processes
From MaRDI portal
Abstract: Determinantal Point Processes (DPPs) were introduced by Macchi as a model for repulsive (fermionic) particle distributions. But their recent popularization is largely due to their usefulness for encouraging diversity in the final stage of a recommender system. The standard sampling scheme for finite DPPs is a spectral decomposition followed by an equivalent of a randomly diagonally-pivoted Cholesky factorization of an orthogonal projection, which is only applicable to Hermitian kernels and has an expensive setup cost. Researchers have begun to connect DPP sampling to factorizations as a means of avoiding the initial spectral decomposition, but existing approaches have only outperformed the spectral decomposition approach in special circumstances, where the number of kept modes is a small percentage of the ground set size. This article proves that trivial modifications of and factorizations yield efficient direct sampling schemes for non-Hermitian and Hermitian DPP kernels, respectively. Further, it is experimentally shown that even dynamically-scheduled, shared-memory parallelizations of high-performance dense and sparse-direct factorizations can be trivially modified to yield DPP sampling schemes with essentially identical performance. The software developed as part of this research, Catamari, https://hodgestar.com/catamari, is released under the Mozilla Public License v2.0. It contains header-only, C++14 plus OpenMP 4.0 implementations of dense and sparse-direct, Hermitian and non-Hermitian DPP samplers.
Recommendations
- Determinantal point processes for machine learning
- Exact sampling of determinantal point processes without eigendecomposition
- On the complexity of constrained determinantal point processes
- On simulation of continuous determinantal point processes
- A heuristic independent particle approximation to determinantal point processes
Cites work
- A framework for symmetric band reduction
- A New Implementation of Sparse Gaussian Elimination
- A set of level 3 basic linear algebra subprograms
- Algorithm 539: Basic Linear Algebra Subprograms for Fortran Usage [F1]
- An extended set of FORTRAN basic linear algebra subprograms
- Asymptotic domino statistics in the Aztec diamond
- Determinantal point processes for machine learning
- Determinantal processes and independence
- Determinantal processes with number variance saturation
- Determinantal random point fields
- Dimer problem in statistical mechanics-an exact result
- HOPDM - a higher order primal-dual method for large scale linear programming
- scientific article; zbMATH DE number 3642435 (Why is no real title available?)
- scientific article; zbMATH DE number 4189084 (Why is no real title available?)
- Immanants and finite point processes
- Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances
- Multiple centrality corrections in a primal-dual method for linear programming
- New parallel sparse direct solvers for multicore architectures
- On the density of Eigenvalues of a random matrix
- Patterns in eigenvalues: the 70th Josiah Willard Gibbs lecture
- Random matrix theory
- Some Properties of Symmetric Quasi-Definite Matrices
- Statistical Ensembles of Complex, Quaternion, and Real Matrices
- Statistical Theory of the Energy Levels of Complex Systems. I
- Symmetric Quasidefinite Matrices
- The coincidence approach to stochastic point processes
- The design and implementation of the MRRR algorithm
- The influence of relaxed supernode partitions on the multifrontal method
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
- Toward an Efficient Parallel Eigensolver for Dense Symmetric Matrices
- Uniform spanning forests
Cited in
(17)- Fixed-size determinantal point processes sampling for species phylogeny
- A heuristic independent particle approximation to determinantal point processes
- Nyström landmark sampling and regularized Christoffel functions
- Determinantal point processes for machine learning
- scientific article; zbMATH DE number 5375044 (Why is no real title available?)
- On the complexity of constrained determinantal point processes
- Exact sampling of determinantal point processes without eigendecomposition
- scientific article; zbMATH DE number 7164768 (Why is no real title available?)
- catamari
- On simulation of continuous determinantal point processes
- Extended L-ensembles: a new representation for determinantal point processes
- On sampling determinantal and Pfaffian point processes on a quantum computer
- Recovering a magnitude-symmetric matrix from its principal minors
- Optimal sublinear sampling of spanning trees and determinantal point processes via average-case entropic independence
- Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
- Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
- On determinantal point processes with nonsymmetric kernels
This page was built for publication: High-performance sampling of generic determinantal point processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993509)
