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

Nikolaos Sidiropoulos, E. E. Papalexakis, C. Faloutsos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

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.

Original languageEnglish (US)
Title of host publication2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-5
Number of pages5
ISBN (Print)9781479928927
DOIs
StatePublished - Jan 1 2014
Event2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014 - Florence, Italy
Duration: May 4 2014May 9 2014

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
ISSN (Print)1520-6149

Other

Other2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014
CountryItaly
CityFlorence
Period5/4/145/9/14

Keywords

  • Big Data
  • CANDECOMP/PARAFAC
  • Cloud Computing and Storage
  • Parallel and Distributed Computation
  • Tensor decomposition

Fingerprint Dive into the research topics of 'A parallel algorithm for big tensor decomposition using randomly compressed cubes (PARACOMP)'. Together they form a unique fingerprint.

Cite this