信息-计算鸿沟

张量PCA存在信息-计算鸿沟：当信噪比高于算法阈值时，谱方法和平方和等全局算法可在多项式时间内成功恢复；低于该阈值时，针对这些算法及某些受限计算模型的下界表明它们必然失败。

信息-计算鸿沟广泛存在于高维统计问题中，如稀疏主成分分析、种植团问题、社区检测等，是统计计算领域最核心的开放问题之一。