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>
----------