A unified convergence analysis of random sketch methods for rank deficient linear systems
摘要
For solving large-scale rank deficient linear systems arising from the practical applications, we present a unified convergence analysis for projection- and reflection-based iterative methods by decomposing iterates into range and null subspaces. Meanwhile, a novel class of sketch-and-reflect iteration methods is constructed by employing random Householder reflection transformation at each iteration. For consistent systems, the convergence analysis demonstrates that the proposed method converges to the minimum norm solution in the range subspace at an expected rate, thereby elucidating the slower convergence of reflection-based methods compared to projection-based methods. To accelerate convergence, the proposed method is restarted by setting the centroid of the ensuing collection of points as the starting point for the subsequent iterations. For inconsistent systems with noisy right-hand side, we prove that the error in expectation depends on the random reflection matrix with the same rate as in the noise-free case. Numerical experiments on the synthetic dense and practical sparse matrices validate the efficiency of our methods.