A Novel Matrix Decomposition with Applications to Algorithm Design and Massive Data Set Analysis

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 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; although this is the second part of a two-part talk we are giving, this talk will be self-contained.
Department of Computer Science,
Rensselaer Polytechnic Institute