We are interested in developing and analyzing fast Monte Carlo algorithms for
performing useful computations on extremely large matrices. Examples of such
computations include matrix multiplication, the computation of the Singular
Value Decomposition of a matrix, the computation of compressed approximate
decompositions of a matrix, and testing the feasibility or infeasibility of
a linear program. We present a Pass-Efficient model of data streaming
computation in which our algorithms may naturally be formulated and present
algorithms that are efficient within this model for each of the four types of
matrix operations mentioned previously. Of particular interest is the
compressed approximate CUR matrix decomposition. After describing the CUR
decomposition, we describe how extensions to it 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 Petros Drineas and
Ravi Kannan.
Copyright. All Rights Reserved.