ARC Colloquium: David Woodruff, IBM Almaden Research Center, San Jose, CA.

Event Details
  • Date/Time:
    • Friday April 26, 2013 - Saturday April 27, 2013
      10:00 am - 9:59 am
  • Location: Klaus 1116
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:


Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

Title: Low Rank Approximation and Regression in Input Sparsity Time


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. We have implemented our algorithms, and preliminary results suggest the algorithms are competitive in practice.

Joint work with Ken Clarkson.


Additional Information

In Campus Calendar

College of Computing, School of Computer Science, School of Computational Science and Engineering, ARC

Invited Audience
No audiences were selected.
No categories were selected.
No keywords were submitted.
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Apr 11, 2013 - 6:39am
  • Last Updated: Oct 7, 2016 - 10:03pm