Volume Sampling and Spectral Equalization in Randomized Alternating Projections
Abstract
We study a family of randomized alternating projection methods that alternate among subspaces spanned by subsets of n vectors from a prescribed set. We derive an explicit characterization of performance bounds when these subspaces are sampled with probabilities proportional to the volumes subtended by the vectors in their corresponding subsets. For each n, the bound is obtained through an explicit nonlinear transformation of the spectrum of an associated matrix. Our analysis reveals an explicit spectral equalization mechanism that drives the spectrum toward improved conditioning as n increases, establishing an unexpected connection between volume sampling and the Cayley-Hamilton theorem. Furthermore, we introduce a computationally efficient uniform sampling scheme that achieves comparable theoretical guarantees through a specific relaxation strategy. Empirical results show that this relaxation method achieves convergence rates comparable to, and often better than, volume sampling, while avoiding the infeasibility of volume sampling at large scale. Besides the randomized Kaczmarz, these results also directly apply to randomized Gauss-Seidel and coordinate descent methods.
Related
- Acceleration of the Method of Alternating Projections on subspaces by GMRES
- Deeply unrolled alternating projections for phase retrieval
- A new convergence proof for an iterative scheme for elliptic Cauchy problems based on alternating orthogonal projections
- Polynomial Acceleration of Alternating Projections: Chebyshev Acceleration, Convergence Rates, and Retractions
- Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning
BibTeX
@misc{entezari2026volume,
title = {{Volume Sampling and Spectral Equalization in Randomized Alternating Projections}},
author = {Alireza Entezari and Arunava Banerjee and Leila Kalantari},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12346},
eprint = {2610.12346},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12346},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Volume Sampling and Spectral Equalization in Randomized Alternating Projections
AU - Alireza Entezari
AU - Arunava Banerjee
AU - Leila Kalantari
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12346
UR - https://arxiv.org/abs/2610.12346
AB - We study a family of randomized alternating projection methods that alternate among subspaces spanned by subsets of n vectors from a prescribed set. We derive an explicit characterization of performance bounds when these subspaces are sampled with probabilities proportional to the volumes subtended by the vectors in their corresponding subsets. For each n, the bound is obtained through an explicit nonlinear transformation of the spectrum of an associated matrix. Our analysis reveals an explicit spectral equalization mechanism that drives the spectrum toward improved conditioning as n increases, establishing an unexpected connection between volume sampling and the Cayley-Hamilton theorem. Furthermore, we introduce a computationally efficient uniform sampling scheme that achieves comparable theoretical guarantees through a specific relaxation strategy. Empirical results show that this relaxation method achieves convergence rates comparable to, and often better than, volume sampling, while avoiding the infeasibility of volume sampling at large scale. Besides the randomized Kaczmarz, these results also directly apply to randomized Gauss-Seidel and coordinate descent methods.
ER -