Randomized Nyström Preconditioning
From MaRDI portal
Abstract: This paper introduces the Nystr"om PCG algorithm for solving a symmetric positive-definite linear system. The algorithm applies the randomized Nystr"om method to form a low-rank approximation of the matrix, which leads to an efficient preconditioner that can be deployed with the conjugate gradient algorithm. Theoretical analysis shows that preconditioned system has constant condition number as soon as the rank of the approximation is comparable with the number of effective degrees of freedom in the matrix. The paper also develops adaptive methods that provably achieve similar performance without knowledge of the effective dimension. Numerical tests show that Nystr"om PCG can rapidly solve large linear systems that arise in data analysis problems, and it surpasses several competing methods from the literature.
Recommendations
- Two-level Nyström-Schur preconditioner for sparse symmetric positive definite matrices
- Randomized algorithms in numerical linear algebra
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Additive preconditioning for matrix computations
- Revisiting the Nyström method for improved large-scale machine learning
Cites work
- A block conjugate gradient method applied to linear systems with multiple right-hand sides
- A fast randomized algorithm for overdetermined linear least-squares regression
- A Scalable Estimate of the Out-of-Sample Prediction Error via Approximate Leave-One-Out Cross-Validation
- Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds
- Algorithm 971
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Fast approximation of matrix coherence and statistical leverage
- Faster kernel ridge regression using sketching and preconditioning
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- LSRN: A parallel iterative solver for strongly over- or underdetermined systems
- On the Sensitivity of Some Spectral Preconditioners
- Optimal Approximate Matrix Product in Terms of Stable Rank
- Practical sketching algorithms for low-rank matrix approximation
- Randomized numerical linear algebra: Foundations and algorithms
- Revisiting the Nyström method for improved large-scale machine learning
- Sketching as a tool for numerical linear algebra
- Support Vector Machines
- The block conjugate gradient algorithm and related methods
Cited in
(25)- Preconditioned Krylov subspace methods for sampling multivariate Gaussian distributions
- Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
- Two-level Nyström-Schur preconditioner for sparse symmetric positive definite matrices
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- Preconditioner design via Bregman divergences
- An adaptive factorized Nyström preconditioner for regularized kernel matrices
- Single-pass Nyström approximation in mixed precision
- Efficient bounds and estimates for canonical angles in randomized subspace approximations
- SketchySGD: reliable stochastic optimization via randomized curvature estimates
- Randomized Nyström preconditioned interior point-proximal method of multipliers
- Randomized Kaczmarz methods with beyond-Krylov convergence
- Embrace rejection: kernel matrix approximation by accelerated randomly pivoted Cholesky
- A gradient-based and determinant-free framework for fully Bayesian Gaussian process regression
- Efficient nonlocal linear image denoising: bilevel optimization with nonequispaced fast Fourier transform and matrix-free preconditioning
- Randomized algorithm for constrained quaternion singular value decomposition and its applications
- Randomized Nyström approximation of non-negative self-adjoint operators
- A generalized Nyström method with subspace iteration for low-rank approximations of large-scale nonsymmetric matrices
- Preconditioning without a preconditioner using randomized block Krylov subspace methods
- Scalable approximate optimal diagonal preconditioning
- A new analysis of the randomly pivoted Cholesky algorithm
- A preconditioned iteration method for solving saddle point problems
- Stable algorithms for general linear systems by preconditioning the normal equations
- Connecting Kaporin's condition number and the Bregman log determinant divergence
- Stochastic trace estimation for parameter-dependent matrices applied to spectral density approximation
- Robust, randomized preconditioning for kernel ridge regression
This page was built for publication: Randomized Nyström Preconditioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166051)
