Randomized block Kaczmarz method with projection for solving least squares

DOI10.1016/j.laa.2015.06.027zbMath1330.65056arXiv1403.4192OpenAlexW1754711404MaRDI QIDQ491121

Ran Zhao, Anastasios Zouzias, Deanna Needell

Publication date: 24 August 2015

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

algebraic reconstruction techniqueblock Kaczmarzmatrix pavingprojections onto convex setsrandomized extended Kaczmarz

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Iterative numerical methods for linear systems (65F10) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Randomized algorithms (68W20)

Related Items (57)

A Deterministic Kaczmarz Algorithm for Solving Linear Systems ⋮ An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm ⋮ Convergence of a randomized Douglas-Rachford method for linear system ⋮ Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection ⋮ Randomized Iterative Methods for Linear Systems ⋮ On greedy randomized average block Kaczmarz method for solving large linear systems ⋮ On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations ⋮ A Fast Block Coordinate Descent Method for Solving Linear Least-Squares Problems ⋮ On Convergence of the Partially Randomized Extended Kaczmarz Method ⋮ Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration ⋮ On the relaxed greedy deterministic row and column iterative methods ⋮ Randomized approximate class-specific kernel spectral regression analysis for large-scale face verification ⋮ On greedy randomized block Kaczmarz method for consistent linear systems ⋮ On randomized partial block Kaczmarz method for solving huge linear algebraic systems ⋮ A greedy block Kaczmarz algorithm for solving large-scale linear systems ⋮ Block Kaczmarz method with inequalities ⋮ A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems ⋮ An almost-maximal residual tensor block Kaczmarz method for large tensor linear systems ⋮ Approximate Solutions of Linear Systems at a Universal Rate ⋮ On adaptive block coordinate descent methods for ridge regression ⋮ On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems ⋮ Randomized Block Adaptive Linear System Solvers ⋮ On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations ⋮ The standard forms and convergence theory of the Kaczmarz-Tanabe type methods for solving linear systems ⋮ Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems ⋮ The extensions of convergence rates of Kaczmarz-type methods ⋮ On the Convergence of Stochastic Gradient Descent for Linear Inverse Problems in Banach Spaces ⋮ Randomized Kaczmarz algorithm with averaging and block projection ⋮ Enhancement of the Kaczmarz algorithm with projection adjustment ⋮ A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility ⋮ Accelerating the distributed Kaczmarz algorithm by strong over-relaxation ⋮ Block sampling Kaczmarz-Motzkin methods for consistent linear systems ⋮ Randomized Extended Average Block Kaczmarz for Solving Least Squares ⋮ A doubly stochastic block Gauss-Seidel algorithm for solving linear equations ⋮ Stability of the Kaczmarz reconstruction for stationary sequences ⋮ Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods ⋮ Faster Randomized Block Kaczmarz Algorithms ⋮ On the error estimate of the randomized double block Kaczmarz method ⋮ A weighted randomized Kaczmarz method for solving linear systems ⋮ 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 ⋮ Randomized double and triple Kaczmarz for solving extended normal equations ⋮ Строчно-ориентированная форма регуляризованного метода Качмажа ⋮ On the regularization effect of stochastic gradient descent applied to least-squares ⋮ On the generally randomized extended Gauss-Seidel method ⋮ On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems ⋮ Randomized Kaczmarz Converges Along Small Singular Vectors ⋮ Surrounding the solution of a linear system of equations from all sides ⋮ On Adaptive Sketch-and-Project for Solving Linear Systems ⋮ Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin ⋮ Sampled limited memory methods for massive linear inverse problems ⋮ Convergence Analysis of Inexact Randomized Iterative Methods ⋮ Regularized Kaczmarz Algorithms for Tensor Recovery ⋮ Greedy Kaczmarz Algorithm Using Optimal Intermediate Projection Technique for Coherent Linear Systems ⋮ Convergence analysis for Kaczmarz-type methods in a Hilbert space framework ⋮ A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations ⋮ On a fast deterministic block Kaczmarz method for solving large-scale linear systems

Uses Software

• Regularization tools

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality
• Two-subspace projection method for coherent overdetermined systems
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• On Kaczmarz's projection iteration as a direct solver for linear least squares problems
• Block-iterative methods for consistent and inconsistent linear equations
• Block Kaczmarz method with inequalities
• On the acceleration of Kaczmarz's method for inconsistent linear systems
• Randomized Kaczmarz solver for noisy linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• The angles between the null spaces of X rays
• Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
• Strong underrelaxation in Kaczmarz's method for inconsistent systems
• Block-projections algorithms with blocks containing mutually orthogonal rows and columns
• The rate of convergence for the method of alternating projections. II
• Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
• An elementary proof of the restricted invertibility theorem
• Norms of random submatrices and sparse approximation
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Regularization tools version \(4.0\) for matlab \(7.3\)
• Projection method for solving a singular system of linear equations and its applications
• On the rate of convergence of the alternating projection method in finite dimensional spaces
• The Mathematics of Computerized Tomography
• Fundamentals of Computerized Tomography
• Randomized Extended Kaczmarz for Solving Least Squares
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Random sets of isomorphism of linear operators on Hilbert space
• A Randomized Solver for Linear Systems with Exponential Convergence
• The method of alternating projections and the method of subspace corrections in Hilbert space
• Column Subset Selection, Matrix Factorization, and Eigenvalue Optimization
• The random paving property for uniformly bounded matrices
• Two Algorithms Related to the Method of Steepest Descent
• John's decompositions: Selecting a large part

This page was built for publication: Randomized block Kaczmarz method with projection for solving least squares