### Distributed Low Rank Approximation of Implicit Functions of a Matrix

**2016-01-28**

1601.07721 | cs.NA

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.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2016-08-16**

1608.04481 | cs.DS

These are lecture notes that are based on the lectures from a class I taught
on the topic of Randomi… show more

**2016-10-21**

1610.06656 | stat.ML

In this paper we present a new algorithm for computing a low rank
approximation of the product $A^TB… show more

**2014-10-14**

1410.3886 | cs.DS

In this work, we propose a new randomized algorithm for computing a low-rank
approximation to a give… show more

**2013-06-25**

1306.5825 | cs.LG

Fourier PCA is Principal Component Analysis of a matrix obtained from higher
order derivatives of th… show more

**2015-02-19**

1502.05746 | cs.DS

Binary embedding is a nonlinear dimension reduction methodology where high
dimensional data are embe… show more

**2019-01-29**

1901.10204 | cs.LG

Spectral clustering refers to a family of unsupervised learning algorithms
that compute a spectral e… show more

**2019-05-14**

1905.05643 | eess.SP

We study the sample complexity of estimating the covariance matrix $T$ of a
distribution $\mathcal{D… show more

**2019-01-10**

1901.03254 | cs.DS

Semidefinite programming (SDP) is a central topic in mathematical
optimization with extensive studie… show more

**2019-04-22**

1904.09841 | cs.DS

In low-rank approximation with missing entries, given $A\in
\mathbb{R}^{n\times n}$ and binary $W \i… show more

**2018-12-01**

1812.00241 | cs.DS

Most known algorithms in the streaming model of computation aim to
approximate a single function suc… show more

**2019-04-11**

1904.05543 | cs.DS

In the subspace sketch problem one is given an $n\times d$ matrix $A$ with
$O(\log(nd))$ bit entries… show more

**2018-05-10**

1805.03765 | cs.DS

We initiate the study of numerical linear algebra in the sliding window
model, where only the most r… show more

**2018-10-18**

1810.08171 | cs.DS

We show that for the problem of testing if a matrix $A \in F^{n \times n}$
has rank at most $d$, or … show more

**2018-09-19**

1809.06986 | cs.DS

Let $\mathbf{P}=\{ p_1, p_2, \ldots p_n \}$ and $\mathbf{Q} = \{ q_1, q_2
\ldots q_m \}$ be two poin… show more

**2017-04-11**

1704.03371 | cs.DS

We show how to compute a relative-error low-rank approximation to any
positive semidefinite (PSD) ma… show more

**2018-04-09**

1804.03065 | cs.LG

We consider the problem of finding anomalies in high-dimensional data using
popular PCA based anomal… show more