Provable online CP/PARAFAC decomposition of a structured tensor via dictionary learning

Sirisha Rambhatla, Xingguo Li, Jarvis Haupt

Research output: Contribution to journalConference articlepeer-review

Abstract

We consider the problem of factorizing a structured 3-way tensor into its constituent Canonical Polyadic (CP) factors. This decomposition, which can be viewed as a generalization of singular value decomposition (SVD) for tensors, reveals how the tensor dimensions (features) interact with each other. However, since the factors are a priori unknown, the corresponding optimization problems are inherently non-convex. The existing guaranteed algorithms which handle this non-convexity incur an irreducible error (bias), and only apply to cases where all factors have the same structure. To this end, we develop a provable algorithm for online structured tensor factorization, wherein one of the factors obeys some incoherence conditions, and the others are sparse. Specifically we show that, under some relatively mild conditions on initialization, rank, and sparsity, our algorithm recovers the factors exactly (up to scaling and permutation) at a linear rate. Complementary to our theoretical results, our synthetic and real-world data evaluations showcase superior performance compared to related techniques.

Original languageEnglish (US)
JournalAdvances in Neural Information Processing Systems
Volume2020-December
StatePublished - 2020
Event34th Conference on Neural Information Processing Systems, NeurIPS 2020 - Virtual, Online
Duration: Dec 6 2020Dec 12 2020

Bibliographical note

Funding Information:
The authors graciously acknowledge the support from the DARPA YFA, Grant N66001-14-1-4047. The authors would also like to express their gratitude to Prof. Nikos Sidiropoulos and Di Xiao for their helpful discussions. The research work was undertaken when Sirisha Rambhatla was a doctoral student at the Department of Electrical and Computer Engineering, University of Minnesota – Twin Cities, Minneapolis, MN.

Funding Information:
The authors graciously acknowledge the support from the DARPA YFA, Grant N66001-14-1-4047. The authors would also like to express their gratitude to Prof. Nikos Sidiropoulos and Di Xiao for their helpful discussions. The research work was undertaken when Sirisha Rambhatla was a doctoral student at the Department of Electrical and Computer Engineering, University of Minnesota ? Twin Cities, Minneapolis, MN.

Publisher Copyright:
© 2020 Neural information processing systems foundation. All rights reserved.

Fingerprint

Dive into the research topics of 'Provable online CP/PARAFAC decomposition of a structured tensor via dictionary learning'. Together they form a unique fingerprint.

Cite this