A randomized Kaczmarz algorithm with exponential convergence

DOI10.1007/s00041-008-9030-4zbMath1169.68052arXivmath/0702226OpenAlexW2048305372WikidataQ60059805 ScholiaQ60059805MaRDI QIDQ1027734

Thomas Strohmer, R. V. Vershinin

Publication date: 30 June 2009

Published in: The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

random matrix exponential convergence randomized Kaczmarz algorithm

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Randomized algorithms (68W20)

Related Items

A Deterministic Kaczmarz Algorithm for Solving Linear Systems, An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm, The numerics of phase retrieval, Randomized numerical linear algebra: Foundations and algorithms, Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation, Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra, Properties and applications of a conjugate transform on Schatten classes, PLSS: A Projected Linear Systems Solver, A semi-randomized Kaczmarz method with simple random sampling for large-scale 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, Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory, Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems, Accelerated greedy randomized augmented Kaczmarz algorithm 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, A randomised iterative method for solving factorised linear systems, Faster randomized block sparse Kaczmarz by averaging, A surrogate hyperplane Kaczmarz method for solving consistent linear equations, Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency, Conjugate gradients acceleration of coordinate descent for linear systems, Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems, Sparse sampling Kaczmarz–Motzkin method with linear convergence, Linearly convergent adjoint free solution of least squares problems by random descent, Inversion of a generalized Radon transform by algebraic iterative methods, A Randomized Tensor Quadrature Method for High Dimensional Polynomial Approximation, On greedy randomized block Gauss-Seidel method with averaging for sparse linear least-squares problems, The method of randomized Bregman projections for stochastic feasibility problems, Iterative inversion of Radon transform via discretization by fuzzy basic functions, 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, Stochastic gradient descent: where optimization meets machine learning, Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition, A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility, Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression, Constrained ERM Learning of Canonical Correlation Analysis: A Least Squares Perspective, Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm, Randomized subspace actions and fusion frames, An acceleration scheme for Dykstra's algorithm, Unnamed Item, ON DISCRETE STOCHASTIC PROCESSES WITH DISJUNCTIVE OUTCOMES, Regularized Kaczmarz Algorithms for Tensor Recovery, Greedy Kaczmarz Algorithm Using Optimal Intermediate Projection Technique for Coherent Linear Systems, A Partially Greedy Randomized Extended Gauss-Seidel Method for Solving Large Linear Systems, A Randomized Algorithm for Multivariate Function Approximation, Iteratively consistent one-bit phase retrieval, Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems, Generalized Gearhart-Koshy acceleration for the Kaczmarz method, Convergence of a randomized Douglas-Rachford method for linear system, A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems, Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection, On global randomized block Kaczmarz method for image reconstruction, Stochastic accelerated alternating direction method of multipliers with importance sampling, Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis, The randomized Kaczmarz method with mismatched adjoint, Inexact coordinate descent: complexity and preconditioning, Vector Monte Carlo stochastic matrix-based algorithms for large linear systems, Accelerated compressed sensing based CT image reconstruction, On greedy randomized average block Kaczmarz method for solving large linear systems, On the Kaczmarz methods based on relaxed greedy selection for solving matrix equation \(A X B = C\), On convergence rate of the randomized Kaczmarz method, On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration, Randomized Kaczmarz methods for tensor complementarity problems, Supplementary projections for the acceleration of Kaczmarz algorithm, Single projection Kaczmarz extended algorithms, A class of residual-based extended Kaczmarz methods for solving inconsistent linear systems, Restarted randomized surrounding methods for solving large linear equations, On the relaxed greedy deterministic row and column iterative methods, Randomized approximate class-specific kernel spectral regression analysis for large-scale face verification, On randomized partial block Kaczmarz method for solving huge linear algebraic systems, Rates of convergence of randomized Kaczmarz algorithms in Hilbert spaces, Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems, Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries, Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem, A greedy block Kaczmarz algorithm for solving large-scale linear systems, A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval, Block Kaczmarz method with inequalities, Almost sure convergence of the Kaczmarz algorithm with random measurements, The block-wise circumcentered-reflection method, On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems, An arithmetic-geometric mean inequality for products of three matrices, Duality and nonlinear graph Laplacians, The extensions of convergence rates of Kaczmarz-type methods, A note on convergence rate of randomized Kaczmarz method, Enhancement of the Kaczmarz algorithm with projection adjustment, Sequential function approximation on arbitrarily distributed point sets, On the relation between the randomized extended Kaczmarz algorithm and coordinate descent, Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma, Greedy and randomized versions of the multiplicative Schwarz method, Rejoinder: ``Nonparametric regression using deep neural networks with ReLU activation function, Linear convergence of the randomized sparse Kaczmarz method, A stochastic Kaczmarz algorithm for network tomography, On block Gaussian sketching for the Kaczmarz method, Worst-case complexity of cyclic coordinate descent: \(O(n^2)\) gap with randomized version, A new greedy Kaczmarz algorithm for the solution of very large linear systems, On convergence rate of the randomized Gauss-Seidel method, Accelerating the distributed Kaczmarz algorithm by strong over-relaxation, Two-subspace projection method for coherent overdetermined systems, Block sampling Kaczmarz-Motzkin methods for consistent linear systems, Randomized block Kaczmarz method with projection for solving least squares, Sample-based population observers, An extended row and column method for solving linear systems on a quantum computer, A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates, A doubly stochastic block Gauss-Seidel algorithm for solving linear equations, A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems, Minimizing finite sums with the stochastic average gradient, Random reordering in SOR-type methods, A geometric probability randomized Kaczmarz method for large scale linear systems, Stochastic projection methods and applications to some nonlinear inverse problems of phase retrieving, On Motzkin's method for inconsistent linear systems, Schwarz iterative methods: infinite space splittings, Stability of the Kaczmarz reconstruction for stationary sequences, OLS with multiple high dimensional category variables, Comparison of approaches based on optimization and algebraic iteration for binary tomography, Mean squared error bounds for the Rangan-Goyal soft thresholding algorithm, Randomized Kaczmarz solver for noisy linear systems, Robust inversion, dimensionality reduction, and randomized sampling, A new randomized Gauss-Seidel method for solving linear least-squares problems, Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods, Proximal algorithms and temporal difference methods for solving fixed point problems, Convergence rates of the Kaczmarz-Tanabe method for linear systems, Iterative hard thresholding based on randomized Kaczmarz method, Randomized double and triple Kaczmarz for solving extended normal equations, Nonlinear Kaczmarz algorithms and their convergence, On the regularization effect of stochastic gradient descent applied to least-squares, On the generally randomized extended Gauss-Seidel method, Gauss-Seidel method with oblique direction, A learning-enhanced projection method for solving convex feasibility problems, On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems, A simple recovery framework for signals with time-varying sparse support, Random activations in primal-dual splittings for monotone inclusions with a priori information, A new randomized vector algorithm for iterative solution of large linear systems, A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin, Comments on the randomized Kaczmarz method, Stochastic heavy-ball method for constrained stochastic optimization problems, A Kaczmarz algorithm for sequences of projections, infinite products, and applications to frames in IFS \(L^2\) spaces, On relaxed greedy randomized iterative methods for the solution of factorized linear systems, Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems, Developing Kaczmarz method for solving Sylvester matrix equations, Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method, Matrix concentration for products, A weighted randomized sparse Kaczmarz method for solving linear systems, Global random walk on grid algorithm for solving Navier-Stokes and Burgers equations, Kaczmarz method with oblique projection, Randomized Kaczmarz for tensor linear systems, On a fast deterministic block Kaczmarz method for solving large-scale linear systems, Parallel coordinate descent methods for big data optimization, Effects of depth, width, and initialization: A convergence analysis of layer-wise training for deep linear neural networks, An accelerated randomized Kaczmarz algorithm, Sparse Online Variational Bayesian Regression, Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods, Randomized Iterative Methods for 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, A Fast Block Coordinate Descent Method for Solving Linear Least-Squares Problems, On Convergence of the Partially Randomized Extended Kaczmarz Method, Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study, Quantile-Based Iterative Methods for Corrupted Systems of Linear Equations, Adaptively sketched Bregman projection methods for linear systems, On greedy randomized block Kaczmarz method for consistent linear systems, Online learning in optical tomography: a stochastic approach, Randomized Kaczmarz with averaging, Randomized block Kaczmarz methods with \(k\)-means clustering for solving large linear systems, On extended Kaczmarz methods with random sampling and maximum-distance for solving large inconsistent linear systems, The exponential convergence rate of Kaczmarz's algorithm and an acceleration strategy for ART, Sketched Newton--Raphson, Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations, Convergence rates for Kaczmarz-type algorithms, AIR tools II: algebraic iterative reconstruction methods, improved implementation, Randomized Monte Carlo algorithms for matrix iterations and solving large systems of linear equations, RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression, Fast and Reliable Parameter Estimation from Nonlinear Observations, On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations, Triangular truncation and its extremal matrices, Unnamed Item, A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems, Sequential function approximation with noisy data, Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms, On the Convergence of Stochastic Gradient Descent for Nonlinear Ill-Posed Problems, On multi-step greedy randomized coordinate descent method for solving large linear least-squares problems, Kaczmarz's anomaly: a surprising feature of Kaczmarz's method, Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory, AIR tools -- a MATLAB package of algebraic iterative reconstruction methods, On Chubanov's Method for Linear Programming, Constructing Least-Squares Polynomial Approximations, Variance reduction for root-finding problems, On Greedy Randomized Kaczmarz Method for Solving Large Sparse Linear Systems, On fast greedy block Kaczmarz methods for solving large consistent linear systems, Splitting-based randomized iterative methods for solving indefinite least squares problem, Batched Stochastic Gradient Descent with Weighted Sampling, Paved with good intentions: analysis of a randomized block Kaczmarz method, The randomized Kaczmarz algorithm with the probability distribution depending on the angle, Randomized block subsampling Kaczmarz-Motzkin method, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, Accelerating Sparse Recovery by Reducing Chatter, Randomized Extended Average Block Kaczmarz for Solving Least Squares, A Smooth Inexact Penalty Reformulation of Convex Problems with Linear Constraints, Evasion from pursuers in a problem of group pursuit with fractional derivatives and phase constraints, Kaczmarz-Type Inner-Iteration Preconditioned Flexible GMRES Methods for Consistent Linear Systems, On the regularizing property of stochastic gradient descent, Unnamed Item, On the von Neumann and Frank--Wolfe Algorithms with Away Steps, Convergence of online mirror descent, The Kaczmarz algorithm, row action methods, and statistical learning algorithms, A refinement of an iterative orthogonal projection method, Learning Theory of Randomized Sparse Kaczmarz Method, Random Gradient Extrapolation for Distributed and Stochastic Optimization, Approximating mixed Hölder functions using random samples, Faster Randomized Block Kaczmarz Algorithms, Stochastic iterative projection methods for large linear systems, 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, Sequential approximation of functions in Sobolev spaces using random samples, Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme, Блочный регуляризованный метод Качмажа, Об одной вычислительной реализации блочного метода Гаусса-Зейделя для нормальных систем уравнений, Строчно-ориентированная форма регуляризованного метода Качмажа, Projected randomized Kaczmarz methods, Sampled Tikhonov regularization for large linear inverse problems, On the linear convergence of the stochastic gradient method with constant step-size, Variant of greedy randomized Kaczmarz for ridge regression, Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity, Randomized Kaczmarz Converges Along Small Singular Vectors, Randomized and fault-tolerant method of subspace corrections, On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems, Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method, Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions, Randomized Projection Methods for Convex Feasibility: Conditioning and Convergence Rates, Surrounding the solution of a linear system of equations from all sides, Kaczmarz-Type Inner-Iteration Preconditioned Flexible GMRES Methods for Consistent Linear Systems, An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems, 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, Extension of an error analysis of the randomized Kaczmarz method for inconsistent linear systems, KACZMARZ ALGORITHM AND FRAMES, Analysis of singular value thresholding algorithm for matrix completion, Iterative Methods for Solving Factorized Linear Systems, On Greedy Randomized Augmented Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems, Convergence analysis for Kaczmarz-type methods in a Hilbert space framework, On stochastic Kaczmarz type methods for solving large scale systems of ill-posed equations, An analysis of stochastic variance reduced gradient for linear inverse problems ^*, A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations, Coordinate descent algorithms, An accelerated randomized Kaczmarz method via low-rank approximation, Hildreth's algorithm with applications to soft constraints for user interface layout

Cites Work