A DISTRIBUTED AND INCREMENTAL SVD ALGORITHM FOR AGGLOMERATIVE DATA ANALYSIS ON LARGE NETWORKS

被引：31
作者：
Iwen, M. A. [1 ,2 ]
Ong, B. W. [3 ]
机构：
[1] Michigan State Univ, Dept Math, E Lansing, MI 48824 USA
[2] Michigan State Univ, Dept Elect & Comp Engn, E Lansing, MI 48824 USA
[3] Michigan Technol Univ, Dept Math Sci, Houghton, MI 49931 USA
来源：
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS | 2016年 / 37卷 / 04期
基金：
美国国家科学基金会;
关键词：
singular value decomposition; low-rank approximations; distributed computing; incremental SVD; SINGULAR-VALUE DECOMPOSITION; UPDATING ALGORITHM; PARALLEL; COMMUNICATION;
D O I：
10.1137/16M1058467
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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.
引用
收藏
页码：1699 / 1718
页数：20
相关论文
共 38 条
[11]   A multilinear singular value decomposition [J].
De Lathauwer, L ;
De Moor, B ;
Vandewalle, J .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2000, 21 (04) :1253-1278
[12]   NONITERATIVE SUBSPACE TRACKING [J].
DEGROAT, RD .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 1992, 40 (03) :571-577
[13]   COMMUNICATION-OPTIMAL PARALLEL AND SEQUENTIAL QR AND LU FACTORIZATIONS [J].
Demmel, James ;
Grigori, Laura ;
Hoemmen, Mark ;
Langou, Julien .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2012, 34 (01) :A206-A239
[14]  
Golub G., 1965, Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis, V2, P205
[15]  
GOLUB GH, 1973, SIAM REV, V15, P318, DOI 10.1137/1015032
[16]   DOWNDATING THE SINGULAR-VALUE DECOMPOSITION [J].
GU, M ;
EISENSTAT, SC .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1995, 16 (03) :793-810
[17]  
Gu M., 1994, A stable and fast algorithm for updating the singular value decomposition"
[18]   An Improved Parallel Singular Value Algorithm and Its Implementation for Multicore Hardware [J].
Haidar, Azzam ;
Kurzak, Jakub ;
Luszczek, Piotr .
2013 INTERNATIONAL CONFERENCE FOR HIGH PERFORMANCE COMPUTING, NETWORKING, STORAGE AND ANALYSIS (SC), 2013,
[19]   Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions [J].
Halko, N. ;
Martinsson, P. G. ;
Tropp, J. A. .
SIAM REVIEW, 2011, 53 (02) :217-288
[20]  
Horn R.A., 1994, TOPICS MATRIX ANAL, DOI DOI 10.1017/CBO9780511840371
1234