A parallel algorithm for big tensor decomposition using randomly compressed cubes (PARACOMP)

Nikos D. Sidiropoulos, Evangelos E. Papalexakis, Christos Faloutsos

Abstract

A parallel algorithm for low-rank tensor decomposition that is especially well-suited for big tensors is proposed. The new algorithm is based on parallel processing of a set of randomly compressed, reduced-size `replicas' of the big tensor. Each replica is independently decomposed, and the results are joined via a master linear equation per tensor mode. The approach enables massive parallelism with guaranteed identifiability properties: if the big tensor has low rank and the system parameters are appropriately chosen, then the rank-one factors of the big tensor will be exactly recovered from the analysis of the reduced-size replicas. The proposed algorithm is proven to yield memory / storage and complexity gains of order up to IJ/F for a big tensor of size I × J × K of rank F with F ≤I ≤J ≤K.
BibTeX
@inproceedings{sidiropoulos2014parallel,
  author = {Nikos D. Sidiropoulos and Evangelos E. Papalexakis and Christos Faloutsos},
  title = {{A parallel algorithm for big tensor decomposition using randomly compressed cubes (PARACOMP)}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2014},
  doi = {10.1109/icassp.2014.6853546},
}

Loading related content...

Figure