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

N. D. Sidiropoulos; E. E. Papalexakis; C. Faloutsos

doi:10.1109/ICASSP.2014.6853546

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

N. D. Sidiropoulos, E. E. Papalexakis, C. Faloutsos

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 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 language	English (US)
Title of host publication	2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1-5
Number of pages	5
ISBN (Print)	9781479928927
DOIs	https://doi.org/10.1109/ICASSP.2014.6853546
State	Published - 2014
Event	2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014 - Florence, Italy Duration: May 4 2014 → May 9 2014

Publication series

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

Other

Other	2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014
Country/Territory	Italy
City	Florence
Period	5/4/14 → 5/9/14

Keywords

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

Publisher link

10.1109/ICASSP.2014.6853546

Find It

Find It at U of M Libraries

Cite this

Sidiropoulos, N. D., Papalexakis, E. E., & Faloutsos, C. (2014). A parallel algorithm for big tensor decomposition using randomly compressed cubes (PARACOMP). In 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014 (pp. 1-5). Article 6853546 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2014.6853546

A parallel algorithm for big tensor decomposition using randomly compressed cubes (PARACOMP). / Sidiropoulos, N. D.; Papalexakis, E. E.; Faloutsos, C.
2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014. Institute of Electrical and Electronics Engineers Inc., 2014. p. 1-5 6853546 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sidiropoulos, ND, Papalexakis, EE & Faloutsos, C 2014, A parallel algorithm for big tensor decomposition using randomly compressed cubes (PARACOMP). in 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014., 6853546, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 1-5, 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014, Florence, Italy, 5/4/14. https://doi.org/10.1109/ICASSP.2014.6853546

Sidiropoulos ND, Papalexakis EE, Faloutsos C. A parallel algorithm for big tensor decomposition using randomly compressed cubes (PARACOMP). In 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 1-5. 6853546. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2014.6853546

Sidiropoulos, N. D. ; Papalexakis, E. E. ; Faloutsos, C. / A parallel algorithm for big tensor decomposition using randomly compressed cubes (PARACOMP). 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 1-5 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{6bbd8e2a6445409ea83978a41ee1877a,

title = "A parallel algorithm for big tensor decomposition using randomly compressed cubes (PARACOMP)",

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.",

keywords = "Big Data, CANDECOMP/PARAFAC, Cloud Computing and Storage, Parallel and Distributed Computation, Tensor decomposition",

author = "Sidiropoulos, {N. D.} and Papalexakis, {E. E.} and C. Faloutsos",

year = "2014",

doi = "10.1109/ICASSP.2014.6853546",

language = "English (US)",

isbn = "9781479928927",

series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1--5",

booktitle = "2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014",

note = "2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014 ; Conference date: 04-05-2014 Through 09-05-2014",

}

TY - GEN

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

AU - Sidiropoulos, N. D.

AU - Papalexakis, E. E.

AU - Faloutsos, C.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Big Data

KW - CANDECOMP/PARAFAC

KW - Cloud Computing and Storage

KW - Parallel and Distributed Computation

KW - Tensor decomposition

UR - http://www.scopus.com/inward/record.url?scp=84905224559&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84905224559&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2014.6853546

DO - 10.1109/ICASSP.2014.6853546

M3 - Conference contribution

AN - SCOPUS:84905224559

SN - 9781479928927

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 1

EP - 5

BT - 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014

Y2 - 4 May 2014 through 9 May 2014

ER -

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

Abstract

Publication series

Other

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this