Sketch & Project Methods for Linear Feasibility Problems: Greedy Sampling & Momentum

Abstract

We develop two greedy sampling rules for the $\textit{Sketch & Project}$ method for solving linear feasibility problems. The proposed greedy sampling rules generalize the existing max-distance sampling rule and uniform sampling rule and generate faster variants of $\textit{Sketch & Project}$ methods. We also introduce greedy capped sampling rules that improve the existing capped sampling rules. Moreover, we incorporate the so-called heavy ball momentum technique to the proposed greedy $\textit{Sketch & Project}$ method. By varying the parameters such as sampling rules, sketching vectors- we recover several well-known algorithms as special cases, including $\textit{Randomized Kaczmarz}$ (RK), $\textit{Motzkin Relaxation}$ (MR), $\textit{Sampling Kaczmarz Motzkin}$ (SKM). We also obtain several new methods such as $\textit{Randomized Coordinate Descent}$, $\textit{Sampling Coordinate Descent}$, $\textit{Capped Coordinate Descent}$ etc. for solving linear feasibility problems. We provide global linear convergence results for both the basic greedy method and the greedy method with momentum. Under weaker conditions, we prove $\mathcal{O}(\frac{1}{k})$ convergence rate for the Cesaro average of sequences generated by both methods. We extend the so-called certificate of feasibility result for the proposed momentum method that generalizes several existing results. To back up the proposed theoretical results, we carry out comprehensive numerical experiments on randomly generated test instances as well as sparse real-world test instances. The proposed greedy sampling methods significantly outperform the existing sampling methods. And finally, the momentum variants designed in this work extend the computational performance of the $\textit{Sketch & Project}$ methods for all of the sampling rules.