论文标题
张量完成，几乎是线性样品，给出弱侧信息
Tensor Completion with Nearly Linear Samples Given Weak Side Information
论文作者
论文摘要
就执行张量估计所需的样品数量而言，张量完成表现出有趣的计算统计差距。虽然只有$θ（TN）$ t $ order tensor，带有$ n^t $条目，但最著名的多项式时间算法需要$ o（n^{t/2}）$样本，以保证一致的估计。在本文中，我们表明弱侧信息足以将样本复杂性降低到$ o（n）$。侧面信息由每个模式的权重矢量组成，这与该模式沿该模式的任何潜在因素都不是正交的；这比假设子空间的嘈杂知识要弱得多。我们提供了一种利用此侧面信息的算法，以$ O（N^{1+κ}）$样品生成一致的估计器，以适用于任何小常数$κ> 0 $。我们还提供有关验证我们理论见解的合成数据集和现实世界数据集的实验。
Tensor completion exhibits an interesting computational-statistical gap in terms of the number of samples needed to perform tensor estimation. While there are only $Θ(tn)$ degrees of freedom in a $t$-order tensor with $n^t$ entries, the best known polynomial time algorithm requires $O(n^{t/2})$ samples in order to guarantee consistent estimation. In this paper, we show that weak side information is sufficient to reduce the sample complexity to $O(n)$. The side information consists of a weight vector for each of the modes which is not orthogonal to any of the latent factors along that mode; this is significantly weaker than assuming noisy knowledge of the subspaces. We provide an algorithm that utilizes this side information to produce a consistent estimator with $O(n^{1+κ})$ samples for any small constant $κ> 0$. We also provide experiments on both synthetic and real-world datasets that validate our theoretical insights.
