Bilateral sampling randomized singular value decomposition

被引：0

作者：

Jiang, Hao ^{[2
]}

Du, Peibing ^{[1
]}

Sun, Tao ^{[1
]}

Li, Housen ^{[1
,3
]}

Cheng, Lizhi ^{[1
,4
]}

Yang, Canqun ^{[2
,5
]}

机构：

[1] Natl Univ Def Technol, Sch Sci, Changsha 410073, Hunan, Peoples R China

[2] Natl Univ Def Technol, Coll Comp, Changsha 410073, Hunan, Peoples R China

[3] Max Planck Inst Biophys Chem, Am Fassberg 11, D-37077 Gottingen, Germany

[4] Natl Univ Def Technol, State Key Lab High Performance Computat, Changsha 410073, Hunan, Peoples R China

[5] Natl Univ Def Technol, Sci & Technol Parallel & Distributed Proc L, Changsha 410073, Hunan, Peoples R China

来源：

2016 17TH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES (PDCAT) | 2016年

基金：

中国国家自然科学基金; 国家高技术研究发展计划(863计划);

关键词：

Low-rank; Singular value decomposition; Randomized methods; Bilateral sampling; Stable; MONTE-CARLO ALGORITHMS; MATRICES; APPROXIMATION;

D O I：

10.1109/PDCAT.2016.26

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Designing fast singular value decomposition (SVD) is significantly interesting in applications. The random direct SVD (RSVD) has provided a fast scheme to compute the well approximate SVD by unilateral randomized sampling. In this paper, we present an efficient random algorithm in a bilateral sampling way. We also prove that the proposed algorithms can be bounded well and have less computational complexity compared to RSVD when the objective matrix is approximately square. Numerical experiments on graph Laplacian and Hilbert matrix demonstrate the efficiency and stability of the proposed methods.

引用

页码：57 / 62

页数：6

共 16 条

[1]

Boutsidis C., 2011, THESIS

[2]

Clarkson K. L., 2009, STOC 09

[3]

Drineas P, 2005, J MACH LEARN RES, V6, P2153

[4] Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication [J].

Drineas, Petros ;

Kannan, Ravi ;

Mahoney, Michael W. .

SIAM JOURNAL ON COMPUTING, 2006, 36 (01) :132-157

[5] Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix [J].

Drineas, Petros ;

Kannan, Ravi ;

Mahoney, Michael W. .

SIAM JOURNAL ON COMPUTING, 2006, 36 (01) :158-183

[6] Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition [J].

Drineas, Petros ;

Kannan, Ravi ;

Mahoney, Michael W. .

SIAM JOURNAL ON COMPUTING, 2006, 36 (01) :184-206

[7]

Gittens A., 2009, ERROR BOUNDS RANDOM

[8]

Gittens A., 2013, INT C MACH LEARN, V28, P567

[9]

Golub GH., 2013, MATRIX COMPUTATIONS

[10] 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

← 1 2 →