  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.
