Tensor SVD: Statistical and Computational Limits

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.

Typos fixed

References in corpus (9)

• A statistical model for tensor PCA
• Computational Lower Bounds for Sparse PCA
• 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

Cited by in corpus (3)

• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Optimal link prediction with matrix logistic regression
• Covariate-Adjusted Tensor Classification in High-Dimensions