A Distributed and Incremental SVD Algorithm for Agglomerative Data Analysis on Large Networks

Abstract

In this paper, we show that the SVD of a matrix can be constructed efficiently in a hierarchical approach. Our algorithm is proven to recover the singular values and left singular vectors if the rank of the input matrix $A$ is known. Further, the hierarchical algorithm can be used to recover the $d$ largest singular values and left singular vectors with bounded error. We also show that the proposed method is stable with respect to roundoff errors or corruption of the original matrix entries. Numerical experiments validate the proposed algorithms and parallel cost analysis.

References in corpus (2)

• MLlib: Machine Learning in Apache Spark
• Parallel Tensor Compression for Large-Scale Scientific Data

Cited by in corpus (11)

• Hierarchical Approximate Proper Orthogonal Decomposition
• Federated Principal Component Analysis
• HDG-POD Reduced Order Model of the Heat Equation
• Error Analysis of an Incremental POD Algorithm for PDE Simulation Data
• MOSES: A Streaming Algorithm for Linear Dimensionality Reduction
• A note on incremental POD algorithms for continuous time data
• Zoom-SVD: Fast and Memory Efficient Method for Extracting Key Patterns in an Arbitrary Time Range
• PD-ML-Lite: Private Distributed Machine Learning from Lighweight Cryptography
• A New High Performance and Scalable SVD algorithm on Distributed Memory Systems
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• Ranky : An Approach to Solve Distributed SVD on Large Sparse Matrices