The CUR Matrix Decomposition with Applications

Motivated by applications in massive data set analysis and algorithm design,
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 focus on applications
of the CUR decomposition to the analysis of large scientific data sets. In
particular, we 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 may then be coupled with more
traditional and/or refined methods of data set analysis in order to construct
in a principled manner a “sketch” of an extremely large data set and then to
perform more refined field-specific analysis on the sketch; recent work along
this direction will be discussed.