A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
复制标题
DOI：
--
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Yuetian Luo;Garvesh Raskutti;M. Yuan;Anru R. Zhang
中科院分区：
文献类型：
--
作者：
Yuetian Luo;Garvesh Raskutti;M. Yuan;Anru R. Zhang
在本文中，我们开发了新的扰动界的高阶正交迭代（HOOI）[DLDMV 00 b]。在温和的正则性条件下，我们建立了HOOI的分块张量扰动界，并保证了对于任意的$q \geq 1$，张量重构满足Hilbert-Schmidt范数$\|\widehat{\bcT\|_{\tHS}$，奇异子空间估计满足Schatten-$q$范数$\| \sin \Theta（\widehat{\U}_k，\U_k）\|_q$.我们的模式$k$奇异子空间估计的上界是单边的，并线性收敛到一个数量，其特征在于块的扰动和信号强度的错误。对于张量重建误差界，我们通过一个简单的量$\xi$，它只依赖于扰动和多线性秩的基础信号表示的界。速率匹配的确定性下界的张量重建，这表明HOOI的最优性，也提供了。此外，我们证明了一步HOOI（即，HOOI仅具有单次迭代）在张量重建方面也是最佳的，并且可以用于降低计算成本。扰动结果也被推广到只有部分模式的$\bcT$具有低秩结构的情况。我们支持我们的理论结果进行了广泛的数值研究。最后，我们将HOOI的新扰动界应用于机器学习和统计的两个应用，张量去噪和张量共聚类，这表明了新扰动结果的优越性。
In this paper, we develop novel perturbation bounds for the high-order orthogonal iteration (HOOI) [DLDMV00b]. Under mild regularity conditions, we establish blockwise tensor perturbation bounds for HOOI with guarantees for both tensor reconstruction in Hilbert-Schmidt norm $\|\widehat{\bcT} - \bcT \|_{\tHS}$ and mode-$k$ singular subspace estimation in Schatten-$q$ norm $\| \sin \Theta (\widehat{\U}_k, \U_k) \|_q$ for any $q \geq 1$. We show the upper bounds of mode-$k$ singular subspace estimation are unilateral and converge linearly to a quantity characterized by blockwise errors of the perturbation and signal strength. For the tensor reconstruction error bound, we express the bound through a simple quantity $\xi$, which depends only on perturbation and the multilinear rank of the underlying signal. Rate matching deterministic lower bound for tensor reconstruction, which demonstrates the optimality of HOOI, is also provided. Furthermore, we prove that one-step HOOI (i.e., HOOI with only a single iteration) is also optimal in terms of tensor reconstruction and can be used to lower the computational cost. The perturbation results are also extended to the case that only partial modes of $\bcT$ have low-rank structure. We support our theoretical results by extensive numerical studies. Finally, we apply the novel perturbation bounds of HOOI on two applications, tensor denoising and tensor co-clustering, from machine learning and statistics, which demonstrates the superiority of the new perturbation results.