*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Monday, November 9, 2015
Klaus 1116 West – 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Input Sparsity Time Algorithms for Robust Regression and Robust Low Rank Approximation
Abstract:
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.
