Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression

DOI10.1137/16M1077891zbMath1392.65054arXiv1507.05844OpenAlexW2964114727MaRDI QIDQ5372641

Aaditya Ramdas, Ahmed Hefny, Deanna Needell

Publication date: 27 October 2017

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

ridge regressionKaczmarzGauss-Seidel

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Iterative numerical methods for linear systems (65F10) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Randomized algorithms (68W20)

Related Items (19)

Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection ⋮ 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 semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems ⋮ On adaptive block coordinate descent methods for ridge regression ⋮ A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems ⋮ Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency ⋮ On greedy randomized block Gauss-Seidel method with averaging for sparse linear least-squares problems ⋮ A note on convergence rate of randomized Kaczmarz method ⋮ Splitting-based randomized iterative methods for solving indefinite least squares problem ⋮ A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility ⋮ Randomized block subsampling Kaczmarz-Motzkin method ⋮ Randomized Extended Average Block Kaczmarz for Solving Least Squares ⋮ A new randomized Gauss-Seidel method for solving linear least-squares problems ⋮ On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems ⋮ Строчно-ориентированная форма регуляризованного метода Качмажа ⋮ On the generally randomized extended Gauss-Seidel method ⋮ Variant of greedy randomized Kaczmarz for ridge regression

Uses Software

• Regularization Kaczmarz

Cites Work

• Unnamed Item
• Unnamed Item
• Two-subspace projection method for coherent overdetermined systems
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• On Kaczmarz's projection iteration as a direct solver for linear least squares problems
• Block-iterative methods for consistent and inconsistent linear equations
• Randomized Kaczmarz solver for noisy linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• The angles between the null spaces of X rays
• Almost sure convergence of the Kaczmarz algorithm with random measurements
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• The Mathematics of Computerized Tomography
• Fundamentals of Computerized Tomography
• Randomized Extended Kaczmarz for Solving Least Squares
• The method of augmented regularized normal equations
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
• The method of alternating projections and the method of subspace corrections in Hilbert space
• Coordinate Descent Face-Off: Primal or Dual?
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm

This page was built for publication: Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression