Volume Sampling and Spectral Equalization in Randomized Alternating Projections

1 Introduction

• For stationary iterative methods, convergence is governed by the iteration matrix’s spectral radius, whose relation to system properties often requires structural assumptions.Examples include symmetry, positive definiteness, or consistent ordering.Source: §1 · p. 1
• Projection-method bounds rely on geometric quantities such as principal angles, are often difficult to evaluate, and do not directly connect convergence to system spectra.Source: §1 · p. 2
• Randomized Kaczmarz with row probabilities proportional to squared Euclidean norms converges exponentially in expectation, with rates expressed through A’s smallest singular value or scaled condition number.The approach was subsequently extended to coordinate descent, yielding randomized Gauss–Seidel [2].Source: §1 · p. 2
• Volume sampling yields an exact expected-projector characterization and a spectral transformation that progressively equalizes the singular-value spectrum as block size increases.The transformation is described by a recursive form of the Cayley–Hamilton theorem.Source: §1 · p. 2
• A relaxed uniform sampling scheme approximates volume sampling with comparable theoretical guarantees, while experiments report that it consistently outperforms volume sampling.The relaxation addresses the combinatorial limits of applying volume sampling to large-scale problems.Source: §1 · p. 2

2 Preliminaries

• The notation uses bold lowercase letters for vectors, bold uppercase letters for matrices, λ_min(A) for the smallest eigenvalue, I for the identity, and tr(A) for trace.Source: §2 · p. 3
• For a consistent system Ax = b, Kaczmarz iterates by orthogonally projecting onto affine hyperplanes defined by A’s rows and the corresponding entries of b.The iterates converge to a point in the intersection of those hyperplanes.Source: §2 · p. 3
• The block setup considers submatrices formed from n rows and projects onto the affine subspace defined by each selected submatrix and its corresponding right-hand-side entries.Source: §2 · p. 3
• The randomized methods select row-subset matrices according to designed probability distributions, and the block projection update uses the Moore–Penrose pseudoinverse.Source: §2 · p. 3

3.1 Volume Sampling

• Squared-volume sampling of row subsets yields convergence rates characterized by a nonlinear transformation of the spectrum of A^T A for each subset size n > 1.Theorem 1 generalizes the construction to arbitrary subset sizes, with the rate parameter determined recursively from the eigenvalues.Source: §3.1 · pp. 3–4

3.2 Spectral Equalization

• As n increases, the transformed spectrum moves toward equality, reaching complete equalization at n = N, while the convergence parameter µ_n increases toward 1.Figure 1 illustrates the normalized spectra and the convergence-parameter trend for geometric, polynomial, and clustered initial spectra.Source: §3.1 · p. 4, §3.2 · pp. 4–5, Figure 1 · p. 5

3.3 Relaxed Uniform Sampling

• Relaxed uniform sampling avoids the combinatorial burden of exact volume sampling while retaining a comparable convergence guarantee, but its theoretical bound is weaker.The passage reports that the relaxed iterations consistently outperform volume-sampling iterations experimentally, while µ_n is reduced by a factor in the bound.Source: §3.3 · pp. 5–6
• The relaxation can maintain its normalization online: updating the running maximum squared volume before each step ensures ω_A_n ≤ 2 without precomputing the maximum over all subsets.The squared volume is obtained as a by-product of the projection step, which solves an n × n system.Source: §3.3 · p. 6

4 Proofs of the Main Results

• Independent draws yield geometric convergence, with rate parameter µ_n determined by the smallest eigenvalue of the expected projector.The one-step conditional progress bound is iterated from any initial point.Source: §4 · p. 6

4.1 Recursive Expansion of Orthogonal Projectors

• An orthogonal projector onto an n-vector span can be expanded using rank-one and leave-one-out projectors, with coefficients tied to angles and squared volumes.The expansion supplies a recursive basis for the later expected-projector calculation.Source: §4.1 · pp. 7–8
• The quasi-projector scales the orthogonal projector by squared volume for independent vectors and is zero for linearly dependent vectors.Its adjugate-Gram construction remains defined for dependent vector sets.Source: §4.1 · p. 8

4.2 Combinatorial Analysis

• For volume sampling, the expected projector is obtained by normalizing the sum of subset quasi-projectors, whose recursion reduces to a formula in A and n.The normalization uses the trace of Φ_n, and row permutations reduce ordered selections to n-subsets.Source: §4.2 · pp. 8–10
• The recursion from Φ_1 = A^T A to Φ_N = I is the recursive Cayley–Hamilton form used to obtain characteristic-polynomial coefficients.Unwinding it gives the lowest n terms of the characteristic polynomial in powers and traces of Φ_1.Source: §4.2 · p. 10
• For relaxed uniform sampling, the expected quasi-projector is related to the mean squared subset volume, extending the volume-sampling results to a uniform subset distribution.The proof develops a conditional expected-progress expression for that distribution.Source: §4.2 · pp. 10–11

5 Numerical Experiments

• The small-scale experiments compare observed convergence with theoretical parameters where exact volume-sampling probabilities can be computed.The numerical validation also includes larger problems, where exact volume sampling is computationally impractical.Source: §5.1 · p. 11, §5 · p. 11

5.1 Small-Scale Comparison

• Small-scale tests use row-normalized Gaussian, Parter, Prolate, and Wilkinson matrices with subset sizes n = 1, 2, 4 and compare mean relative squared error over 250 trajectories.The systems are consistent, and uniform and relaxed uniform methods use identical sampled subset sequences within each trial.Source: §5.1 · p. 11
• In all reported experiments, relaxed uniform sampling converges faster than volume sampling, although its theoretical bound is weaker.For the small-scale matrices, both theoretical parameters increase with subset size, but monotonicity of the relaxed-sampling parameter is not guaranteed generally.Source: §5.1 · p. 12, Figure 2 · p. 12

5.2 Large-Scale Experiments

• Large-scale tests use fanbeam 64 and well1850, comparing uniform and relaxed uniform sampling with matched subset sequences over ten trials and 500 equivalent row passes.The matched initial iterates and exact solutions isolate the effect of adaptive relaxation.Source: §5.2 · p. 13
• At the same computational time, relaxed uniform sampling generally reaches lower error than uniform sampling on both large sparse systems, with a larger advantage at larger subset sizes.The observed iteration-count reduction is preserved in wall-clock performance.Source: §5.2 · p. 13

• The representation has exact spectral coefficients but leads to a tractable Loewner lower bound; gives selected-spectrum guarantees rather than the full spectral transformation.The result uses a tail condition and a top-k-deflation interpretation.Source: §6 · pp. 14–15
• The exact expected-projector spectrum determines μ_n and the per-iteration factor 1−μ_n, with every increase in volume-sampled block size improving the guaranteed rate.This monotonicity is a structural property of volume sampling, not a generic consequence of batching.Source: §6 · p. 15
• The complete spectrum enables asymptotic analysis using the two smallest expected-projector eigenvalues, information unavailable from lower bounds on μ_n alone.The expected-progress inequality is described as a conservative estimate of observed convergence.Source: §6 · p. 15
• The characterization strengthens analysis of volume-sampled coordinate descent and can support accelerated randomized block methods whose convergence depends on the expected projector.The coordinate-descent connection follows from its equivalence to randomized block Gauss–Seidel under the standard primal–dual correspondence.Source: §6 · p. 15
• Volume sampling makes expected convergence depend on global spectral properties, rather than the conditioning of the worst block in a prescribed partition.Fixed partitions can produce worst-block conditioning only weakly related to the spectrum of the full matrix.Source: §6 · p. 16
• Exact volume sampling remains costly for large-scale problems, while relaxed uniform sampling avoids that overhead and retains a theoretical contraction guarantee close to exact volume sampling.The cited computational costs include determinant evaluations, repeated factorizations, and preprocessing.Source: §6 · p. 16
• Experiments report that relaxed uniform sampling consistently outperforms existing methods in wall-clock time; the authors identify spectral equalization, approximated by relaxation, as volume sampling’s principal benefit.The relaxed strategy combines inexpensive uniform subset selection with a relaxation.Source: §6 · p. 16