Tensor SVD: Statistical and Computational Limits
Tensor SVD: Statistical and Computational Limits
复制标题
DOI：
10.1109/tit.2018.2841377
复制
发表时间：
2017-03
影响因子：
2.5
通讯作者：
Anru R. Zhang;Dong Xia
中科院分区：
文献类型：
--
作者：
Anru R. Zhang;Dong Xia
本文提出了张量奇异值分解的一般框架(张量奇异值分解(SVD))，重点研究了从高维张量数据中提取隐藏的低阶结构的方法和理论。给出了张量奇异值分解的统计极限和计算极限的综合结果。根据信噪比(SNR)的不同，该问题呈现出三个不同的阶段。特别地，在高信噪比下，我们证明了经典的高阶正交迭代在估计中达到了极小极大最优收敛速度；在弱信噪比下，信息论下界意味着一般不可能有一致的估计；在中等信噪比下，我们证明了非凸最大似然估计提供了最优解，但具有NP-Hard计算代价；此外，在超图植入团检测的困难假设下，没有多项式时间算法在一般情况下执行一致。
In this paper, we propose a general framework for tensor singular value decomposition (tensor singular value decomposition (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.