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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2016-10-21

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

Highlights - Most important sentences from the article

2014-10-14

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

Highlights - Most important sentences from the article

2013-06-25

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

Highlights - Most important sentences from the article

2015-02-19

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

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
PDF

Highlights - Most important sentences from the article

2019-05-14

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

Highlights - Most important sentences from the article

2019-01-10

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

Highlights - Most important sentences from the article

2019-04-22

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

Highlights - Most important sentences from the article

2018-12-01

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

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
PDF

Highlights - Most important sentences from the article

2018-05-10

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

Highlights - Most important sentences from the article

2018-10-18

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
PDF

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
PDF

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
PDF

Highlights - Most important sentences from the article

2018-04-09

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

Highlights - Most important sentences from the article