An efficient greedy quasi block coordinate descent method for solving linear least-squares problems

We study to improve the computational efficiency of block coordinate descent methods for linear least-squares problems. Specifically, we propose a quasi block coordinate descent (QBCD) iteration scheme to accelerate the implementation of the classical block coordinate descent iteration. By further introducing a random partition based greedy strategy to determine the working block, we develop a greedy QBCD method. Convergence analysis shows that the new method converges linearly. Theoretical and numerical results further demonstrate that the convergence speed is satisfactory, which leads to superior computational efficiency.