Gossip PCA

Details Gossip PCA Gossip PCA

2011-03-22

arxiv.org/abs/1103.4195v1

Computer Science

Data Structures and Algorithms

13 pages, 1 figure

Scientific paper

Eigenvectors of data matrices play an important role in many computational problems, ranging from signal processing to machine learning and control. For instance, algorithms that compute positions of the nodes of a wireless network on the basis of pairwise distance measurements require a few leading eigenvectors of the distances matrix. While eigenvector calculation is a standard topic in numerical linear algebra, it becomes challenging under severe communication or computation constraints, or in absence of central scheduling. In this paper we investigate the possibility of computing the leading eigenvectors of a large data matrix through gossip algorithms. The proposed algorithm amounts to iteratively multiplying a vector by independent random sparsification of the original matrix and averaging the resulting normalized vectors. This can be viewed as a generalization of gossip algorithms for consensus, but the resulting dynamics is significantly more intricate. Our analysis is based on controlling the convergence to stationarity of the associated Kesten-Furstenberg Markov chain.

Affiliated with

Also associated with

No associations

Rating

Gossip PCA does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Gossip PCA, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Gossip PCA will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-48226