Journal Papers (Ex: Least Squares Approximation)

The world falls into two categories: those who write journal papers, and those who don't. Like in all such statements, alas, there are notes: some first write journal versions and cut them down for the conf; some write journal versions of "important" results, "invited" papers, or papers with students or whatever refinement one finds suitable to fit their dataset of journal publications.

Recently I made a joint journal submission with Petros Drineas, Michael Mahoney and Tamas Sarlos. Given an n X d matrix A and a d dimensional vector b, the least squares problem is to minimize ||Ax-d||_2 over all d dimensional vectors x. Methods dating back to Gauss and Legendre find a solution in O(n d^2) time. The problem can be reduced to (n/d) MM(d) where MM(d) is the time to multiply two d X d matrices, which means the best running time is O(n d^{1+c}) for some ever-dwindling constant c.

We show how to get (1+ε) approximation in time O(n d log(d/ε,n)). This combines our SODA06 result on constructing a coreset for the problem with the Fast Johnson-Lindenstrauss of Ailon-Chazelle used by Sarlos in his FOCS06 paper into what is the best result we could obtain. The full version is at the arxiv, meandering through the journal process. Comments welcome.