Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition

摘要

In many applications, the data consist of ( or may be naturally formulated as) an m x n matrix A which may be stored on disk but which is too large to be read into random access memory ( RAM) or to practically perform superlinear polynomial time computations on it. Two algorithms are presented which, when given an m x n matrix A, compute approximations to A which are the product of three smaller matrices, C, U, and R, each of which may be computed rapidly. Let A' = CUR be the computed approximate decomposition; both algorithms have provable bounds for the error matrix A - A'. In the first algorithm, c columns of A and r rows of A are randomly chosen. If the m x c matrix C consists of those c columns of A ( after appropriate rescaling) and the r x n matrix R consists of those r rows of A ( also after appropriate rescaling), then the c x r matrix U may be calculated from C and R. For any matrix X, let parallel to X parallel to(F) and parallel to X parallel to(2) denote its Frobenius norm and its spectral norm, respectively. It is proven that