Faster Least Squares Optimization

Understand

We investigate iterative methods with randomized preconditioners for solving overdetermined least-squares problems, where the preconditioners are based on a random embedding of the data matrix.

• We consider two distinct approaches: the sketch is either computed once (fixed preconditioner), or, the random projection is refreshed at each iteration, i.e., sampled independently of previous ones (varying preconditioners).
• Although fixed sketching-based preconditioners have received considerable attention in the recent literature, little is known about the performance of refreshed sketches.
• For a fixed sketch, we characterize the optimal iterative method, that is, the preconditioned conjugate gradient as well as its rate of convergence in terms of the subspace embedding properties of the random embedding.