Randomized Nyström Preconditioning

DOI10.1137/21M1466244zbMath1517.65020arXiv2110.02820OpenAlexW3204947518MaRDI QIDQ6166051

Madeleine Udell, Joel A. Tropp, Unnamed Author

Publication date: 6 July 2023

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2110.02820

zbMATH Keywords

linear systemcross-validationrandomized algorithmkernel methodridge regressionpreconditionerconjugate gradientNyström approximationregularized least-squares

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Preconditioners for iterative methods (65F08) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Related Items (6)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The block conjugate gradient algorithm and related methods
• A block conjugate gradient method applied to linear systems with multiple right-hand sides
• LSRN: A Parallel Iterative Solver for Strongly Over- or Underdetermined Systems
• Computational Advertising: Techniques for Targeting Relevant Ads
• A fast randomized algorithm for overdetermined linear least-squares regression
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Algorithm 971
• Support Vector Machines
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Faster Kernel Ridge Regression Using Sketching and Preconditioning
• Optimal Approximate Matrix Product in Terms of Stable Rank
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• 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
• On the Sensitivity of Some Spectral Preconditioners
• Randomized numerical linear algebra: Foundations and algorithms

This page was built for publication: Randomized Nyström Preconditioning