Low Rank Approximation and Regression in Input Sparsity Time

David Woodruff, IBM Research, USA

Abstract:
We improve the running times of algorithms for least squares regression and low-rank approximation to account for the sparsity of the input matrix. Namely, if nnz(A) denotes the number of non-zero entries of an input matrix A:

  • we show how to solve approximate least squares regression given an n x d matrix A in nnz(A) + poly(d log n) time
  • we show how to find an approximate best rank-k approximation of an n x n matrix in nnz(A) + n*poly(k log n) time

All approximations are relative error. Previous algorithms based on fast Johnson-Lindenstrauss transforms took at least ndlog d or nnz(A)*k time.

Joint work with Ken Clarkson.

Biography:
David Woodruff joined the algorithms and complexity group at IBM Almaden in 2007 after completing his Ph.D. at MIT in theoretical computer science. His interests are in compressed sensing, communication, numerical linear algebra, sketching, and streaming.