On block Gaussian sketching for the Kaczmarz method

DOI10.1007/s11075-020-00895-9zbMath1456.65023arXiv1905.08894OpenAlexW3010837853MaRDI QIDQ2219454

Deanna Needell, Elizaveta Rebrova

Publication date: 20 January 2021

Published in: Numerical Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random matricesconcentration of measurerandomized algorithmsblock Kaczmarz methodnoisy linear systemsGaussian sketching

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Iterative numerical methods for linear systems (65F10) Random matrices (algebraic aspects) (15B52) Randomized algorithms (68W20)

Related Items (12)

Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration ⋮ Quantile-Based Iterative Methods for Corrupted Systems of Linear Equations ⋮ On adaptive block coordinate descent methods for ridge regression ⋮ Randomized Block Adaptive Linear System Solvers ⋮ A surrogate hyperplane Kaczmarz method for solving consistent linear equations ⋮ Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems ⋮ The method of randomized Bregman projections for stochastic feasibility problems ⋮ Randomized Kaczmarz algorithm with averaging and block projection ⋮ Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition ⋮ Convergence analyses based on frequency decomposition for the randomized row iterative method ⋮ On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems ⋮ Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin

Uses Software

• UCI-ml

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper bound for intermediate singular values of random matrices
• Two-subspace projection method for coherent overdetermined systems
• Block-iterative methods for consistent and inconsistent linear equations
• Randomized Kaczmarz solver for noisy linear systems
• A universality result for the smallest eigenvalues of certain sample covariance matrices
• A randomized Kaczmarz algorithm with exponential convergence
• Incorporation of a priori moment information into signal recovery and synthesis problems
• Some inequalities for Gaussian processes and applications
• Condition numbers of random matrices
• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• The Littlewood-Offord problem and invertibility of random matrices
• Randomized Iterative Methods for Linear Systems
• Smallest singular value of a random rectangular matrix
• Eigenvalues and Condition Numbers of Random Matrices
• High-Dimensional Probability
• Phase retrieval via randomized Kaczmarz: theoretical guarantees
• A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
• Condition Numbers of Gaussian Random Matrices
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm

This page was built for publication: On block Gaussian sketching for the Kaczmarz method