*(English)*Zbl 1125.65005

Summary: We consider the problem of approximating a given $m\times n$ matrix $\mathbf{A}$ by another matrix of specified rank $k$, which is smaller than $m$ and $n$. The singular value decomposition (SVD) can be used to find the ‘best’ such approximation. However, it takes time polynomial in $m$, $n$ 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 ${\mathbf{D}}^{*}$ of rank at most $k$ so that

holds with probability at least $1-\delta $ (where ${\parallel \xb7\parallel}_{F}$ is the Frobenius norm). The algorithm takes time polynomial in $k$, $1/\epsilon $, $log(1/\delta )$ only and is independent of $m$ and $n$. 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.