### 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

Abstract:

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.