Summary: We consider the problem of approximating a given matrix by another matrix of specified rank , which is smaller than and . The singular value decomposition (SVD) can be used to find the ‘best’ such approximation. However, it takes time polynomial in , which is prohibitive for some modern applications. In this article, we develop an algorithm that is qualitatively faster, provided we may sample the entries of the matrix in accordance with a natural probability distribution. In many applications, such sampling can be done efficiently. Our main result is a randomized algorithm to find the description of a matrix of rank at most so that
holds with probability at least (where is the Frobenius norm). The algorithm takes time polynomial in , , only and is independent of and . In particular, this implies that in constant time, it can be determined if a given matrix of arbitrary size has a good low-rank approximation.