Provable Sparse Tensor Decomposition
arXiv:1502.01425
Abstract
We propose a novel sparse tensor decomposition method, namely Tensor Truncated Power (TTP) method, that incorporates variable selection into the estimation of decomposition components. The sparsity is achieved via an efficient truncation step embedded in the tensor power iteration. Our method applies to a broad family of high dimensional latent variable models, including high dimensional Gaussian mixture and mixtures of sparse regressions. A thorough theoretical investigation is further conducted. In particular, we show that the final decomposition estimator is guaranteed to achieve a local statistical rate, and further strengthen it to the global statistical rate by introducing a proper initialization procedure. In high dimensional regimes, the obtained statistical rate significantly improves those shown in the existing non-sparse decomposition methods. The empirical advantages of TTP are confirmed in extensive simulated results and two real applications of click-through rate prediction and high-dimensional gene clustering.
arXiv commentTo Appear in JRSS-B
References in corpus (15)
- Sparsity and Incoherence in Compressive Sampling
- Tensor Regression with Applications in Neuroimaging Data Analysis
- On Tensors, Sparsity, and Nonnegative Factorizations
- Truncated Power Method for Sparse Eigenvalue Problems
- Polynomial Learning of Distribution Families
- A New Convex Relaxation for Tensor Completion
- Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank- Updates
- Alternating Minimization for Mixed Linear Regression
- Consistent selection of tuning parameters via variable selection stability
- Numerical Optimization for Symmetric Tensor Decomposition
- Settling the Polynomial Learnability of Mixtures of Gaussians
- High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
- Bayesian Conditional Tensor Factorizations for High-Dimensional Classification
- On Tensor Completion via Nuclear Norm Minimization
- Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method