# A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration

arXiv: https://arxiv.org/abs/2008.02437 · HTML: https://mlsanity.com/paper/2008.02437/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2020.

## Built on by (most cited first, 5 of 5)

- [Long Random Matrices and Tensor Unfolding](https://mlsanity.com/paper/2110.10210/) (2021)
- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [Signed Diverse Multiplex Networks: Clustering and Inference](https://mlsanity.com/paper/2402.10242/) (2024)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Perfect Clustering in Very Sparse Diverse Multiplex Networks](https://mlsanity.com/paper/2507.19423/) (2025)

## Abstract (arXiv)

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 |widehatbcT - bcT |tHS and mode-k singular subspace estimation in Schatten-q norm | sin Theta (widehatUk, Uk) |q for any q ≥ 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.