Randomized online CP decomposition

• Main Authors: MA, Congbo, YANG, Xiaowei, WANG, Hu
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: CP decomposition; Online learning; Randomized-sampling; Tensor decomposition; Databases and Information Systems; Programming Languages and Compilers
• Online Access: https://ink.library.smu.edu.sg/sis_research/4112
• Institution: Singapore Management University

CANDECOMP/PARAFAC (CP) decomposition has been widely used to deal with multi-way data. For real-time or large-scale tensors, based on the ideas of randomized-sampling CP decomposition algorithm and online CP decomposition algorithm, a novel CP decomposition algorithm called randomized online CP decomposition (ROCP) is proposed in this paper. The proposed algorithm can avoid forming full Khatri-Rao product, which leads to boost the speed largely and reduce memory usage. The experimental results on synthetic data and real-world data show the ROCP algorithm is able to cope with CP decomposition for large-scale tensors with arbitrary number of dimensions. In addition, ROCP can reduce the computing time and memory usage dramatically, especially for large-scale tensors.