ML p(r)ior | Distributed Low Rank Approximation of Implicit Functions of a Matrix

### 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.

Highlights - Most important sentences from the article

# 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

Highlights - Most important sentences from the article

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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 2015-02-19 1502.05746 | cs.DS Binary embedding is a nonlinear dimension reduction methodology where high dimensional data are embe… show more Highlights - Most important sentences from the article 2019-01-29 1901.10204 | cs.LG Spectral clustering refers to a family of unsupervised learning algorithms that compute a spectral e… show more Highlights - Most important sentences from the article 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

Highlights - Most important sentences from the article

2019-01-10
1901.03254 | cs.DS

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

Highlights - Most important sentences from the article

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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article