Distributed low rank approximation of implicit functions of a matrix
By David P. Woodruff, Peilin Zhong. 2016
33 citations recorded by the source corpus.
We study distributed low rank approximation in which the matrix to be approximated is only implicitly represented across the different servers. For example, each of s servers may have an n × d matrix A<sup>t</sup>, and we may be interested in computing a low rank approximation to A = f(Σ<sub>t=1</sub><sup>s</sup>A<sup>t</sup>), where f is a function which is applied entrywise to the matrix Σ<sub>t=1</sub><sup>s</sup>A<sup>t</sup>. We show for a wide class of functions f it is possible to efficiently compute a d × d rank-k projection matrix P for which ∥A - AP∥<sub>F</sub><sup>2</sup> ≤ ∥A - [A]<sub>k</sub>∥<sub>F</sub><sup>2</sup> + ε ∥A∥<sub>F</sub><sup>2</sup>, where AP denotes the projection of A onto the row span of P, and [A]<sub>k</sub> denotes the best rank-k approximation to A given by the singular value decomposition. The communication cost of our protocols is d·(sk=ε)<sup>O(1)</sup>, and they succeed with high probability. Our framework allows us to efficiently compute a low rank approximation to an entry-wise softmax, to a Gaussian kernel expansion, and to M-Estimators applied entrywise (i.e., forms of robust low rank approximation). We also show that our additive error approximation is best possible, in the sense that any protocol achieving relative error for these problems requires significantly more communication. Finally, we experimentally validate our algorithms on real datasets.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- David P. Woodruff
- Christos Boutsidis
- Peilin Zhong
- Zhao Song
- Jakub Konecný
- Michael W. Mahoney
- Peter Bhlmann
- Nicolas Loizou
Citations in the corpus
- Optimal principal component analysis in distributed and streaming models (2015, background): “We note that there is a fairly simple known Ω( ε − 2 ) bit lower bound [46], so although one cannot achieve an O (log(1 /ε )) dependence in the communication as one would maybe expect given iterative algorithms for regression with running time O (log(1 /ε )) (see section 2.6 of [47] for an…”