Nonconvex Low-Rank Symmetric Tensor Completion from Noisy Data
Nonconvex Low-Rank Symmetric Tensor Completion from Noisy Data
复制标题
DOI：
--
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Changxiao Cai;Gen Li;H. Poor;Yuxin Chen
中科院分区：
文献类型：
--
作者：
Changxiao Cai;Gen Li;H. Poor;Yuxin Chen
我们研究了广泛的实践兴趣的嘈杂对称张量的完成问题，即，从高度不完整和随机损坏其条目的观察结果中重建了低级别的对称张量。尽管已经针对此问题进行了各种先前的工作，但先前的算法要么在计算上对于大规模应用来说太昂贵了，要么带有优化的统计保证。为了关注恒定CP等级的“不连贯”和条件良好的张量，我们提出了一种两阶段的非convex算法----（香草）梯度下降，这是一个艰难的初始化，这实现了两全其最佳的世界。具体而言，提出的非凸算法忠实地完成了张量，并在几乎线性的时间内检索所有单个张量因子，同时享受近乎最佳的统计保证（即，最小的样本复杂性和最佳估计精度）。估计错误均匀分布在所有条目中，从而实现了最佳$ \ ell _ {\ infty} $统计精度。通过我们对非凸优化的分析传达的见解可能对其他张量估计问题有影响。
We study a noisy symmetric tensor completion problem of broad practical interest, namely, the reconstruction of a low-rank symmetric tensor from highly incomplete and randomly corrupted observations of its entries. While a variety of prior work has been dedicated to this problem, prior algorithms either are computationally too expensive for large-scale applications, or come with sub-optimal statistical guarantees. Focusing on "incoherent" and well-conditioned tensors of a constant CP rank, we propose a two-stage nonconvex algorithm --- (vanilla) gradient descent following a rough initialization --- that achieves the best of both worlds. Specifically, the proposed nonconvex algorithm faithfully completes the tensor and retrieves all individual tensor factors within nearly linear time, while at the same time enjoying near-optimal statistical guarantees (i.e. minimal sample complexity and optimal estimation accuracy). The estimation errors are evenly spread out across all entries, thus achieving optimal $\ell_{\infty}$ statistical accuracy. The insight conveyed through our analysis of nonconvex optimization might have implications for other tensor estimation problems.