Cross: Efficient Low-rank Tensor Completion
Cross: Efficient Low-rank Tensor Completion
复制标题
DOI：
10.1214/18-aos1694
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Anru R. Zhang
中科院分区：
文献类型：
--
作者：
Anru R. Zhang
张量或高阶数组的完备化在最近的研究中引起了极大的关注。目前关于张量完备化的文献主要集中在从一组均匀随机测量的条目中恢复，并且实现恢复所需的测量数量不能保证是最优的。此外，以前的一些方法的实现是NP难的。在这篇文章中，我们提出了一个框架，通过一个新的张量测量计划，我们命名为十字架低秩张量完成。所提出的程序是有效的，易于实施。特别地，我们证明了在p1 × p2 × p3维空间中，一个Tucker秩为-（r1，r2，r3）的三阶张量可以从少到r1 r2 r3 + r1（p1-r1）+r2（p2-r2）+r3（p3-r3）的无噪声测量中恢复出来，这与样本复杂度的下限相匹配.在噪声测量的情况下，我们还开发了一个理论上的上限和匹配的Minimax下界恢复误差在某些类别的低秩张量的建议的程序。结果可以进一步推广到四阶或更高阶张量。仿真研究表明，该方法在各种设置下都有很好的性能。最后，通过一个真实的神经影像数据集说明了该过程。
The completion of tensors, or high-order arrays, attracts significant attention in recent research. Current literature on tensor completion primarily focuses on recovery from a set of uniformly randomly measured entries, and the required number of measurements to achieve recovery is not guaranteed to be optimal. In addition, the implementation of some previous methods is NP-hard. In this article, we propose a framework for low-rank tensor completion via a novel tensor measurement scheme we name Cross. The proposed procedure is efficient and easy to implement. In particular, we show that a third order tensor of Tucker rank-$(r_1, r_2, r_3)$ in $p_1$-by-$p_2$-by-$p_3$ dimensional space can be recovered from as few as $r_1r_2r_3 + r_1(p_1-r_1) + r_2(p_2-r_2) + r_3(p_3-r_3)$ noiseless measurements, which matches the sample complexity lower-bound. In the case of noisy measurements, we also develop a theoretical upper bound and the matching minimax lower bound for recovery error over certain classes of low-rank tensors for the proposed procedure. The results can be further extended to fourth or higher-order tensors. Simulation studies show that the method performs well under a variety of settings. Finally, the procedure is illustrated through a real dataset in neuroimaging.