# Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis

arXiv: https://arxiv.org/abs/2001.01017 · HTML: https://mlsanity.com/paper/2001.01017/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jan 2020.

## Built on by (most cited first, 3 of 3)

- [A Linearly Convergent Algorithm for Distributed Principal Component Analysis](https://mlsanity.com/paper/2101.01300/) (2021)
- [Distributed Principal Subspace Analysis for Partitioned Big Data: Algorithms, Analysis, and Implementation](https://mlsanity.com/paper/2103.06406/) (2021)
- [Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering](https://mlsanity.com/paper/2207.14589/) (2022)

## Abstract (arXiv)

This paper considers the problem of estimating the principal eigenvector of a covariance matrix from independent and identically distributed data samples in streaming settings. The streaming rate of data in many contemporary applications can be high enough that a single processor cannot finish an iteration of existing methods for eigenvector estimation before a new sample arrives. This paper formulates and analyzes a distributed variant of the classical Krasulina's method (D-Krasulina) that can keep up with the high streaming rate of data by distributing the computational load across multiple processing nodes. The analysis shows that---under appropriate conditions---D-Krasulina converges to the principal eigenvector in an order-wise optimal manner; i.e., after receiving M samples across all nodes, its estimation error can be O(1/M). In order to reduce the network communication overhead, the paper also develops and analyzes a mini-batch extension of D-Krasulina, which is termed DM-Krasulina. The analysis of DM-Krasulina shows that it can also achieve order-optimal estimation error rates under appropriate conditions, even when some samples have to be discarded within the network due to communication latency. Finally, experiments are performed over synthetic and real-world data to validate the convergence behaviors of D-Krasulina and DM-Krasulina in high-rate streaming settings.