DIMACS Theoretical Computer Science Seminar

Title: The CUR Matrix Decomposition and its Applications to Algorithm Design and Massive Data Set Analysis

Speaker: Petros Drineas, Rensselaer Polytechnic Institute

Date: November 29, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


Motivated by applications in algorithm design and massive data set analysis, we are interested in developing and analyzing fast Monte Carlo algorithms for performing useful computations on large matrices. Of particular interest is the compressed approximate CUR matrix decomposition. After describing the CUR matrix decomposition, we describe how it can be used to design an improved approximation algorithm for the Max-Cut problem. We then describe how extensions of the CUR decomposition may be used for improved kernel-based statistical learning and for the efficient approximation of massive tensor-based data sets.

This is joint work with Michael Mahoney and Ravi Kannan.