Paved with good intentions: analysis of a randomized block Kaczmarz method
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4205183 (Why is no real title available?)
- scientific article; zbMATH DE number 4001918 (Why is no real title available?)
- scientific article; zbMATH DE number 4056349 (Why is no real title available?)
- scientific article; zbMATH DE number 852536 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- scientific article; zbMATH DE number 3027894 (Why is no real title available?)
- A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
- A Kaczmarz-Kovarik algorithm for symmetric ill-conditioned matrices
- A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
- A fast randomized algorithm for the approximation of matrices
- A mathematical introduction to compressive sensing
- A note on column subset selection
- A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin
- A randomized Kaczmarz algorithm with exponential convergence
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- An elementary proof of the restricted invertibility theorem
- Applied iterative methods.
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Block-iterative methods for consistent and inconsistent linear equations
- Block-iterative projection methods for parallel computation of solutions to convex feasibility problems
- Block-projections algorithms with blocks containing mutually orthogonal rows and columns
- Comments on the randomized Kaczmarz method
- Dual coordinate ascent methods for non-strictly convex minimization
- Extensions of Pure States
- Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
- Extensions, Restrictions, and Representations of States on C ∗ - Algebras
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Improved analysis of the subsampled randomized Hadamard transform
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- 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
- Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality
- Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
- John's decompositions: Selecting a large part
- Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
- Norms of random submatrices and sparse approximation
- RESTRICTED INVERTIBILITY AND THE BANACH–MAZUR DISTANCE TO THE CUBE
- Random sets of isomorphism of linear operators on Hilbert space
- Randomized Kaczmarz solver for noisy linear systems
- Randomized extended Kaczmarz for solving least squares
- Randomized methods for linear constraints: convergence rates and conditioning
- The angles between the null spaces of X rays
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
- The method of alternating projections and the method of subspace corrections in Hilbert space
- The random paving property for uniformly bounded matrices
- Two-subspace projection method for coherent overdetermined systems
- Uncertainty principles and ideal atomic decomposition
- User-friendly tail bounds for sums of random matrices
Cited in
(only showing first 100 items - show all)- An accelerated block randomized Kaczmarz method
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Mismatched adjoint random Kaczmarz with averaging
- Randomized block residual steepest descent method with k-means clustering for large sparse linear systems
- Inertial randomized Kaczmarz algorithms for solving coherent linear systems
- Survey of a class of iterative row-action methods: the Kaczmarz method
- The standard forms and convergence theory of the Kaczmarz-Tanabe type methods for solving linear systems
- On a nonlinear fast deterministic block Kaczmarz method for solving nonlinear equations
- Randomized Kaczmarz with averaging
- Inexact coordinate descent: complexity and preconditioning
- The row-oriented form of the regularized Kaczmarz's method
- Randomized extended average block Kaczmarz for solving least squares
- On the block Kaczmarz-Tanabe methods with relaxation parameters for solving linear systems
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- On constrained Kaczmarz algorithm with momentum for image reconstruction
- The block Kaczmarz algorithm based on solving linear systems with arrowhead matrices
- Surrounding the solution of a linear system of equations from all sides
- Faster randomized block sparse Kaczmarz by averaging
- On greedy randomized average block Kaczmarz method for solving large linear systems
- Multigrid method with greedy partial block Jacobi smoother for solving two-dimensional space-fractional diffusion equations
- On randomized partial block Kaczmarz method for solving huge linear algebraic systems
- Solving, tracking and stopping streaming linear inverse problems
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- A guide to stochastic optimisation for large-scale inverse problems
- A refinement of an iterative orthogonal projection method
- 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
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- The accelerated tensor Kaczmarz algorithm with adaptive parameters for solving tensor systems
- Accelerating the distributed Kaczmarz algorithm by strong over-relaxation
- A weighted randomized Kaczmarz method for solving linear systems
- Accelerating Sparse Recovery by Reducing Chatter
- Sampled limited memory methods for massive linear inverse problems
- Randomized Kaczmarz Converges Along Small Singular Vectors
- On Adaptive Sketch-and-Project for Solving Linear Systems
- Randomized numerical linear algebra: Foundations and algorithms
- Quantile-based iterative methods for corrupted systems of linear equations
- 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
- On greedy randomized block Kaczmarz method for consistent linear systems
- Randomized block Kaczmarz methods with k-means clustering for solving large linear systems
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
- The equivalence of the randomized extended Gauss-Seidel and randomized extended Kaczmarz 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
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- Randomized Block Adaptive Linear System Solvers
- On greedy randomized block Gauss-Seidel method with averaging for sparse linear least-squares problems
- Generalized Gearhart-Koshy acceleration for the Kaczmarz method
- On randomized multiple row-action methods for linear feasibility problems
- Stochastic reformulations of linear systems: algorithms and convergence theory
- Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Sampled Tikhonov regularization for large linear inverse problems
- On relaxed greedy randomized augmented Kaczmarz methods for solving large sparse inconsistent linear systems
- An almost-maximal residual tensor block Kaczmarz method for large tensor linear systems
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- On convergence rates of Kaczmarz-type methods with different selection rules of working rows
- A greedy randomized average block projection method for linear feasibility problems
- Quantile-based random sparse Kaczmarz for corrupted and noisy linear systems
- Convergence rates of the Kaczmarz-Tanabe method for linear systems
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Randomized subspace actions and fusion frames
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- 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
- Linear discriminant analysis with the randomized Kaczmarz method
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
- On randomized explicit block Kaczmarz method for solving large linear systems
- Regularized Kaczmarz Algorithms for Tensor Recovery
- Acceleration and restart for the randomized Bregman-Kaczmarz method
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- Randomized Kaczmarz algorithm with averaging and block projection
- Convergence of the multiplicative algebraic reconstruction technique for the inconsistent system of equations
- A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctions
- A partially randomized extended Kaczmarz method for solving inconsistent rank-deficient linear systems
- Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
- Randomized iterative methods for tensor regression under the t-product
- Faster randomized block Kaczmarz algorithms
- On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems
- The extensions of convergence rates of Kaczmarz-type methods
- Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- 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
- Approximate Solutions of Linear Systems at a Universal Rate
- The quaternion relaxed greedy randomized Kaczmarz method with adaptive parameters for solving quaternion matrix equation
- The global block Kaczmarz method using double greedy strategy
- On block Gaussian sketching for the Kaczmarz method
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- Convergence rates for Kaczmarz-type algorithms
- Convergence and semi-convergence of a class of constrained block iterative methods
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)
