Randomized extended Kaczmarz for solving least squares
From MaRDI portal
(Redirected from 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)- A randomized Kaczmarz algorithm with exponential convergence
- The randomized Kaczmarz method with mismatched adjoint
- Sequential function approximation on arbitrarily distributed point sets
- Linear convergence of the randomized sparse Kaczmarz method
- A new greedy Kaczmarz algorithm for the solution of very large linear systems
- A geometric probability randomized Kaczmarz method for large scale linear systems
- On Motzkin's method for inconsistent linear systems
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- 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
- On the regularization effect of stochastic gradient descent applied to least-squares
- On the generally randomized extended Gauss-Seidel method
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
- On relaxed greedy randomized iterative methods for the solution of factorized linear systems
- Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method
- A weighted randomized sparse Kaczmarz method for solving linear systems
- Randomized Kaczmarz for tensor linear systems
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- Machine learning with kernels for portfolio valuation and risk management
- A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems
- 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
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- A class of residual-based extended Kaczmarz methods for solving inconsistent linear systems
- Randomized approximate class-specific kernel spectral regression analysis for large-scale face verification
- Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
- 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
- On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems
- 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
- Accelerating the distributed Kaczmarz algorithm by strong over-relaxation
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- 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
- A refinement of an iterative orthogonal projection method
- On the error estimate of the randomized double block Kaczmarz method
- Sequential approximation of functions in Sobolev spaces using random samples
- Projected randomized Kaczmarz methods
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Hildreth's algorithm with applications to soft constraints for user interface layout
- Convergence rates for Kaczmarz-type algorithms
- 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
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- 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
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- Randomized block subsampling Kaczmarz-Motzkin method
- A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
- Incremental regularized least squares for dimensionality reduction of large-scale data
- Extension of an error analysis of the randomized Kaczmarz method for inconsistent linear systems
- Iterative Methods for Solving Factorized Linear Systems
- Single projection Kaczmarz extended algorithms
- An accelerated randomized Kaczmarz algorithm
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Randomized iterative methods for linear systems
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- A stochastic Kaczmarz algorithm for network tomography
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- Learning theory of randomized sparse Kaczmarz method
- Randomized block Kaczmarz method with projection for solving least squares
- A weighted randomized Kaczmarz method for solving linear systems
- Randomized Kaczmarz Converges Along Small Singular Vectors
- Surrounding the solution of a linear system of equations from all sides
- 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
- On greedy randomized augmented Kaczmarz method for solving large sparse inconsistent linear systems
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- Effects of depth, width, and initialization: a convergence analysis of layer-wise training for deep linear neural networks
- 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
- Quantile-based iterative methods for corrupted systems of linear equations
- Distributed algorithms with finite data rates that solve linear equations
- Stochastic reformulations of linear systems: algorithms and convergence theory
- Randomized extended average block Kaczmarz for solving least squares
- scientific article; zbMATH DE number 6402625 (Why is no real title available?)
- Faster randomized block Kaczmarz algorithms
- Random reordering in SOR-type methods
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- A randomized algorithm for multivariate function approximation
- A randomized tensor quadrature method for high dimensional polynomial approximation
- 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
- Convergence analysis of inexact randomized iterative methods
- 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
- Quantile-based Random Kaczmarz for corrupted linear systems of equations
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
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)
