Model-Driven Sparse CP Decomposition for Higher-Order Tensors

Jiajia Li, Jee Choi, Ioakeim Perros, Jimeng Sun, Richard Vuduc

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

Abstract

Given an input tensor, its CANDECOMP/PARAFAC decomposition (or CPD) is a low-rank representation. CPDs are of particular interest in data analysis and mining, especially when the data tensor is sparse and of higher order (dimension). This paper focuses on the central bottleneck of a CPD algorithm, which is evaluating a sequence of matricized tensor times Khatri-Rao products (MTTKRPs). To speed up the MTTKRP sequence, we propose a novel, adaptive tensor memoization algorithm, AdaTM. Besides removing redundant computations within the MTTKRP sequence, which potentially reduces its overall asymptotic complexity, our technique also allows a user to make a space-time tradeoff by automatically tuning algorithmic and machine parameters using a model-driven framework. Our method improves as the tensor order grows, making its performance more scalable for higher-order data problems. We show speedups of up to 8× and 820× on real sparse data tensors with orders as high as 85 over the SPLATT package and Tensor Toolbox library respectively; and on a full CPD algorithm (CP-ALS), AdaTM can be up to 8× faster than state-of-the-art method implemented in SPLATT.

Original languageEnglish (US)
Title of host publicationProceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium, IPDPS 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1048-1057
Number of pages10
ISBN (Electronic)9781538639146
DOIs
StatePublished - Jun 30 2017
Externally publishedYes
Event31st IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017 - Orlando, United States
Duration: May 29 2017Jun 2 2017

Publication series

NameProceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium, IPDPS 2017

Other

Other31st IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017
CountryUnited States
CityOrlando
Period5/29/176/2/17

Keywords

  • auto-tuning
  • sparse tensor
  • tensor decomposition

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Model-Driven Sparse CP Decomposition for Higher-Order Tensors'. Together they form a unique fingerprint.

  • Cite this

    Li, J., Choi, J., Perros, I., Sun, J., & Vuduc, R. (2017). Model-Driven Sparse CP Decomposition for Higher-Order Tensors. In Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium, IPDPS 2017 (pp. 1048-1057). [7967195] (Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium, IPDPS 2017). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPS.2017.80