Volume Sampling and Spectral Equalization in Randomized Alternating Projections

DOI10.48550/arXiv.2610.12346MaRDI QIDQ7374651arXivFDO

Authors Alireza Entezari, Arunava Banerjee, Leila Kalantari

Publication date 8 October 2026

Published in arXiv

Tldr We study alternating projection methods with volume sampled subspaces, deriving explicit performance bounds through a spectral equalization mechanism that connects volume sampling to the Cayley-Hamilton theorem. We introduce a computationally efficient uniform sampling scheme achieving comparable guarantees with an unexpected relaxation strategy.

Full work available at URL https://doi.org/10.48550/arXiv.2610.12346

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Iterative numerical methods for linear systems (65F10) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Randomized algorithms (68W20)

arXiv classification

math.NA

Cites work

• A randomized coordinate descent method with volume sampling
• A randomized Kaczmarz algorithm with exponential convergence
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• An accelerated randomized Kaczmarz algorithm
• Block-iterative methods for consistent and inconsistent linear equations
• Breaking Locality Accelerates Block Gauss-Seidel
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Efficient volume sampling for row/column subset selection
• Error bounds for the method of alternating projections
• Extensions of the Ostrowski-Reich theorem for SOR iterations
• Fast Monte-Carlo algorithms for finding low-rank approximations
• Global Asymptotic Rates Under Randomization: Gauss-Seidel and Kaczmarz
• Iterative Methods for Sparse Linear Systems
• Iterative solution of large sparse systems of equations
• Matrix approximation and projective clustering via volume sampling
• On convergence rate of the randomized Kaczmarz method
• On the rate of convergence of the alternating projection method in finite dimensional spaces
• Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Practical and mathematical aspects of the problem of reconstructing objects from radiographs
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• Randomized block Kaczmarz with volume sampling: Momentum acceleration and efficient implementation
• Randomized iterative methods for linear systems
• Randomized methods for linear constraints: convergence rates and conditioning
• Reverse iterative volume sampling for linear regression
• Sampling from large matrices
• Solving Dense Linear Systems Faster than via Preconditioning
• The rate of convergence for the method of alternating projections. II

This page was built for publication: Volume Sampling and Spectral Equalization in Randomized Alternating Projections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7374651)