Source-linked AI summary
Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
Anna Ma, Deanna Needell, Aaditya Ramdas
TL;DR
Randomized Kaczmarz and Gauss-Seidel methods have convergence behavior that changes across consistent, inconsistent, overdetermined, and underdetermined systems. The paper unifies their analysis, introduces REGS for underdetermined systems, and proves linear convergence to the least norm solution.
Problem
The central problem is that RK and RGS do not behave uniformly across system dimensions and consistency, including failure to reach desired least-squares or least-norm solutions.
Method
The paper develops a unified theory of RK, RGS, REK, and REGS across the main linear-system settings, combining analytical convergence results with simulations.
Results
The main result proves that REGS converges linearly to the least norm solution in the underdetermined case.
Takeaways & Limitations
The resulting framework completes the convergence picture for the four methods across the settings studied in the paper.
Takeaways & Limitations
In underdetermined systems, ordinary RGS can minimize the residual without converging to the least norm solution because row-span-orthogonal components are never eliminated.
Abstract
from arXiv · showhide
The Kaczmarz and Gauss-Seidel methods both solve a linear system $\bf{X}\bfβ = \bf{y}$ by iteratively refining the solution estimate. Recent interest in these methods has been sparked by a proof of Strohmer and Vershynin which shows the randomized Kaczmarz method converges linearly in expectation to the solution. Lewis and Leventhal then proved a similar result for the randomized Gauss-Seidel algorithm. However, the behavior of both methods depends heavily on whether the system is under or overdetermined, and whether it is consistent or not. Here we provide a unified theory of both methods, their variants for these different settings, and draw connections between both approaches. In doing so, we also provide a proof that an extended version of randomized Gauss-Seidel converges linearly to the least norm solution in the underdetermined case (where the usual randomized Gauss Seidel fails to converge). We detail analytically and empirically the convergence properties of both methods and their extended variants in all possible system settings. With this result, a complete and rigorous theory of both methods is furnished.
1. Introduction.
The paper develops a unified account of randomized Kaczmarz and Gauss-Seidel methods across consistent, inconsistent, overdetermined, and underdetermined systems. It introduces REGS to address the underdetermined case and reports theoretical and empirical convergence analyses.
- Motivation and contribution: Randomized Kaczmarz and Randomized Gauss-Seidel have linear convergence results, but their behavior depends on system dimensions and consistency.The paper places existing convergence results within a broader analysis of distinct problem settings.
- Motivation and contribution: In inconsistent overdetermined systems, RK does not converge to the ordinary least-squares solution, whereas REK was developed to converge to βLS.The paper notes that RGS converges to βLS in this setting without a special extension.
- Motivation and contribution: In underdetermined systems, fewer constraints than variables yield infinitely many solutions, motivating interest in the least Euclidean norm solution βLN.This setting is especially relevant when there is no prior reason to assume additional sparsity.
- Motivation and contribution: RGS fails to converge to βLN in the underdetermined setting, while RK is argued to converge to βLN without extensions.RGS can reduce the residual while retaining components orthogonal to the row span of X.
- Motivation and contribution: The paper constructs REGS as an extension paralleling REK and aims to provide a unified theory summarized across the relevant system settings.The proposed method is intended to retain linear convergence, require little additional computation, and perform well in simulations.
2. Existing Algorithms and Related Work.
This section reviews randomized Kaczmarz, randomized extended Kaczmarz, randomized Gauss-Seidel, and their coordinate or projection interpretations. It summarizes how row- and column-based updates behave for consistent and inconsistent systems.
- Randomized Kaczmarz: Strohmer and Vershynin established an expected linear convergence rate for RK to the solution in the consistent setting.Their result provides an explicit rate depending only on geometric properties of the system.
- Randomized Kaczmarz: RK selects rows randomly with probability proportional to row Euclidean norms, then projects the current estimate onto the selected equation.The update can also be interpreted as stochastic gradient descent with a step size given by the inverse stochastic-gradient Lipschitz constant.
- Randomized Extended Kaczmarz: For inconsistent systems, RK does not converge to the least-squares solution because complete projections cannot overcome the convergence horizon.REK instead adds random projections that reduce the component of y orthogonal to the range of X, and it converges linearly in expectation to βLS.
- Randomized Gauss-Seidel: RGS randomly selects a column and minimizes the least-squares objective with respect to that coordinate.Its update is equivalently a univariate descent step whose step size is the inverse Lipschitz constant along the selected coordinate.
- Randomized Gauss-Seidel: Leventhal and Lewis showed that RGS has an expected linear convergence rate.The paper compares this column-based method with the row-based Kaczmarz variants in subsequent convergence analyses.
3. Problem Variations.
The paper unifies randomized Kaczmarz and Gauss-Seidel behavior across consistent, inconsistent, overconstrained, and underconstrained systems. Their convergence targets differ by setting: RGS succeeds for least squares where RK fails, while RK succeeds for least norm where RGS fails, motivating extended methods.
- Problem Variations: The analysis compares RK and RGS across three system settings to clarify their opposing convergence behavior.The settings are unique consistent, inconsistent least squares, and minimum-norm consistent systems.
- Overconstrained System, Consistent: In the unique consistent setting, both RK and RGS converge linearly, with equivalent analyses presented side by side.The comparison uses Σ = X*X and conditional expectations over the next randomized update.
- Overconstrained System, Inconsistent: In inconsistent overconstrained systems, RK does not converge to βLS because its projections use incorrect hyperplanes, whereas RGS converges linearly to βLS.RGS operates through fitted values Xβ, preserving the Pythagorean argument in this setting.
- Underconstrained System, Infinite Solutions: In underconstrained systems, RK converges linearly to βLN from β0 = 0, while RGS iterates fail to converge to βLN even though Xβt converges to XβLN.RGS can reduce the residual while retaining components orthogonal to the row span, which residual minimization ignores.
- Extensions: The proposed REGS extension is designed to make RGS converge to the least-norm solution, completing the unified framework alongside REK.The paper also aims for linear convergence, limited extra computation, and good simulation performance.
4. REGS.
REGS extends randomized Gauss-Seidel by removing the iterate’s component orthogonal to the row span, yielding linear convergence to the least-norm solution in underdetermined systems. The analysis also applies to overdetermined consistent and inconsistent systems, with convergence bounds comparable to related methods.
- Main result: The main theorem proves that REGS converges linearly to the least-norm solution in the underdetermined case.This extends the convergence guarantees available for RK and REK in that setting.
- Proof strategy: The proof controls conditional expected errors by combining projection identities, orthogonal decompositions, and bounds involving α and B.The argument uses conditional expectations over the randomized row and column choices and an auxiliary lemma to complete the convergence proof.
- Overdetermined systems: The same proof framework applies to overdetermined consistent and inconsistent systems because the key lemmas hold for β_LS and β* in those settings.The authors state that REGS therefore has the same relevant theoretical coverage across these cases.
- Comparison: Up to constant terms, the convergence bounds for RK, REK, RGS, and REGS provide the same rate α in the compared settings.The paper attributes likely differences in constants to artifacts of the proofs.
5. Empirical Results.
Experiments evaluate REGS on random underdetermined systems, larger systems, and a tomography problem using median ℓ2-error across repeated trials. REGS often converges faster than its theoretical worst-case bound, while iteration-based comparisons find RK and RGS faster than their extended counterparts.
- Experimental setup: 50-trial experiments track median ℓ2-error, trial ranges, and theoretical upper bounds for REGS on random linear systems.The plots use a solid blue median curve, a light blue trial-range band, and a red theoretical bound.
- Random systems: REGS is tested on varying-sized underdetermined systems, including a 150 × 500 matrix and m × 500 matrices with m = 50, 100, 150.Figure 5.1 compares the observed ℓ2-error with the theoretical bound and examines matrix-size variation.
- Observed convergence: REGS often converges much faster than the theoretical worst-case bound.This observation is reported for the plotted convergence experiments.
- Tomography and larger systems: REGS is also evaluated on a 700 × 1000 system and a 400 × 1200 tomography problem.The tomography experiments use absorption samples along random lines on a 20 × 20 grid with oversampling factor d = 3.
- Algorithm comparison: In iteration-based comparisons, RK and RGS converge faster than their extended counterparts, while REGS and REK reach the desired solution at about the same rate.The comparison covers RK, REK, RGS, and REGS under the paper’s different system settings.
6. Conclusion.
The paper compares randomized Kaczmarz and Gauss-Seidel variants across underdetermined and overdetermined settings, including inconsistent systems. It presents REGS as part of a unified treatment of these methods.
- Figure 5.3 compares RK, REK, and REGS using median ℓ2-error on a log scale for an underdetermined system.
- Figure 5.4 compares RGS, REK, and REGS using median ℓ2-error on a log scale for an overdetermined, inconsistent system.
- The paper presents REGS as a natural extension of RGS within a unified analysis of the methods and their solution behavior.