A residual-based surrogate hyperplane extended Kaczmarz algorithm for large least squares problems

We present a simple yet efficient two-stage extended Kaczmarz-type algorithm for solving large least squares problem. During each stage, the current iterate is projected onto a surrogate hyperplane instead of a single one, yielding remarkable reduction in the number of iteration steps and computational time. We prove that the proposed algorithm converges to the unique least-norm least-squares solution with a convergence factor asymptotically smaller than that for some existing randomized extended Kaczmarz-type algorithms. Numerical examples show that the new algorithm outperforms several counterparts for various test problems.