Abstract

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 8TB tensor and a real life 12.5 GB tensor in a few minutes on a standard laptop.

Code description

This package provides experiment files and auxiliary files for the randomized block sampling approach to CPD. These scripts can be used to reproduce the experiments the RBS paper.

Reference

N. Vervliet and L. De Lathauwer, "A randomized block sampling approach to canonical polyadic decomposition of large-scale tensors," IEEE Journal of Selected Topics in Signal Processing, vol. 10, no. 2; pp. 284 - 295, Jan. 2016.

Download code