On subspace-constrained preconditioning for randomized iterative methods
For researchers working on iterative linear system solvers, this provides a more efficient preconditioning technique that eliminates the need for explicit preconditioner construction.
The paper refines subspace-constrained preconditioning for randomized iterative solvers, achieving linear convergence in expectation and avoiding full-rank assumptions by using a QR-like factorization that reduces the problem to a smaller system with favorable singular value distribution.
In this paper, we further investigate and refine the subspace-constrained preconditioning technique to enhance the theoretical and numerical convergence properties of randomized iterative methods for solving linear systems. In particular, we design a QR-like factorization that transforms the original linear system into an equivalent block-orthogonal form, thus avoiding the full-rank assumptions adopted in existing work. Moreover, this reformulation reduces the problem to solving a smaller linear system with a favorable singular value distribution, provided an appropriate initial point is employed. The proposed framework can be implemented implicitly within the iteration and does not require explicitly constructing either a preconditioner matrix or a preconditioned linear system, which eliminates the prohibitive cost of forming a fully preconditioned system. Furthermore, we construct orthogonalized search directions from stochastic gradients and develop accelerated variants of the framework. We prove that the proposed algorithmic framework converges linearly in expectation. Numerical experiments demonstrate the benefits of the proposed preconditioning strategy.