Adaptive Sketch-and-Project Methods for Solving Linear Systems

Understand

We present new adaptive sampling rules for the sketch-and-project method for solving linear systems.

• To deduce our new sampling rules, we first show how the progress of one step of the sketch-and-project method depends directly on a sketched residual.
• Based on this insight, we derive a 1) max-distance sampling rule, by sampling the sketch with the largest sketched residual 2) a proportional sampling rule, by sampling proportional to the sketched residual, and finally 3) a capped sampling rule.
• The capped sampling rule is a generalization of the recently introduced adaptive sampling rules for the Kaczmarz method.