**A relative-error CUR decomposition for
matrices and its data applications **

**Michael W. Mahoney **

**Yahoo Research**

Much recent work in the Theoretical
Computer Science, Linear Algebra, and Machine Learning has considered matrix
decompositions of the following form: given an m-by-n matrix A, decompose it as
a product of three matrices, C, U, and R, where C consists of a few (typically a
constant number of) columns of A, R consists of a few (typically a constant
number of) rows of A, and U is a small carefully constructed matrix that
guarantees that the product CUR is "close" to A. Applications of such
decompositions include the computation of compressed "sketches" for large
matrices in a pass-efficient manner, matrix reconstruction, speeding up
kernel-based statistical learning computations, sparsity-preservation in
low-rank approximations, and improved interpretability of data analysis methods.
In this talk we shall discuss various choices for the matrices C, U, and R that
are appropriate in different application domains. The main result will be an
algorithm that computes matrices C, U, and R such that the (Frobenius) norm of
the error matrix A - CUR is almost minimal. Although this talk will build on
ideas from the tutorial given earlier in the day, this talk will be entirely
self-contained.