Skip to main content
Seminar | Mathematics and Computer Science

Towards Practical Large-scale Least Squares Solvers with Iterative Right Random Sketching

LANS Seminar

Abstract: Solving the least squares problem is fundamental to many typical predictive techniques of today, such as 4D-Var and GLMs. Unfortunately, our increasing desire for more accurate predictions requires the use of more parameters and more data, which increases the computational difficulty of solving these problems. This increased difficulty arises from the high cost of moving data at a large scale. Using Krylov methods or Incremental QR ameliorates the issues arising from these memory costs when the matrix has either a high row or column dimension. These methods fail to be acceptable solutions when the system has both a high row and column dimension. In this case, Iterative Right Random Sketching (IRRS) appears to be a good solution because it can compress the number of columns into a more manageable dimension. However, for IRRS to work efficiently, its progress must be cheaply tracked and stopped.

In this talk, we introduce a novel technique for tracking and stopping the progress of such Iterative Right Random Sketching methods. It will establish theoretically and experimentally that our technique can track progress with high accuracy and stop progress with a user-specified risk of failure. Finally, using this progress tracking method, the presentation demonstrates how IRRS can facilitate solving a 4D-Var problem of about 0.76 TB in size using only 100 MB of memory.