Paved with good intentions: analysis of a randomized block Kaczmarz method
From MaRDI portal
Publication:2437339
DOI10.1016/J.LAA.2012.12.022zbMATH Open1282.65042arXiv1208.3805OpenAlexW1977769089MaRDI QIDQ2437339FDOQ2437339
Publication date: 3 March 2014
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Abstract: The block Kaczmarz method is an iterative scheme for solving overdetermined least-squares problems. At each step, the algorithm projects the current iterate onto the solution space of a subset of the constraints. This paper describes a block Kaczmarz algorithm that uses a randomized control scheme to choose the subset at each step. This algorithm is the first block Kaczmarz method with an (expected) linear rate of convergence that can be expressed in terms of the geometric properties of the matrix and its submatrices. The analysis reveals that the algorithm is most effective when it is given a good row paving of the matrix, a partition of the rows into well-conditioned blocks. The operator theory literature provides detailed information about the existence and construction of good row pavings. Together, these results yield an efficient block Kaczmarz scheme that applies to many overdetermined least-squares problem.
Full work available at URL: https://arxiv.org/abs/1208.3805
Recommendations
Numerical solutions to overdetermined systems, pseudoinverses (65F20) Randomized algorithms (68W20) Iterative numerical methods for linear systems (65F10) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65)
Cites Work
- A randomized Kaczmarz algorithm with exponential convergence
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
- User-friendly tail bounds for sums of random matrices
- Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
- Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
- An elementary proof of the restricted invertibility theorem
- RESTRICTED INVERTIBILITY AND THE BANACH–MAZUR DISTANCE TO THE CUBE
- Extensions of Pure States
- Title not available (Why is that?)
- The Kadison–Singer Problem in mathematics and engineering
- A mathematical introduction to compressive sensing
- Title not available (Why is that?)
- Extensions, Restrictions, and Representations of States on C ∗ - Algebras
- Uncertainty principles and ideal atomic decomposition
- Title not available (Why is that?)
- The random paving property for uniformly bounded matrices
- Block-iterative projection methods for parallel computation of solutions to convex feasibility problems
- Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
- The method of alternating projections and the method of subspace corrections in Hilbert space
- A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
- Title not available (Why is that?)
- IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
- Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
- Randomized extended Kaczmarz for solving least squares
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- Randomized Kaczmarz solver for noisy linear systems
- Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
- Title not available (Why is that?)
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality
- The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
- A fast randomized algorithm for the approximation of matrices
- Norms of random submatrices and sparse approximation
- Block-iterative methods for consistent and inconsistent linear equations
- Incorporation of a priori moment information into signal recovery and synthesis problems
- Dual coordinate ascent methods for non-strictly convex minimization
- The angles between the null spaces of X rays
- Two-subspace projection method for coherent overdetermined systems
- John's decompositions: Selecting a large part
- Block-projections algorithms with blocks containing mutually orthogonal rows and columns
- A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
- Random sets of isomorphism of linear operators on Hilbert space
- A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin
- Comments on the randomized Kaczmarz method
- A Note on Column Subset Selection
Cited In (only showing first 100 items - show all)
- Randomized Kaczmarz with averaging
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- Inexact coordinate descent: complexity and preconditioning
- Surrounding the solution of a linear system of equations from all sides
- On greedy randomized average block Kaczmarz method for solving large linear systems
- On randomized partial block Kaczmarz method for solving huge linear algebraic systems
- Randomized Iterative Methods for Linear Systems
- Faster Randomized Block Kaczmarz Algorithms
- A refinement of an iterative orthogonal projection method
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- Accelerating Sparse Recovery by Reducing Chatter
- A weighted randomized Kaczmarz method for solving linear systems
- Randomized Kaczmarz Converges Along Small Singular Vectors
- On Adaptive Sketch-and-Project for Solving Linear Systems
- Randomized numerical linear algebra: Foundations and algorithms
- On greedy randomized block Kaczmarz method for consistent linear systems
- Randomized block Kaczmarz methods with \(k\)-means clustering for solving large linear systems
- Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
- On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
- Randomized Block Adaptive Linear System Solvers
- On greedy randomized block Gauss-Seidel method with averaging for sparse linear least-squares problems
- Convergence and Semi-Convergence of a Class of Constrained Block Iterative Methods
- Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- On Convergence of the Partially Randomized Extended Kaczmarz Method
- Convergence Analysis of Inexact Randomized Iterative Methods
- Randomized subspace actions and fusion frames
- Convergence rates of the Kaczmarz-Tanabe method for linear systems
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
- Regularized Kaczmarz Algorithms for Tensor Recovery
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- On Greedy Randomized Augmented Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems
- On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems
- The extensions of convergence rates of Kaczmarz-type methods
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
- Approximate Solutions of Linear Systems at a Universal Rate
- On the relaxed greedy deterministic row and column iterative methods
- Randomized approximate class-specific kernel spectral regression analysis for large-scale face verification
- A greedy block Kaczmarz algorithm for solving large-scale linear systems
- On block Gaussian sketching for the Kaczmarz method
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- Convergence rates for Kaczmarz-type algorithms
- Adaptively sketched Bregman projection methods for linear systems
- Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
- On the regularization effect of stochastic gradient descent applied to least-squares
- Строчно-ориентированная форма регуляризованного метода Качмажа
- Single projection Kaczmarz extended algorithms
- Two-subspace projection method for coherent overdetermined systems
- Accelerating the alternating projection algorithm for the case of affine subspaces using supporting hyperplanes
- Randomized Extended Average Block Kaczmarz for Solving Least Squares
- Title not available (Why is that?)
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
- Randomized block Kaczmarz method with projection for solving least squares
- A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- On the error estimate of the randomized double block Kaczmarz method
- Block Kaczmarz method with inequalities
- Sparse sampling Kaczmarz–Motzkin method with linear convergence
- Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems
- On Relaxed Greedy Randomized Augmented Kaczmarz Methods for Solving Large Sparse Inconsistent Linear Systems
- Convergence analysis for column-action methods in image reconstruction
- Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
- Randomness and permutations in coordinate descent methods
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- Developing Kaczmarz method for solving Sylvester matrix equations
- Randomized Kaczmarz for tensor linear systems
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Linear convergence of the randomized sparse Kaczmarz method
- On constrained Kaczmarz algorithm with momentum for image reconstruction
- Faster randomized block sparse Kaczmarz by averaging
- Solving, tracking and stopping streaming linear inverse problems
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- On adaptive stochastic heavy ball momentum for solving linear systems
- The accelerated tensor Kaczmarz algorithm with adaptive parameters for solving tensor systems
- Sampled limited memory methods for massive linear inverse problems
- Accelerating the distributed Kaczmarz algorithm by strong over-relaxation
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- Tensor randomized extended Kaczmarz methods for large inconsistent tensor linear equations with t-product
- Average block column action methods for solving least squares problems
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- Greedy Kaczmarz Algorithm Using Optimal Intermediate Projection Technique for Coherent Linear Systems
- Generalized Gearhart-Koshy acceleration for the Kaczmarz method
- Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
- Sampled Tikhonov regularization for large linear inverse problems
- An almost-maximal residual tensor block Kaczmarz method for large tensor linear systems
- On convergence rates of Kaczmarz-type methods with different selection rules of working rows
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- On adaptive block coordinate descent methods for ridge regression
- An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
- A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
Uses Software
This page was built for publication: Paved with good intentions: analysis of a randomized block Kaczmarz method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437339)
