Provable Sparse Tensor Decomposition

• Activity Number: 656
• Type: Contributed
• Date/Time: Thursday, August 13, 2015 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Wei Sun* and Junwei Lu and Han Liu and Guang Cheng
• Companies: Purdue University and Princeton University and Princeton University and Purdue University
• Keywords: High dimensional data ; Global convergence ; Truncated power method ; Tensor decomposition ; Variable selection

Abstract

We propose a novel sparse tensor decomposition algorithm which naturally incorporates sparsity structure into the decomposition component. The sparsity is achieved via a truncation procedure which directly addresses the cardinality constraint. With an appropriate initialization, our algorithm obtains a tight local convergence rate of the decomposition estimator. We further strengthen this result to the global convergence by initializing via a simple sparse singular value decomposition procedure. In high dimensional regimes, the obtained rate of convergence significantly improves the rates shown in existing non-sparse decomposition algorithms. Moreover, the proposed algorithm is applicable to solve a broad family of high dimensional latent variable models, including high dimensional gaussian mixture model and mixtures of linear sparse regressions. Extensive experiments further demonstrate the superior performance of our algorithm in both estimation accuracy and variable selection performance of tensor decomposition.