分布式的PCA

Improved Distributed Principal Component Analysis

Maria-Florina Balcan

School of Computer Science

Carnegie Mellon University

ninamf@cs.cmu.edu

Vandana Kanchanapally

School of Computer Science

Georgia Institute of Technology

vvandana@gatech.edu

Yingyu Liang

Department of Computer Science

dure for approximate PCA, one can use it to approximately solve problems such

as k-means clustering and low rank approximation. The essential properties of an

approximate distributed PCA algorithm are its communication cost and computa-

tional efficiency for a given desired accuracy in downstream applications. We give

new algorithms and analyses for distributed PCA which lead to improved com-

munication and computational costs for k-means clustering and related problems.

Our empirical study on real world data shows a speedup of orders of magnitude,

preserving communication with only a negligible degradation in solution quality.

Some of these techniques we develop, such as a general transformation from a

constant success probability subspace embedding to a high success probability

captures as much of the variance of the data as possible. Hence, it can reveal low-dimensional

structure in very high dimensional data. Moreover, it can serve as a preprocessing step to reduce

the data dimension in various machine learning tasks, such as Non-Negative Matrix Factorization

(NNMF) [15] and Latent Dirichlet Allocation (LDA) [4].

In the distributed model, approximate PCA was used by Feldman et al. [9] for solving a number

of shape fitting problems such as k-means clustering, where the approximation is in the form of a

coreset, and has the property that local coresets can be easily combined across servers into a global

coreset, thereby providing an approximate PCA to the union of the data sets. Designing small

coresets therefore leads to communication-efficient protocols. Coresets have the nice property that

their size typically does not depend on the number n of points being approximated. A beautiful

parameters of the downstream applications (such as the number k of clusters in k-means clustering)?

Second, while preserving optimal or nearly-optimal communication, can we improve the computa-

tional costs of the protocols? We note that in the protocols of Feldman et al. each server has to

run a singular value decomposition (SVD) on her local data set, while additional work needs to be

performed to combine the outputs of each server into a global approximate PCA. Third, are these al-

gorithms practical and do they scale well with large-scale datasets? In this paper we give answers to

the above questions. To state our results more precisely, we first define the model and the problems.

Communication Model. In the distributed setting, we consider a set of s nodes V = {v

i

, 1 ≤ i ≤

s}, each of which can communicate with a central coordinator v

. On each node v

, there is a local

1

2

Let p

i

denote the i-th row of P. Throughout the paper, we assume that the data points are centered

Approximate PCA and `

2

-Error Fitting. For a matrix A = [a

a

2

ij

be its

Frobenius norm, and let σ

i

(A) be the i-th singular value of A. Let A

(t)

denote the matrix that

d

q∈L

kp − qk

2

2

= kp − π

L

(p)k

2

2

.

Definition 1. The linear (or affine) r-Subspace k-Clustering on P ∈ R

n×d

is

min

(p

, L) (1)

1

n

j

k

j=1

of which is an r-dimensional linear (or affine) subspace.

PCA is a special case when k = 1 and the center is an r-dimensional subspace. This optimal r-

dimensional subspace is spanned by the top r right singular vectors of P, also known as the principal

components, and can be found using the singular value decomposition (SVD). Another special case

of the above is k-means clustering when the centers are points (r = 0). Constrained versions of this

problem include NNMF where the r-dimensional subspace should be spanned by positive vectors,

and LDA which assumes a prior distribution defining a probability for each r-dimensional subspace.

i

stacks the O(r/) × d matrices Y

i

on top of each other, forming an O(sr/) × d matrix Y, and

computes the top r principal components of Y, and returns these to the servers. This provides a

Our Contributions. Our results are summarized as follows.

Improved Communication: We improve the communication cost for using distributed PCA for k-

means clustering and similar `

2

-fitting problems. The best previous approach is to use Corollary 4.5

in [9], which shows that given a data matrix P, if we project the rows onto the space spanned by

the top O(k/

2

) principal components, and solve the k-means problem in this subspace, we obtain a

feature of this approach is that by using the distributed k-means algorithm in [3] on the projected

data, the coordinator can sample points from the servers proportional to their local k-means cost

solutions, which reduces the communication roughly by a factor of s, which would come from each

server sending their local k-means coreset to the coordinator. Furthermore, before applying the

above approach, one can first run any other dimension reduction to dimension d

cost is preserved up to certain accuracy. For example, if we want a 1+ approximation factor, we can

set d

= O(log n/

2

) by a Johnson-Lindenstrauss transform; if we want a larger 2+ approximation

factor, we can set d

= O(k/

) using [5]. In this way the parameter d in the above communication

cost bound can be replaced by d

projecting onto principal components is deterministic and does not incur error probability.

of our knowledge has not been addressed. A major bottleneck is that each player is computing

2

to P

. Then we only need to do PCA on

i

i

(r)

Lemma 1. Suppose A has SVD A = UΣV and let

(V

If t = O(r/), then for any d × r matrix X with orthonormal columns,

2

(A, L

This means that the projections of

k

]. Each term in which is bounded by the lemma. So we can use

the PCA task. Again, computing PCA on

where the minimization is over d×r orthonormal matrices X. The communication is O(

) words.

2.1 Guarantees for Distributed `

Algorithm disPCA can also be used as a pre-processing step for applications such as `

2

-error fitting.

Therefore, the projected data serves as a proxy of the original data, i.e., any distributed algorithm

can be applied on the projected data to get a solution on the original data. As the dimension is lower,

the communication cost is reduced. Formally,

Theorem 3. Let t

constant c

2

(P, L) ≤ d

(

≤ (1 + )d

(P, L).

(P, L) ≤ d

2

0

2

(

0

2

which leads to d

2

(P, L

). In other words, the distributed PCA step only

introduces a small multiplicative approximation factor of (1 + 3).

The key to prove the theorem is the close projection property of the algorithm (Lemma 4): for any

Algorithm 1 Distributed k-means clustering

2

s

i=1

as a sub-

routine, to get k centers L.

Output: L.

particular, we choose X to be the orthonormal basis of the subspace spanning the centers. Then the

difference between the objective values of P and

mal columns, 0 ≤ kPX −

2

F

2

2

F

2

).

Proof Sketch: We first introduce some auxiliary variables for the analysis, which act as intermediate

connections between P and

i

to

concatenation of

i

. These variables are designed

so that the difference between P and

Our proof then proceeds by first bounding these differences, and then bounding that between P and

The first term is just

kP

i

2

F

2

F

Subspace Embeddings One can significantly improve the time of the distributed PCA algorithms