History PCA: A New Algorithm for Streaming PCA

Abstract

In this paper we propose a new algorithm for streaming principal component analysis. With limited memory, small devices cannot store all the samples in the high-dimensional regime. Streaming principal component analysis aims to find the $k$-dimensional subspace which can explain the most variation of the $d$-dimensional data points that come into memory sequentially. In order to deal with large $d$ and large $N$ (number of samples), most streaming PCA algorithms update the current model using only the incoming sample and then dump the information right away to save memory. However the information contained in previously streamed data could be useful. Motivated by this idea, we develop a new streaming PCA algorithm called History PCA that achieves this goal. By using $O(Bd)$ memory with $B\approx 10$ being the block size, our algorithm converges much faster than existing streaming PCA algorithms. By changing the number of inner iterations, the memory usage can be further reduced to $O(d)$ while maintaining a comparable convergence speed. We provide theoretical guarantees for the convergence of our algorithm along with the rate of convergence. We also demonstrate on synthetic and real world data sets that our algorithm compares favorably with other state-of-the-art streaming PCA methods in terms of the convergence speed and performance.

References in corpus (6)

• The Noisy Power Method: A Meta Algorithm with Applications
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCA
• Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
• Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm
• First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate

Cited by in corpus (6)

• Exploring Scalable, Distributed Real-Time Anomaly Detection for Bridge Health Monitoring
• Streaming Batch Eigenupdates for Hardware Neuromorphic Networks
• AdaOja: Adaptive Learning Rates for Streaming PCA
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• Memory-efficient training with streaming dimensionality reduction
• Embedding Principal Component Analysis for Data Reductionin Structural Health Monitoring on Low-Cost IoT Gateways