Pass efficient algorithms for approximating large matrices
Petros Drineas, Ravi Kannan · 2003
1 Summary In many applications, an m \\Theta 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 \\Theta 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 \\Theta s matrix consisting of s (randomly picked) columns of A; R is an s \\Theta n matrix consisting of s (randomly picked) rows of A and U is an s \\Theta 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 \\Gamma A0)xj2 ^ ffl X