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
Pages209-220
Number of pages12
Edition1 SPEC. ISSUE
DOIs
StatePublished - Jul 15 2011
Event2011 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'11 - San Jose, CA, United States
Duration: Jun 7 2011Jun 11 2011

Publication series

NamePerformance Evaluation Review
Number1 SPEC. ISSUE
Volume39
ISSN (Print)0163-5999

Other

Other2011 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'11
Country/TerritoryUnited States
CitySan Jose, CA
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