Faster Robust Tensor Power Method for Arbitrary Order
Yichuan Deng Zhao Song Junze Yin
Tensor decomposition is a fundamental method used in various areas to deal
with high-dimensional data. \emph{Tensor power method} (TPM) is one of the
widely-used techniques in the decomposition of tensors. This paper presents a
novel tensor power method for decomposing arbitrary order tensors, which
overcomes limitations of existing approaches that are often restricted to
lower-order (less than $3$) tensors or require strong assumptions about the
underlying data structure. We apply sketching method, and we are able to
achieve the running time of $\widetilde{O}(n^{p-1})$, on the power $p$ and
dimension $n$ tensor. We provide a detailed analysis for any $p$-th order
tensor, which is never given in previous works.