Randomized extended Kaczmarz for solving least squares
From MaRDI portal
Publication:2848636
Abstract: We present a randomized iterative algorithm that exponentially converges in expectation to the minimum Euclidean norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the square condition number of the system multiplied by the number of non-zeros entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.
Recommendations
- Randomized extended average block Kaczmarz for solving least squares
- Randomized block Kaczmarz method with projection for solving least squares
- Single projection Kaczmarz extended algorithms
- Randomized double and triple Kaczmarz for solving extended normal equations
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
Cited in
(only showing first 100 items - show all)- Distributed algorithms with finite data rates that solve linear equations
- A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval
- Randomized block Kaczmarz method with projection for solving least squares
- scientific article; zbMATH DE number 7708789 (Why is no real title available?)
- On relaxed greedy randomized augmented Kaczmarz methods for solving large sparse inconsistent linear systems
- On the generally randomized extended Gauss-Seidel method
- On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems
- Randomized double and triple Kaczmarz for solving extended normal equations
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- Single projection Kaczmarz extended algorithms
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- Faster randomized block Kaczmarz algorithms
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- A randomised iterative method for solving factorised linear systems
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- The randomized Kaczmarz method with mismatched adjoint
- A weighted randomized Kaczmarz method for solving linear systems
- The extensions of convergence rates of Kaczmarz-type methods
- A new greedy Kaczmarz algorithm for the solution of very large linear systems
- A greedy block Kaczmarz algorithm for solving large-scale linear systems
- A geometric probability randomized Kaczmarz method for large scale linear systems
- A randomized tensor quadrature method for high dimensional polynomial approximation
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- A randomized algorithm for multivariate function approximation
- On the regularization effect of stochastic gradient descent applied to least-squares
- On greedy randomized average block Kaczmarz method for solving large linear systems
- On the relation between the randomized extended Kaczmarz algorithm and coordinate descent
- A fast block coordinate descent method for solving linear least-squares problems
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- An accelerated randomized Kaczmarz algorithm
- Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification
- On convergence of the partially randomized extended Kaczmarz method
- Randomized block Kaczmarz methods with \(k\)-means clustering for solving large linear systems
- Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory
- A note on convergence rate of randomized Kaczmarz method
- Randomized Kaczmarz Converges Along Small Singular Vectors
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems
- A weighted randomized sparse Kaczmarz method for solving linear systems
- Enhancement of the Kaczmarz algorithm with projection adjustment
- Subspace correction methods in algebraic multi-level frames
- Incremental regularized least squares for dimensionality reduction of large-scale data
- On Adaptive Sketch-and-Project for Solving Linear Systems
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Linear convergence of the randomized sparse Kaczmarz method
- A randomized Kaczmarz algorithm with exponential convergence
- Randomized Kaczmarz with averaging
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- Projected randomized Kaczmarz methods
- Randomized extended average block Kaczmarz for solving least squares
- Randomized Kaczmarz solver for noisy linear systems
- A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
- Stochastic reformulations of linear systems: algorithms and convergence theory
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized Block Adaptive Linear System Solvers
- Random reordering in SOR-type methods
- Block Kaczmarz method with inequalities
- Sequential approximation of functions in Sobolev spaces using random samples
- Hildreth's algorithm with applications to soft constraints for user interface layout
- Regularized Kaczmarz Algorithms for Tensor Recovery
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- Iterative Methods for Solving Factorized Linear Systems
- Approximate Solutions of Linear Systems at a Universal Rate
- A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems
- Sequential function approximation on arbitrarily distributed point sets
- Randomized iterative methods for linear systems
- On Motzkin's method for inconsistent linear systems
- A stochastic Kaczmarz algorithm for network tomography
- A refinement of an iterative orthogonal projection method
- Convergence rates for Kaczmarz-type algorithms
- Effects of depth, width, and initialization: a convergence analysis of layer-wise training for deep linear neural networks
- Kaczmarz-type methods for solving matrix equations
- Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method
- Randomized Kaczmarz with geometrically smoothed momentum
- A randomized block Douglas-Rachford method for solving linear matrix equation
- Quantile-based iterative methods for corrupted systems of linear equations
- Convergence analysis of inexact randomized iterative methods
- Randomized Kaczmarz algorithm with averaging and block projection
- A class of residual-based extended Kaczmarz methods for solving inconsistent linear systems
- On adaptive stochastic heavy ball momentum for solving linear systems
- Randomized approximate class-specific kernel spectral regression analysis for large-scale face verification
- Choosing relaxation parameter in randomized Kaczmarz method
- On the adaptive deterministic block Kaczmarz method with momentum for solving large-scale consistent linear systems
- Convergence of the multiplicative algebraic reconstruction technique for the inconsistent system of equations
- The greedy randomized extended Kaczmarz algorithm for noisy linear systems
- On greedy randomized augmented Kaczmarz method for solving large sparse inconsistent linear systems
- On weighted average fast block Kaczmarz methods for solving large consistent linear systems
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
- Machine learning with kernels for portfolio valuation and risk management
- Randomized Kaczmarz for tensor linear systems
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- A two-dimensional randomized extended Gauss-Seidel algorithm for solving least squares problems
- Quantile-based Random Kaczmarz for corrupted linear systems of equations
- Greedy block extended Kaczmarz method for solving the least squares problems
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- Pseudo inverse versus iterated projection: novel learning approach and its application on broad learning system
This page was built for publication: Randomized extended Kaczmarz for solving least squares
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848636)
