Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
复制标题
DOI：
10.1109/tit.2017.2724549
复制
发表时间：
2016-06
影响因子：
2.5
通讯作者：
Ming Yuan;Cun-Hui Zhang
中科院分区：
文献类型：
--
作者：
Ming Yuan;Cun-Hui Zhang
本文研究了一类高阶张量补全的核范数最小化方法的样本量要求。我们通过允许不同级别的相干性来引入一类张量范数，这使我们能够利用张量的非相干性。特别地，我们证明了一个k阶张量，阶数为r，维数为d乘以cdots乘以d，可以通过适当的非相干核范数最小化，从最少$O((r^{(k-1)/2}d^{3/2}+r^{k-1}d)(\log (d))^{2})$均匀采样项中完全恢复。我们的结果证明了完成矩阵和高阶张量之间的一些关键区别：它们不仅指出了比通常的核范数最小化有改进的潜在空间，而且还强调了在处理高阶张量时明确考虑非相干性的重要性。虽然我们的重点主要集中在核规范最小化的理论保证上，但这些见解可能对理解其他相关方法的性能和开发改进的实际算法有用。
In this paper, we investigate the sample size requirement for a general class of nuclear norm minimization methods for higher order tensor completion. We introduce a class of tensor norms by allowing for different levels of coherence, which allows us to leverage the incoherence of a tensor. In particular, we show that a $k$ th-order tensor of multilinear rank $r$ and dimension $d \times \cdots \times d$ can be recovered perfectly from as few as $O((r^{(k-1)/2}d^{3/2}+r^{k-1}d)(\log (d))^{2})$ uniformly sampled entries through an appropriate incoherent nuclear norm minimization. Our results demonstrate some key differences between completing a matrix and a higher order tensor: they not only point to potential room for improvement over the usual nuclear norm minimization but also highlight the importance of explicitly accounting for incoherence, when dealing with higher order tensors. Although our focus is primarily on the theoretical guarantees for nuclear norm minimization, such insights may prove useful for understanding performance of other related methods and developing improved practical algorithms.