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:
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   <> 
To see today's activities and other future and past activities go to
Announcement from:  <>