Random reordering in SOR-type methods (Q522242)

To solve \(Ax=b\) in least squares sense, the successive overrelaxation iteration can be applied to \(B=AA^*\). The method uses a decomposition \(B=L+D+L^*\) with \(L\) strictly lower triangular and \(D\) diagonal. Classical SOR then corresponds to successive projections on the coordinate directions in a cyclic repetition so that convergence depends on the order in which the equations are given. This paper analyses convergence of two randomized versions. Either the order is randomized in each iteration step (shuffled) or randomized once, followed by standard iterations (preshuffle). Improved convergence estimates (for the expected energy norm) are obtained for these two methods. The analysis is based on the existence of an absolute constant \(C\) in \(\|L_\sigma\|\leq C\|B_\sigma\|\) (where index \(\sigma\) refers to a permutation \(\sigma\) of the rows of \(B\)), which in turn depends on a proof of the Anderson paving conjecture (see for example [\textit{P. G. Casazza} and \textit{J. C. Tremain}, in: New trends in applied harmonic analysis. Sparse representations, compressed sensing, and multifractal analysis. Cham: Birkhäuser/Springer. 191--213 (2016; Zbl 1343.42040)] for details about the latter).