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

DOI10.1137/23M1545537arXiv2208.09585MaRDI QIDQ6202283FDOQ6202283

Elizaveta Rebrova, Michał Dereziński

Publication date: 26 March 2024

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

Abstract: Sketch-and-project is a framework which unifies many known iterative methods for solving linear systems and their variants, as well as further extensions to non-linear optimization problems. It includes popular methods such as randomized Kaczmarz, coordinate descent, variants of the Newton method in convex optimization, and others. In this paper, we obtain sharp guarantees for the convergence rate of sketch-and-project methods via new tight spectral bounds for the expected sketched projection matrix. Our estimates reveal a connection between the sketch-and-project convergence rate and the approximation error of another well-known but seemingly unrelated family of algorithms, which use sketching to accelerate popular matrix factorizations such as QR and SVD. This connection brings us closer to precisely quantifying how the performance of sketch-and-project solvers depends on their sketch size. Our analysis covers not only Gaussian and sub-gaussian sketching matrices, but also a family of efficient sparse sketching methods known as LESS embeddings. Our experiments back up the theory and demonstrate that even extremely sparse sketches show the same convergence properties in practice.

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) Randomized algorithms (68W20) Iterative numerical methods for linear systems (65F10)

Cites Work

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

Cited In (3)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202283)