Collection Nexus Trimester - 2016 - Central Workshop
Organizer(s)
Date(s)
03/05/2024
Sketching as a Tool for Numerical Linear Algebra and Recent Developments
We give near optimal algorithms for regression, low rank approximation, and robust variants of these problems. Our results are based on the sketch and solve paradigm, which is a tool for quickly compressing a problem to a smaller version of itself, for which one can then run a slow algorithm on the smaller problem. These lead to the fastest known algorithms for fundamental inference problems, which run in time proportional to the number of non-zero entries of the input. We first give algorithms for least squares regression, and robust variants such as l_p regression and M-Estimator loss functions. Then we give algorithms for approximate singular value decomposition, and robust variants such as minimizing sum of distances to a subspace, rather than sum of squared distances. The talk is based on work covered in my monograph of the same title in NOW Publishers, 2014, together with work in SODA ’15 and FOCS ’15 with Ken Clarkson.
