On the Relation Between the Randomized Extended Kaczmarz Algorithm and Coordinate Descent
This provides a theoretical efficiency comparison for practitioners choosing between EK and CD for least-squares problems.
The paper compares the randomized extended Kaczmarz (EK) algorithm and randomized coordinate descent (CD) for solving overdetermined least-squares problems, proving that CD requires fewer operations to meet residual-based termination criteria. For general least-squares, a two-step approach (CD then Kaczmarz) is shown to be more efficient than EK.
In this note we compare the randomized extended Kaczmarz (EK) algorithm and randomized coordinate descent (CD) for solving the full-rank overdetermined linear least-squares problem and prove that CD needs less operations for satisfying the same residual-related termination criteria. For the general least-squares problems, we show that running first CD to compute the residual and then standard Kaczmarz on the resulting consistent system is more efficient than EK.