Saturday, July 15, 2006

Linear L_2 Regression: Past and Present

The linear least squares fit problem is the following. Given an n X d, n >d, matrix A of real values and a d dimensional vector b, minimize ||b-Ax||_2. It has a past most of us know. It can be solved in O(nd^2) time. Petros Drineas, Michael Mahoney and I had a SODA paper that showed that if you sampled poly(1/\eps,d) rows from A and b and solved the induced problem, one gets 1+\eps approximation to the problem. Unfortunately, the sampling was somewhat complicated and could not be done in o(nd^2) time. We knew that instead of sampling, if one "sketches" A, that is, takes poly(1/\ep,d) random linear combinations of rows of A and b, the same claim would follow, but it still did not improve the running time. Tamás Sarlós makes a very nice observation in his paper in upcoming FOCS that by plugging in Fast Johnson-Lindenstrauss Transform of Ailon and Chazelle from STOC06 and squeezing the bounds, this sketching method in fact can be run in O(nd log n) time. Kol Hakavod, Tamás!


Anonymous Anonymous said...

Who knows where to download XRumer 5.0 Palladium?
Help, please. All recommend this program to effectively advertise on the Internet, this is the best program!

12:26 PM  

Post a Comment

<< Home