A Randomized Block Sampling Approach to Canonical Polyadic Decomposition of Large-Scale Tensors

被引:63
作者
Vervliet, Nico [1 ,2 ]
De Lathauwer, Lieven [1 ,2 ,3 ]
机构
[1] Katholieke Univ Leuven, Dept Elect Engn ESAT, B-3001 Louvain, Belgium
[2] iMinds Med IT, B-3000 Louvain, Belgium
[3] KU Leuven Kulak, Grp Sci Engn & Technol, B-8500 Kortrijk, Belgium
基金
欧洲研究理事会;
关键词
Tensor decomposition; canonical polyadic decomposition; CANDECOMP/PARAFAC; randomized algorithms; block sampling; big data; blind source separation; ALGORITHMS; PARAFAC; RANK; OPTIMIZATION; UNIQUENESS; COMPLEXITY; ARRAYS; BOUNDS;
D O I
10.1109/JSTSP.2015.2503260
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
For the analysis of large-scale datasets one often assumes simple structures. In the case of tensors, a decomposition in a sum of rank-1 terms provides a compact and informative model. Finding this decomposition is intrinsically more difficult than its matrix counterpart. Moreover, for large-scale tensors, computational difficulties arise due to the curse of dimensionality. The randomized block sampling canonical polyadic decomposition method presented here combines increasingly popular ideas from randomization and stochastic optimization to tackle the computational problems. Instead of decomposing the full tensor at once, updates are computed from small random block samples. Using step size restriction the decomposition can be found up to near optimal accuracy, while reducing the computation time and number of data accesses significantly. The scalability is illustrated by the decomposition of a synthetic 8 TB tensor and a real life 12.5 GB tensor in a few minutes on a standard laptop.
引用
收藏
页码:284 / 295
页数:12
相关论文
共 57 条
[1]   A scalable optimization approach for fitting canonical tensor decompositions [J].
Acar, Evrim ;
Dunlavy, Daniel M. ;
Kolda, Tamara G. .
JOURNAL OF CHEMOMETRICS, 2011, 25 (02) :67-86
[2]   PARAFAC algorithms for large-scale problems [J].
Anh Huy Phan ;
Cichocki, Andrzej .
NEUROCOMPUTING, 2011, 74 (11) :1970-1984
[3]   LOW COMPLEXITY DAMPED GAUSS-NEWTON ALGORITHMS FOR CANDECOMP/PARAFAC [J].
Anh-Huy Phan ;
Tichavsky, Petr ;
Cichocki, Andrzej .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2013, 34 (01) :126-147
[4]  
[Anonymous], 2011, Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)
[5]  
[Anonymous], 1985, Adaptive signal processing prentice-hall
[6]  
[Anonymous], 1988, P 1988 CONNECTIONIST
[7]  
[Anonymous], P NEUR INF PROC SYST
[8]   Efficient MATLAB computations with sparse and factored tensors [J].
Bader, Brett W. ;
Kolda, Tamara G. .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2007, 30 (01) :205-231
[9]   SOME CLASSES OF GLOBAL CRAMER-RAO BOUNDS [J].
BOBROVSKY, BZ ;
MAYERWOLF, E ;
ZAKAI, M .
ANNALS OF STATISTICS, 1987, 15 (04) :1421-1438
[10]  
Bordes A, 2009, J MACH LEARN RES, V10, P1737