David P. Woodruff - IBM
Monday, November 9, 2015
Klaus 1116 West – 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Input Sparsity Time Algorithms for Robust Regression and Robust Low Rank Approximation
We give near optimal algorithms for regression and low rank approximation in the robust case. For regression, we give algorithms generalizing l_p regression to M-Estimator loss functions, such as the Huber measure, which enjoys the robustness properties of l_1 as well as the smoothness properties of l_2. For low rank approximation, we give new algorithms generalizing the singular value decomposition to sum of p-th powers of distances, and M-estimator loss functions applied to the distances. Some problems here are arguably even more fundamental than the SVD itself, such as given a set of points, find a line which minimizes the sum of distances of the points to the line, rather than the sum of squared distances. These measures are less sensitive to outliers and we show they can be computed approximately in time proportional to the number of non-zeros of the input matrix. We also discuss hardness results in the low rank approximation setting.