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 条

[1] Numerical linear algebra on emerging architectures: the PLASMA and MAGMA projects [J].

Agullo, Emmanuel ;

Demmel, Jim ;

Dongarra, Jack ;

Hadri, Bilel ;

Kurzak, Jakub ;

Langou, Julien ;

Ltaief, Hatem ;

Luszczek, Piotr ;

Tomov, Stanimire .

SCIDAC 2009: SCIENTIFIC DISCOVERY THROUGH ADVANCED COMPUTING, 2009, 180

[2] Multi-scale geometric methods for data sets II: Geometric Multi-Resolution Analysis [J].

Allard, William K. ;

Chen, Guangliang ;

Maggioni, Mauro .

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 2012, 32 (03) :435-462

[3]

[Anonymous], 2015, CORR

[4]

[Anonymous], 2009, Hadoop: The Definitive Guide

[5] Low-Rank Incremental methods for computing dominant singular subspaces [J].

Baker, C. G. ;

Gallivan, K. A. ;

Van Dooren, P. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 436 (08) :2866-2888

[6]

Balzano L, 2013, 2013 IEEE 5TH INTERNATIONAL WORKSHOP ON COMPUTATIONAL ADVANCES IN MULTI-SENSOR ADAPTIVE PROCESSING (CAMSAP 2013), P1, DOI 10.1109/CAMSAP.2013.6713992

[7] Fast low-rank modifications of the thin singular value decomposition [J].

Brand, M .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2006, 415 (01) :20-30

[8] A portable programming interface for performance evaluation on modern processors [J].

Browne, S ;

Dongarra, J ;

Garner, N ;

Ho, G ;

Mucci, P .

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS, 2000, 14 (03) :189-204

[9] RANK-ONE MODIFICATION OF SYMMETRIC EIGENPROBLEM [J].

BUNCH, JR ;

NIELSEN, CP ;

SORENSEN, DC .

NUMERISCHE MATHEMATIK, 1978, 31 (01) :31-48

[10] Collective communication: theory, practice, and experience [J].

Chan, Ernie ;

Heimlich, Marcel ;

Purkayastha, Avi ;

van de Geijn, Robert .

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2007, 19 (13) :1749-1783

← 1 2 3 4 →