Tensor SVD: Statistical and Computational Limits
arXiv:1703.02724
Abstract
In this paper, we propose a general framework for tensor singular value decomposition (tensor SVD), which focuses on the methodology and theory for extracting the hidden low-rank structure from high-dimensional tensor data. Comprehensive results are developed on both the statistical and computational limits for tensor SVD. This problem exhibits three different phases according to the signal-to-noise ratio (SNR). In particular, with strong SNR, we show that the classical higher-order orthogonal iteration achieves the minimax optimal rate of convergence in estimation; with weak SNR, the information-theoretical lower bound implies that it is impossible to have consistent estimation in general; with moderate SNR, we show that the non-convex maximum likelihood estimation provides optimal solution, but with NP-hard computational cost; moreover, under the hardness hypothesis of hypergraphic planted clique detection, there are no polynomial-time algorithms performing consistently in general.
arXiv commentTypos fixed
References in corpus (18)
- Tensor Regression with Applications in Neuroimaging Data Analysis
- Sparse PCA: Optimal rates and adaptive estimation
- Optimal detection of sparse principal components in high dimension
- Unbiased Risk Estimates for Singular Value Thresholding and Spectral Estimators
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Minimax risk of matrix denoising by singular value thresholding
- Computational barriers in minimax submatrix detection
- Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank- Updates
- A statistical model for tensor PCA
- Computational Lower Bounds for Sparse PCA
- Sparse CCA: Adaptive Estimation and Computational Barriers
- Optimal Estimation of Low Rank Density Matrices
- Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
- Regularized Tensor Factorizations and Higher-Order Principal Components Analysis
- Characterizing Spatiotemporal Transcriptome of Human Brain via Low Rank Tensor Decomposition
- Homotopy Analysis for Tensor PCA
- Interpolating Convex and Non-Convex Tensor Decompositions via the Subspace Norm
- Cross: Efficient Low-rank Tensor Completion