Abstract: Solving systems of linear equations has numerous applications across many areas, from data science and machine learning, to scientific computing, engineering and more. When these systems are too large to solve directly, iterative refinement methods such as conjugate gradient have proven to be a powerful alternative. The computational cost of these methods can be significantly affected by a problem-dependent condition number, which is often addressed by combining the iterative solver with a preconditioner, i.e., an easy to invert approximation of the original system. However, constructing a good preconditioner can still be very expensive, which leads to an undesirable trade-off between the cost of preconditioning and the cost of solving the linear system.

In this talk, I will present new stochastic iterative methods for solving linear systems based on the so-called Sketch-and-Project paradigm, which can reduce the condition number of the system without having to precondition it. This approach is based on the following phenomenon: Whenever the spectral structure of a linear system is amenable to constructing a strong preconditioner via low-rank matrix approximation, we can design a Sketch-and-Project solver that will implicitly take advantage of this to find the solution faster. In particular, I will show how this leads to solving an n x n linear system with at most k large (outlying) singular values in ~O( n^2 + n k^2 ) arithmetic operations, which is faster than the ~O( n^2 k ) cost of constructing a good preconditioner for this system.


Contact: Robert Krasny