张量PCA

张量PCA问题定义在球面S_N上：给定未知向量的k阶张量幂的带噪观测（k≥3固定），目标是恢复该未知向量。

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

此前学界普遍认为局部算法（如马尔可夫链）在张量PCA中表现远逊于全局算法，仅知道在随机初始化下需要多项式级更高的信噪比才能成功。

在张量PCA中，谱方法在信噪比高于算法阈值时成功，SoS在相同阈值下也成功，且SoS下界表明低于该阈值任何SoS算法均失败。