A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration

Abstract

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 Θ(\widehat{\U}_k, \U_k) \|_q$ for any $q\ge 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.

References in corpus (24)

• Tensor Decomposition for Signal Processing and Machine Learning
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• Tensor Regression with Applications in Neuroimaging Data Analysis
• Robust Low-rank Tensor Recovery: Models and Algorithms
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• A statistical model for tensor PCA
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
• Tensor principal component analysis via sum-of-squares proofs
• Provable Convex Co-clustering of Tensors
• A new convergence proof for the higher-order power method and generalizations
• Unperturbed: spectral analysis beyond Davis-Kahan
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Multiway clustering via tensor block models
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Characterizing Spatiotemporal Transcriptome of Human Brain via Low Rank Tensor Decomposition
• Tensor Methods for Additive Index Models under Discordance and Heterogeneity
• Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Interpolating Convex and Non-Convex Tensor Decompositions via the Subspace Norm
• Fast algorithms for Higher-order Singular Value Decomposition from incomplete data
• A Schatten-$q$ Low-rank Matrix Perturbation Analysis via Perturbation Projection Error Bound
• Tensor denoising and completion based on ordinal observations

Cited by in corpus (3)

• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• Power Iteration for Tensor PCA
• Long Random Matrices and Tensor Unfolding