Dimension Independent Matrix Square using MapReduce (DIMSUM)
Reza Bosagh Zadeh, Gunnar Carlsson · 2015
We compute the singular values of an m n sparse matrix A in a distributed setting, without communication dependence on m, which is useful for very large m. In particular, we give a simple nonadaptive sampling scheme where the singular values of A 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 A T A. We preserve singular values of A T A with relative error with shue size