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 \times d$ matrix $A^t$, and we may
be interested in computing a low rank approximation to $A = f(\sum_{t=1}^s
A^t)$, where $f$ is a function which is applied entrywise to the matrix
$\sum_{t=1}^s A^t$. We show for a wide class of functions $f$ it is possible to
efficiently compute a $d \times d$ rank-$k$ projection matrix $P$ for which
$\|A - AP\|_F^2 \leq \|A - [A]_k\|_F^2 + \varepsilon \|A\|_F^2$, where $AP$
denotes the projection of $A$ onto the row span of $P$, and $[A]_k$ denotes the
best rank-$k$ approximation to $A$ given by the singular value decomposition.
The communication cost of our protocols is $d \cdot (sk/\varepsilon)^{O(1)}$,
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.

本研究探讨了分布式低秩逼近，其中需要只隐含地跨不同服务器表示逼近的矩阵。研究表明，在宽泛的函数 f 类别中，可以高效计算一个低秩映射矩阵 P，以满足通信成本为 d∙(sk/ε)^O (1)，且算法成功概率高，并可将其用于计算入门型 softmax、Gaussian 核扩展以及 robust 低秩逼近等问题。