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.
Presentation (PDF File)
Video of Talk (RealPlayer File)
Copyright. All Rights Reserved.