Technion, IEM faculty - Operations Research seminar Speaker: David Woodruff Title: Fast Robust Regression and Hyperplane Fitting Date: 04/04/2011 Time: 12:30 Place: Bloomfield-527 The abstract for this talk can currently be accessed at the web address: <http://www.math.technion.ac.il/~techm/temp/20110404WOOD.pdf> It will be available for up to a month after the date of the activity. Abstract: I will talk about the l_1-regression problem, namely given an n x m matrix A and an n x 1 column vector b, together with a parameter eps > 0, output a vector x' in R^m for which |Ax'-b|_1 <= (1+eps) min_x |Ax-b|_1 with good probability. In practice, l_1-regression is more robust than least squares regression. We focus on the heavily over constrained version. We give a much faster algorithm for this problem using a new embedding result for subspaces of l_1. We also give a much faster algorithm for the l_1 best fit hyperplane problems. Our algorithms are also the first that are implementable in a single pass in a data stream in small space. These results are motivated by practical problems in image analysis, spam detection, and statistics, where the l_1-norm is used in studies where outliers may be safely and effectively ignored. Joint work with Christian Sohler (STOC, 2011). --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> To see today's activities and other future and past activities go to <http://www.math.technion.ac.il/~techm/today.html> Announcement from: <levinas@techunix.technion.ac.il> ----------