Tensor SVD: Statistical and Computational Limits
This work addresses the fundamental challenge of tensor decomposition for data analysis, providing theoretical limits that are foundational for the field, though it is incremental in refining existing statistical and computational frameworks.
The paper tackles the problem of extracting low-rank structure from high-dimensional tensor data using tensor SVD, showing that the optimal estimation method depends on the signal-to-noise ratio (SNR), with higher-order orthogonal iteration achieving minimax optimal rates under strong SNR, non-convex maximum likelihood being optimal but NP-hard under moderate SNR, and consistent estimation being impossible under weak SNR.
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.