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!