S. Korada, A. Montanari, and S. Oh. Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, page 209--220. New York, NY, USA, ACM, (2011)
DOI: 10.1145/1993744.1993764
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.</p> <p>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.
%0 Conference Paper
%1 Korada:2011:GP:1993744.1993764
%A Korada, Satish Babu
%A Montanari, Andrea
%A Oh, Sewoong
%B Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems
%C New York, NY, USA
%D 2011
%I ACM
%K gossip pca
%P 209--220
%R 10.1145/1993744.1993764
%T Gossip PCA
%X 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.</p> <p>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.
%@ 978-1-4503-0814-4
@inproceedings{Korada:2011:GP:1993744.1993764,
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.</p> <p>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.},
acmid = {1993764},
added-at = {2013-05-06T19:49:32.000+0200},
address = {New York, NY, USA},
author = {Korada, Satish Babu and Montanari, Andrea and Oh, Sewoong},
biburl = {https://www.bibsonomy.org/bibtex/2df513d9f6393d1de71fd1350eed2f11b/ytyoun},
booktitle = {Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems},
doi = {10.1145/1993744.1993764},
interhash = {4ff45cfa3b53dd7ec5c82aa5d08a8cf8},
intrahash = {df513d9f6393d1de71fd1350eed2f11b},
isbn = {978-1-4503-0814-4},
keywords = {gossip pca},
location = {San Jose, California, USA},
numpages = {12},
pages = {209--220},
publisher = {ACM},
series = {SIGMETRICS '11},
timestamp = {2013-05-06T19:49:32.000+0200},
title = {Gossip PCA},
year = 2011
}