Determinantal point processes in randomized numerical linear algebra
From MaRDI portal
Publication:5149289
Abstract: Randomized Numerical Linear Algebra (RandNLA) uses randomness to develop improved algorithms for matrix problems that arise in scientific computing, data science, machine learning, etc. Determinantal Point Processes (DPPs), a seemingly unrelated topic in pure and applied mathematics, is a class of stochastic point processes with probability distribution characterized by sub-determinants of a kernel matrix. Recent work has uncovered deep and fruitful connections between DPPs and RandNLA which lead to new guarantees and improved algorithms that are of interest to both areas. We provide an overview of this exciting new line of research, including brief introductions to RandNLA and DPPs, as well as applications of DPPs to classical linear algebra tasks such as least squares regression, low-rank approximation and the Nystr"om method. For example, random sampling with a DPP leads to new kinds of unbiased estimators for least squares, enabling more refined statistical and inferential understanding of these algorithms; a DPP is, in some sense, an optimal randomized algorithm for the Nystr"om method; and a RandNLA technique called leverage score sampling can be derived as the marginal distribution of a DPP. We also discuss recent algorithmic developments, illustrating that, while not quite as efficient as standard RandNLA techniques, DPP-based algorithms are only moderately more expensive.
Recommendations
Cited in
(30)- On proportional volume sampling for experimental design in general spaces
- Random projections of linear and semidefinite problems with linear inequalities
- Determinantal random point fields
- Communication-efficient distributed covariance sketch, with application to distributed PCA
- Convexification with bounded gap for randomly projected quadratic optimization
- Exact sampling of determinantal point processes without eigendecomposition
- scientific article; zbMATH DE number 7164768 (Why is no real title available?)
- Determinantal Point Processes Implicitly Regularize Semiparametric Regression Problems
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Randomized Quasi-Optimal Local Approximation Spaces in Time
- Extended L-ensembles: a new representation for determinantal point processes
- On sampling determinantal and Pfaffian point processes on a quantum computer
- On the mean projection theorem for determinantal point processes
- Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
- Energy-based sequential sampling for low-rank PSD-matrix approximation
- Randomized Kaczmarz methods with beyond-Krylov convergence
- Estimating a matrix's singular values with interpolative decompositions
- Optimal sublinear sampling of spanning trees and determinantal point processes via average-case entropic independence
- Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
- Random multitype spanning forests for synchronization on sparse graphs
- CholeskyQR with randomization and pivoting for tall matrices (CQRRPT)
- Low-rank approximation of parameter-dependent matrices via CUR decomposition
- Surrogate-based autotuning for randomized sketching algorithms in regression problems
- Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
- Accuracy and stability of CUR decompositions with oversampling
- Accelerating the Canonical Polyadic Alternating Least Squares Optimization via a Randomized Interpolative Decomposition
- Entry growth in Gaussian elimination
- A new analysis of the randomly pivoted Cholesky algorithm
- Subspace-constrained randomized coordinate descent for linear systems with good low-rank matrix approximations
- Error Analysis and Precision Selection for Mixed-Precision DEIM-CUR Decompositions
This page was built for publication: Determinantal point processes in randomized numerical linear algebra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5149289)
