We compute the singular values of an @math sparse matrix @math in a distributed setting, without communication dependence on @math , which is useful for very large @math . In particular, we give a simple nonadaptive sampling scheme where the singular values of @math are estimated within relative error with constant probability. Our proven bounds focus on the MapReduce framework, which has become the de facto tool for handling such large matrices that cannot be stored or even streamed through a single machine. On the way, we give a general method to compute @math . We preserve singular values of @math with @math relative error with shuffle size @math and reduce-key complexity @math . We further show that if only specific entries of @math are required and @math has nonnegative entries, then we can reduce the shuffle size to @math and reduce-key complexity to @math , where @math is the minimum cosine similarity for the entries being estimated. All of our bounds are independent of @math , the larger dimension. We provide open-source implementations in Spark and Scalding, along with experiments in an industrial setting.
We prove that any real matrix A contains a subset of at most 4k e+ 2k log(k+1) rows whose span “contains” a matrix of rank at most k with error only (1+e) times the error of the best rank-k approximation of A. We complement it with an almost matching lower bound by constructing matrices where the span of any k 2e rows does not “contain” a relative (1+e)-approximation of rank k. Our existence result leads to an algorithm that finds such rank-k approximation in time @math i.e., essentially O(Mk e), where M is the number of nonzero entries of A. The algorithm maintains sparsity, and in the streaming model [12,14,15], it can be implemented using only 2(k+1)(log(k+1)+1) passes over the input matrix and @math additional space. Previous algorithms for low-rank approximation use only one or two passes but obtain an additive approximation. We consider the problem of approximating a given m × n matrix 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 D* of rank at most k so that holds with probability at least 1 − Δ (where v·vF is the Frobenius norm). The algorithm takes time polynomial in k,1 e, log(1 Δ) 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.