Gossip PCA

Satish Babu Korada, Andrea Montanari, Sewoong Oh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSIGMETRICS'11 - Proceedings of the 2011 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
PublisherAssociation for Computing Machinery
Pages209-220
Number of pages12
Volume39
Edition1 SPEC. ISSUE
ISBN (Print)9781450302623
DOIs
StatePublished - 2011
Externally publishedYes
Event2011 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2011 - San Jose, United States
Duration: Jun 7 2011Jun 11 2011

Conference

Conference2011 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2011
Country/TerritoryUnited States
CitySan Jose
Period6/7/116/11/11

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Gossip PCA'. Together they form a unique fingerprint.

Cite this