Author:

Keywords:

SISTA, BIOTENSORS - 339804;info:eu-repo/grantAgreement/EC/FP7/339804, Science & Technology, Technology, Engineering, Electrical & Electronic, Engineering, Tensor decomposition, canonical polyadic decomposition, CANDECOMP/PARAFAC, randomized algorithms, block sampling, big data, blind source separation, ALGORITHMS, PARAFAC, RANK, OPTIMIZATION, UNIQUENESS, COMPLEXITY, ARRAYS, BOUNDS, C16/15/059#53326574, 0801 Artificial Intelligence and Image Processing, 0906 Electrical and Electronic Engineering, 1005 Communications Technologies, Networking & Telecommunications, 4006 Communications engineering, 4603 Computer vision and multimedia computation

Abstract:

© 2015 IEEE. 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.