When the data is large, or comes in a streaming way, randomized iterative methods provide an efficient way to solve a variety of problems, including solving linear systems, finding least square solutions, solving feasibility problems, and others. Randomized Kaczmarz algorithm for solving over-determined linear systems is one of the popular choices due to its efficiency and its simple, geometrically intuitive iterative steps.
In challenging cases, for example, when the condition number of the system is bad, or some of the equations contain large corruptions, the geometry can be also helpful to augment the solver in the right way. I will discuss our recent work with Michal Derezinski and Jackie Lok on Kaczmarz-based algorithms that use external knowledge about the linear system to (a) accelerate the convergence of iterative solvers, and (b) enable convergence in the highly corrupted regime.