论文标题
张量完成使实用
Tensor Completion Made Practical
论文作者
论文摘要
张量完成是矩阵完成的自然高阶概括，其目标是从稀疏观察结果中恢复低级数张量。现有算法是没有可证明的保证的启发式算法，基于解决不切实际的大型半决赛计划，或者做出诸如要求这些因素几乎是正交的诸如诸如需要正交的假设。在本文中，我们介绍了一种交替最小化的新变体，这反过来又是通过了解如何将最小化在矩阵设置中的交替最小化收敛的方法进行的启发，需要适应张量设置。我们表现出强大的可证明保证，包括表明我们的算法即使因素高度相关并可以在几乎线性的时间内实施，我们的算法也将线性收敛到真正的张量。此外，我们的算法也非常实用，我们表明我们可以通过观察一小部分条目来完成三阶张量。相比之下，有些令人惊讶的是，我们表明，在没有新扭曲的情况下，交替的最小化的标准版本可以在实践中以较慢的速度收敛。
Tensor completion is a natural higher-order generalization of matrix completion where the goal is to recover a low-rank tensor from sparse observations of its entries. Existing algorithms are either heuristic without provable guarantees, based on solving large semidefinite programs which are impractical to run, or make strong assumptions such as requiring the factors to be nearly orthogonal. In this paper we introduce a new variant of alternating minimization, which in turn is inspired by understanding how the progress measures that guide convergence of alternating minimization in the matrix setting need to be adapted to the tensor setting. We show strong provable guarantees, including showing that our algorithm converges linearly to the true tensors even when the factors are highly correlated and can be implemented in nearly linear time. Moreover our algorithm is also highly practical and we show that we can complete third order tensors with a thousand dimensions from observing a tiny fraction of its entries. In contrast, and somewhat surprisingly, we show that the standard version of alternating minimization, without our new twist, can converge at a drastically slower rate in practice.
