Perturbation Bounds for (Nearly) Orthogonally Decomposable Tensors
This work provides foundational perturbation theory for tensors, impacting statistical and machine learning methods that rely on spectral learning of higher-order tensors.
The paper develops deterministic perturbation bounds for singular values and vectors of orthogonally decomposable tensors, showing that perturbations affect each singular value/vector in isolation, unlike matrices, and applies these results to derive optimal convergence rates for spectral learning in high-dimensional tensor SVD.
We develop deterministic perturbation bounds for singular values and vectors of orthogonally decomposable tensors, in a spirit similar to classical results for matrices such as those due to Weyl, Davis, Kahan and Wedin. Our bounds demonstrate intriguing differences between matrices and higher-order tensors. Most notably, they indicate that for higher-order tensors perturbation affects each essential singular value/vector in isolation, and its effect on an essential singular vector does not depend on the multiplicity of its corresponding singular value or its distance from other singular values. Our results can be readily applied and provide a unified treatment to many different problems in statistics and machine learning involving spectral learning of higher-order orthogonally decomposable tensors. In particular, we illustrate the implications of our bounds in the context of high dimensional tensor SVD problem, and how it can be used to derive optimal rates of convergence for spectral learning.