Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition

DOI10.1137/23M1545537arXiv2208.09585MaRDI QIDQ6202283

Elizaveta Rebrova, Michał Dereziński

Publication date: 26 March 2024

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

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

zbMATH Keywords

spectral analysisrandomized singular value decompositionrandomized Kaczmarzrandomized Newtonstochastic iterative methodssketch-and-project

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Iterative numerical methods for linear systems (65F10) Randomized algorithms (68W20)

Related Items (3)

A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation ⋮ Randomized Kaczmarz with geometrically smoothed momentum ⋮ Solving, tracking and stopping streaming linear inverse problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Two-subspace projection method for coherent overdetermined systems
• Hanson-Wright inequality and sub-Gaussian concentration
• Block Kaczmarz method with inequalities
• A randomized Kaczmarz algorithm with exponential convergence
• On the empirical distribution of eigenvalues of a class of large dimensional random matrices
• On the mean and variance of the generalized inverse of a singular Wishart matrix
• On block Gaussian sketching for the Kaczmarz method
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Low-Rank Approximation and Regression in Input Sparsity Time
• A Randomized Coordinate Descent Method with Volume Sampling
• Randomized Iterative Methods for Linear Systems
• A Hilbert Space Embedding for Distributions
• Kernel Mean Embedding of Distributions: A Review and Beyond
• Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms
• High-Dimensional Probability
• Randomized Kaczmarz Converges Along Small Singular Vectors
• On Adaptive Sketch-and-Project for Solving Linear Systems
• Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
• Randomized sketch descent methods for non-separable linearly constrained optimization
• Sketched Newton--Raphson
• Determinantal Point Processes in Randomized Numerical Linear Algebra
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions
• A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
• The Relaxation Method for Linear Inequalities
• Randomized numerical linear algebra: Foundations and algorithms

This page was built for publication: Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition