Fast Monte-Carlo algorithms for finding low-rank approximations

In several applications, the data consists of an m x n matrix A and it is of interest to find an approximation D of a specified rank k to A where, k is much smaller than m and n. Traditional methods like the Singular Value Decomposition (SVD) help us find the "best" such approximation. However, these methods take time polynomial in m, n which is often too prohibitive. In this paper; we develop an algorithm which is qualitatively faster provided we may sample the entries of the matrix according to a natural probability distribution. Indeed, in the applications such sampling is possible. Our main result is that we can find the description of a matrix D* of rank at most k so that \\A - D*\\(F) less than or equal to min(D.rank(D)less than or equal to k) \\A - D\\(F) + epsilon\\A\\(F) holds with probability at least 1 - delta. (For any matrix M, \\M\\(2)(F) denotes the sum of the squares of all the entries of M.) The algorithm takes time polynomial in k, 1/epsilon, log (1/delta) only, independent of m, n.