PaperlayerView exact revision on arXiv

Source-linked AI summary

Faster randomized block Kaczmarz algorithms

Ion Necoara

arXiv:1902.09946v1math.OC

TL;DR

For averaged block Kaczmarz, prior rates did not expose dependence on block size or block geometry, and theory had not explained extrapolation’s observed efficiency. The paper analyzes randomized block selection and extrapolated stepsizes, deriving expected linear convergence rates and identifying well-conditioned block sampling as especially effective.

  • Problem

    For averaged block Kaczmarz, existing rates did not show dependence on block size or submatrix geometry, and theory did not explain extrapolation’s observed reduction in iterations.

    Source: §1.1 · p. 2, §1.2 · p. 2

  • Method

    The paper analyzes randomized block Kaczmarz with stochastic row-block selection and extrapolated stepsizes.

    Source: §1.2 · p. 2, §2.1 · p. 3

  • Results

    The analysis establishes expected linear convergence rates tied to matrix and submatrix geometry and block size, and finds extrapolated RBK especially effective with well-conditioned row blocks.

    Source: §2.3 · p. 4

  • Takeaways & Limitations

    Block sampling that partitions rows into well-conditioned blocks is identified as the most effective setting for distributed extrapolated RBK.

    Source: §2.3 · p. 4, §4.3 · p. 14

    For λmin(AAT)=0, extending Theorem 5.1 to the stronger criterion remains open.

    Source: §5.1 · p. 15, §5.2 · p. 18

Abstract

from arXiv · show

The Kaczmarz algorithm is a simple iterative scheme for solving consistent linear systems. At each step, the method projects the current iterate onto the solution space of a single constraint. Hence, it requires very low cost per iteration and storage, and it has a linear rate of convergence. Distributed implementations of Kaczmarz have become, in recent years, the de facto architectural choice for large-scale linear systems. Therefore, in this paper we develop a family of randomized block Kaczmarz algorithms that uses at each step a subset of the constraints and extrapolated stepsizes, and can be deployed on distributed computing units. Our approach is based on several new ideas and tools, including stochastic selection rule for the blocks of rows, stochastic conditioning of the linear system, and novel strategies for designing extrapolated stepsizes. We prove that randomized block Kaczmarz algorithm converges linearly in expectation, with a rate depending on the geometric properties of the matrix and its submatrices and on the size of the blocks. Our convergence analysis reveals that the algorithm is most effective when it is given a good sampling of the rows into well-conditioned blocks. Besides providing a general framework for the design and analysis of randomized block Kaczmarz methods, our results resolve an open problem in the literature related to the theoretical understanding of observed practical efficiency of extrapolated block Kaczmarz methods.

1. Introduction.

The introduction frames Kaczmarz methods as low-cost iterative approaches for consistent linear systems, then motivates randomized row blocks and extrapolated stepsizes. It highlights gaps in explaining extrapolation’s observed efficiency and in accounting for row-block importance.

1. Introduction.

  • For consistent systems, the goal is to find a point within a chosen tolerance of the solution set, which models problems across engineering and physics.The passage lists applications including partial differential equations, sensor networks, filtering, signal processing, tomography, machine learning, and optimal control.Source: §1 · p. 1

1.1. Iterative methods.

  • Block projection Kaczmarz projects onto an entire sampled block but incurs least-squares cost, whereas block Kaczmarz averages individual row projections at comparable per-iteration cost and supports distributed units.The averaged-row update has per-iteration cost O(τn), compared with O(τ^2n) for block projection.Source: §1.1 · p. 2

1.2. Extrapolation.

  • Extrapolation moves beyond the projection average with αk≥2 and empirically speeds the averaged block method, but theory had not explained its reduced iteration counts over αk=1.The cited adaptive stepsize is often much larger than 2 and is reported to converge faster than stepsizes in (0, 2).Source: §1.2 · p. 2

1.3. Rows importance.

  • Existing importance analyses address block projection rather than the averaged-row update, while some row blocks may merit more frequent sampling.The text notes that uniform sampling is natural but that different blocks can have different importance.Source: §1.3 · pp. 2–3

2. Contributions.

The paper develops a randomized block Kaczmarz framework that couples row-block sampling with extrapolated stepsizes. Its expected linear convergence rates depend on matrix geometry and block size, and its analysis identifies well-conditioned block sampling as especially effective.

2.1. General framework.

  • Sampling a row block both defines the randomized selection rule and assigns block importance; for normalized rows, λblock^max characterizes that importance.The analysis identifies sampling that makes λblock^max small with partitions into well-conditioned blocks.Source: §2.1 · p. 3

2.2. Algorithms.

  • At each iteration, the framework samples a constraint subset and uses one of three extrapolated stepsize choices, including adaptive and Chebyshev-based rules.The analyzed extrapolation procedures use αk ≥ 2 and allow parallel projections onto several rows.Source: §2.2 · pp. 3–4

2.3. Convergence rates.

  • RBK’s expected linear rates expose matrix and submatrix geometry and block size; smaller λblock^max determines how much extrapolation helps.The analysis reports that extrapolated RBK can outperform basic Kaczmarz.Source: §2.3 · p. 4
  • For normalized matrices with λmin > 0, Chebyshev-based extrapolation attains the same condition-number-square-root rate as conjugate gradient.The paper describes this estimate as optimal for this class of iterative schemes.Source: §2.3 · pp. 4–5

3. Preliminaries.

The preliminaries formulate consistent linear systems and review Kaczmarz updates, their optimization interpretations, and convergence properties. They also introduce block-sampling schemes used in the later analysis.

3. Preliminaries.

  • The linear-system problem is presented through least-squares, least-norm, and dual quadratic formulations, with primal and dual variables linked by x = A^T y.The solution set is X = {x : Ax = b}, and the text defines projections onto X.Source: §3 · p. 5

3.1. Basic Kaczmarz algorithm.

  • Basic Kaczmarz selects a row and projects the current estimate onto its hyperplane, with αk = 1 giving the basic update.The method requires O(n) cost per iteration and storage.Source: §3.1 · p. 5

3.2. Interpretations.

  • Randomized Kaczmarz is equivalent to a stochastic-gradient step on the primal finite-sum problem or a randomized-coordinate-descent step on the dual problem.The text relates the primal and dual variables by x = A^T y.Source: §3.2 · pp. 5–6

3.3. Convergence properties.

  • Random row selection yields an expected linear convergence estimate, while ill-conditioned problems can converge slowly with constant stepsizes in (0, 2).The text presents block variants with extrapolated stepsizes larger than 2 as a way to accelerate convergence.Source: §3.3 · p. 6

3.4. Preliminary probability results.

  • The preliminaries describe uniform sampling of a fixed number of unique rows and partition sampling with probabilities uniform across blocks or proportional to block Frobenius norms.For equal-sized blocks and normalized A, the two partition probabilities coincide.Source: §3.4 · p. 7

4. Randomized block Kaczmarz algorithms.

This section develops and analyzes randomized block Kaczmarz methods that use subsets of rows and extrapolated stepsizes, including constant and adaptive choices. It establishes expected linear convergence tied to the geometry of the system matrix and its submatrices, and examines how well-conditioned blocks and row diversity relate to the methods’ effectiveness.

4. Randomized block Kaczmarz algorithms.

  • RBK updates by combining projections onto several selected row constraints with weights and a stepsize, and general choices extend beyond its batch stochastic gradient and block coordinate descent interpretations.The weights are positive and sum to one; the paper states that general weights and stepsizes do not admit those interpretations.Source: §4 · pp. 7–8

4.1. Randomized block Kaczmarz algorithm with constant stepsize.

  • With a new constant extrapolated stepsize, RBK converges linearly in expectation at a rate depending on the geometry of A and its submatrices; well-conditioned blocks can give speed-up of approximately τ.The stated speed-up applies when λblock_max is much smaller than τ.Source: §4.1 · pp. 9–11

4.2. Randomized block Kaczmarz algorithm with adaptive stepsize.

  • An adaptive extrapolated stepsize avoids computing λblock_max while retaining expected linear convergence, and its analysis explains the observed practical efficiency of extrapolated block Kaczmarz.For uniform weights and normalized matrices, the adaptive stepsize is an online approximation of the constant extrapolated stepsize and is generally larger.Source: §4.2 · pp. 11, 13

4.3. When block Kaczmarz works?.

  • Well-conditioned blocks can yield a speed-up of approximately τ over basic Kaczmarz, and the row-sampling probability is key to achieving this through good row pavings.For normalized matrices, randomized row partitions are described as a way to obtain relatively small block-conditioning parameters.Source: §4.3 · p. 14
  • RBK is most effective when the row sampling partitions A into well-conditioned blocks; otherwise, the basic Kaczmarz method with τ = 1 can be used.The analysis gives an optimal batch size of order τ ∼ m/∥A∥2.Source: §4.3 · p. 14
  • For extrapolated stepsizes, condition (4.12) requires substantial row diversity for RBK to outperform basic Kaczmarz; identical rows maximize ∥A∥2 for normalized A.The maximal squared spectral norm is m when A has rank 1.Source: §4.3 · p. 14
  • RBK costs O(τn) per iteration, versus about O(τ^2n) for block projection Kaczmarz, which solves a least-squares problem; similar convergence rates for the latter were derived in.The cited block projection result uses stepsize α_k = 1.Source: §4.3 · p. 14

5. Randomized block Kaczmarz algorithm with Chebychev-based stepsize.

With Chebyshev-based extrapolated stepsizes, RBK has linear convergence in expectation when λmin(AAT)>0 and sublinear convergence when λmin(AAT)=0. The stepsizes are designed from Chebyshev polynomials under uniform or partition sampling of equal-sized blocks.

5.1. Case 1: λmin(AAT ) > 0.

  • For normalized A with λmin(AAT)>0, RBK with uniform or partition sampling has linear convergence in expectation.The theorem’s stepsizes are based on roots of a degree-k Chebyshev polynomial.Source: §5.1 · pp. 15–16
  • For λmin(AAT)>0, the stepsizes use the polynomial least deviating from zero on [ℓ,u] subject to Pk(0)=1.This polynomial is given in terms of a Chebyshev polynomial, and the stepsizes are its inverse roots.Source: §5.1 · p. 16
  • The λmin(AAT)>0 rate matches conjugate gradient’s rate and is optimal for this class, but does not depend on block size, so the authors usually sample single rows.The paper contrasts this with the weaker convergence criterion used for the theorem.Source: §5.1 · p. 16

5.2. Case 2: λmin(AAT ) = 0.

  • When λmin(AAT)=0, Chebyshev-based RBK has sublinear convergence for the residual of the normal system in expectation.The estimate is stated for sufficiently large k.Source: §5.2 · pp. 16–18
  • For λmin(AAT)=0, the stepsize design instead uses a degree-(k+1) polynomial constrained by Qk(0)=0 and Q′k(0)=1.The construction uses a root of a degree-(k+1) Chebyshev polynomial.Source: §5.2 · p. 17
  • The paper identifies this as its first use of Chebyshev-polynomial properties to accelerate RBK, while whether Theorem 5.1 holds in the stronger expected-norm criterion remains open.The Chebyshev-based RBK variant belongs to the Chebyshev semi-iterative class.Source: §5.2 · p. 18

Appendix (Chebyshev polynomials).

The appendix reviews Chebyshev polynomials and properties used in the paper’s stepsize construction. It gives their cosine representation and their minimal-deviation property on [-1,1].

Appendix (Chebyshev polynomials).

Loading 1902.09946v1…