A distributed and incremental SVD algorithm for agglomerative data analysis on large networks

© 2016 Society for Industrial and Applied Mathematics. In this paper it is shown that the SVD of a matrix can be constructed efficiently in a hierarchical approach. The proposed algorithm is proven to recover the singular values and left singular vectors of the input matrix A if its rank is known. Further, the hierarchical algorithm can be used to recover the d largest singular values and left singular vectors with bounded error. It is also shown that the proposed method is stable with respect to round-off errors or corruption of the original matrix entries. Numerical experiments validate the proposed algorithms and parallel cost analysis