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 matrixexponential convergencerandomized Kaczmarz algorithm

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the acceleration of Kaczmarz's method for inconsistent linear systems
• The smallest eigenvalue of a large dimensional Wishart matrix
• The rate of convergence of conjugate gradients
• A limit theorem for the norm of random matrices
• Strong underrelaxation in Kaczmarz's method for inconsistent systems
• Efficient numerical methods in non-uniform sampling theory
• The rate of convergence for the method of alternating projections. II
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• The Littlewood-Offord problem and invertibility of random matrices
• On the rate of convergence of the alternating projection method in finite dimensional spaces
• Sampling from large matrices
• Smallest singular value of a random rectangular matrix
• The Probability That a Numerical Analysis Problem is Difficult
• Eigenvalues and Condition Numbers of Random Matrices
• On the Distribution of a Scaled Condition Number
• Reconstruction Algorithms in Irregular Sampling
• Relaxation methods for image reconstruction
• Irregular sampling, Toeplitz matrices, and the approximation of entire functions of exponential type
• Random Sampling of Multivariate Trigonometric Polynomials
• Fast monte-carlo algorithms for finding low-rank approximations
• Tails of Condition Number Distributions

This page was built for publication: A randomized Kaczmarz algorithm with exponential convergence