Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-$1$ Updates
This work addresses tensor decomposition, a fundamental problem in machine learning and data analysis, by offering theoretical guarantees for a simple algorithm, which is incremental as it builds on existing tensor power iteration methods.
The paper tackles the problem of recovering CP tensor decomposition by proposing an alternating rank-1 update algorithm, providing local and global convergence guarantees for overcomplete tensors under incoherence and rank conditions, with results extended to higher-order tensors and noisy settings.
In this paper, we provide local and global convergence guarantees for recovering CP (Candecomp/Parafac) tensor decomposition. The main step of the proposed algorithm is a simple alternating rank-$1$ update which is the alternating version of the tensor power iteration adapted for asymmetric tensors. Local convergence guarantees are established for third order tensors of rank $k$ in $d$ dimensions, when $k=o \bigl( d^{1.5} \bigr)$ and the tensor components are incoherent. Thus, we can recover overcomplete tensor decomposition. We also strengthen the results to global convergence guarantees under stricter rank condition $k \le βd$ (for arbitrary constant $β> 1$) through a simple initialization procedure where the algorithm is initialized by top singular vectors of random tensor slices. Furthermore, the approximate local convergence guarantees for $p$-th order tensors are also provided under rank condition $k=o \bigl( d^{p/2} \bigr)$. The guarantees also include tight perturbation analysis given noisy tensor.