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.
@cite_8 introduced a sampling procedure where rows and columns of @math are picked with probabilities proportional to their squared lengths and used that to compute an approximation to @math . Later @cite_3 and @cite_6 improved the sampling procedure. To implement these approximations to @math on MapReduce one would need a shuffle size dependent on @math or overload a single machine. We improve this to be independent of @math both in shuffle size and reduce-key complexity.
@cite_6 @cite_3 @cite_8
2885550688 1970950689 1979750072
Given a matrix A, it is often desirable to find a good approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when A has strong spectral features, that is, when the singular values of interest are significantly greater than those of a random matrix with size and entries similar to A. Our technique amounts to independently sampling and or quantizing the entries of A, thus speeding up computation by reducing the number of nonzero entries and or the length of their representation. Our analysis is based on observing that the acts of sampling and quantization can be viewed as adding a random matrix N to A, whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability, N has very weak spectral features, we can prove that the effect of sampling and quantization nearly vanishes when a low-rank approximation to A p N is computed. We give high probability bounds on the quality of our approximation both in the Frobenius and the 2-norm. 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.