Paved with good intentions: analysis of a randomized block Kaczmarz method

DOI10.1016/J.LAA.2012.12.022zbMath1282.65042arXiv1208.3805OpenAlexW1977769089MaRDI QIDQ2437339

Joel A. Tropp, Deanna Needell

Publication date: 3 March 2014

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

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

zbMATH Keywords

algebraic reconstruction techniqueblock Kaczmarzmatrix pavingprojections onto convex sets

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 (only showing first 100 items - show all)

On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations ⋮ Randomized Kaczmarz algorithm with averaging and block projection ⋮ Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition ⋮ A Deterministic Kaczmarz Algorithm for Solving Linear Systems ⋮ An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection ⋮ Inexact coordinate descent: complexity and preconditioning ⋮ Stochastic block projection algorithms with extrapolation for convex feasibility problems ⋮ Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods ⋮ 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 ⋮ On Relaxed Greedy Randomized Augmented Kaczmarz Methods for Solving Large Sparse Inconsistent Linear Systems ⋮ On Convergence of the Partially Randomized Extended Kaczmarz Method ⋮ Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration ⋮ Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study ⋮ Quantile-Based Iterative Methods for Corrupted Systems of Linear Equations ⋮ Single projection Kaczmarz extended algorithms ⋮ On the relaxed greedy deterministic row and column iterative methods ⋮ Adaptively sketched Bregman projection methods for linear systems ⋮ 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 ⋮ Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems ⋮ Randomized Kaczmarz with averaging ⋮ A greedy block Kaczmarz algorithm for solving large-scale linear systems ⋮ Randomized block Kaczmarz methods with \(k\)-means clustering for solving large linear systems ⋮ Convergence rates for Kaczmarz-type algorithms ⋮ 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 ⋮ Convergence of the multiplicative algebraic reconstruction technique for the inconsistent system of equations ⋮ Randomness and permutations in coordinate descent methods ⋮ Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems ⋮ 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 ⋮ On convergence rates of Kaczmarz-type methods with different selection rules of working rows ⋮ Faster randomized block sparse Kaczmarz by averaging ⋮ A surrogate hyperplane Kaczmarz method for solving consistent linear equations ⋮ A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems ⋮ 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 ⋮ Sparse sampling Kaczmarz–Motzkin method with linear convergence ⋮ On greedy randomized block Gauss-Seidel method with averaging for sparse linear least-squares problems ⋮ The extensions of convergence rates of Kaczmarz-type methods ⋮ Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory ⋮ On fast greedy block Kaczmarz methods for solving large consistent linear systems ⋮ Splitting-based randomized iterative methods for solving indefinite least squares problem ⋮ A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility ⋮ Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression ⋮ Randomized block subsampling Kaczmarz-Motzkin method ⋮ Linear convergence of the randomized sparse Kaczmarz method ⋮ On block Gaussian sketching for the Kaczmarz method ⋮ Accelerating Sparse Recovery by Reducing Chatter ⋮ Accelerating the distributed Kaczmarz algorithm by strong over-relaxation ⋮ Two-subspace projection method for coherent overdetermined systems ⋮ Accelerating the alternating projection algorithm for the case of affine subspaces using supporting hyperplanes ⋮ Block sampling Kaczmarz-Motzkin methods for consistent linear systems ⋮ Randomized Extended Average Block Kaczmarz for Solving Least Squares ⋮ Randomized block Kaczmarz method with projection for solving least squares ⋮ A doubly stochastic block Gauss-Seidel algorithm for solving linear equations ⋮ Convergence analysis for column-action methods in image reconstruction ⋮ Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods ⋮ The Kaczmarz algorithm, row action methods, and statistical learning algorithms ⋮ A refinement of an iterative orthogonal projection method ⋮ Convergence rates of the Kaczmarz-Tanabe method for linear systems ⋮ Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm ⋮ Randomized subspace actions and fusion frames ⋮ 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 ⋮ Строчно-ориентированная форма регуляризованного метода Качмажа ⋮ Unnamed Item ⋮ On the regularization effect of stochastic gradient descent applied to least-squares ⋮ Sampled Tikhonov regularization for large linear inverse problems ⋮ On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems ⋮ Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity ⋮ Randomized Kaczmarz Converges Along Small Singular Vectors ⋮ On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems ⋮ Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions ⋮ 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 ⋮ Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems ⋮ Sampled limited memory methods for massive linear inverse problems ⋮ Convergence Analysis of Inexact Randomized Iterative Methods ⋮ Developing Kaczmarz method for solving Sylvester matrix equations ⋮ Regularized Kaczmarz Algorithms for Tensor Recovery ⋮ Convergence and Semi-Convergence of a Class of Constrained Block Iterative Methods ⋮ On Greedy Randomized Augmented Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems ⋮ 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 ⋮ Randomized Kaczmarz for tensor linear systems

Uses Software

• Blendenpik

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A mathematical introduction to compressive sensing
• 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
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
• User-friendly tail bounds for sums of random matrices
• Block-iterative methods for consistent and inconsistent linear equations
• A fast randomized algorithm for the approximation of matrices
• Randomized Kaczmarz solver for noisy linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin
• Comments on the randomized Kaczmarz method
• Incorporation of a priori moment information into signal recovery and synthesis problems
• 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
• Block-projections algorithms with blocks containing mutually orthogonal rows and columns
• Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
• An elementary proof of the restricted invertibility theorem
• Block-iterative projection methods for parallel computation of solutions to convex feasibility problems
• Dual coordinate ascent methods for non-strictly convex minimization
• Norms of random submatrices and sparse approximation
• Randomized Extended Kaczmarz for Solving Least Squares
• Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform
• A Note on Column Subset Selection
• IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• RESTRICTED INVERTIBILITY AND THE BANACH–MAZUR DISTANCE TO THE CUBE
• Extensions of Pure States
• The Kadison–Singer Problem in mathematics and engineering
• Random sets of isomorphism of linear operators on Hilbert space
• Extensions, Restrictions, and Representations of States on C ∗ - Algebras
• The method of alternating projections and the method of subspace corrections in Hilbert space
• Uncertainty principles and ideal atomic decomposition
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• The random paving property for uniformly bounded matrices
• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
• John's decompositions: Selecting a large part

This page was built for publication: Paved with good intentions: analysis of a randomized block Kaczmarz method