Pass efficient algorithms for approximating large matrices

1 Summary In many applications, an m \Θ n matrix A is stored on disk and is too large to be read into RAM. Our main result is a succinct easily computed approximation A0 to A which is also an m \Θ n matrix. To be precise, A0 has the following properties: (s below is a natural number under our choice. It usually will be O(1).) (i) A0 = CU R, where C is an m \Θ s matrix consisting of s (randomly picked) columns of A; R is an s \Θ n matrix consisting of s (randomly picked) rows of A and U is an s \Θ s matrix computed from C; R. (ii) C; U; R can be constructed after making two passes through the whole matrix A from disk, (iii) using RAM space and additional time (in addition to the two full passes) O(m + n + the number of nonzero entries in C; R) and (iv) satisfies max x:jxj=1 j(A \Γ A0)xj2 ^ ffl X