# Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updates

arXiv: https://arxiv.org/abs/1402.5180 · HTML: https://mlsanity.com/paper/1402.5180/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2014.

## Built on by (most cited first, 21 of 21)

- [Reconstructing Training Data from Model Gradient, Provably](https://mlsanity.com/paper/2212.03714/) (2022)
- [Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms](https://mlsanity.com/paper/1802.07417/) (2018)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples](https://mlsanity.com/paper/2101.07150/) (2021)
- [Learning Good State and Action Representations via Tensor Decomposition](https://mlsanity.com/paper/2105.01136/) (2021)
- [Tensor Principal Component Analysis in High Dimensional CP Models](https://mlsanity.com/paper/2108.04428/) (2021)
- [Model based Multi-agent Reinforcement Learning with Tensor Decompositions](https://mlsanity.com/paper/2110.14524/) (2021)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Modelling matrix time series via a tensor CP-decomposition](https://mlsanity.com/paper/2112.15423/) (2021)
- [Finite Sample Identification of Wide Shallow Neural Networks with Biases](https://mlsanity.com/paper/2211.04589/) (2022)
- [Covariate-assisted Sparse Tensor Completion](https://mlsanity.com/paper/2103.06428/) (2021)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Learning Tensor Representations for Meta-Learning](https://mlsanity.com/paper/2201.07348/) (2022)
- [Multivariate Analysis for Multiple Network Data via Semi-Symmetric Tensor PCA](https://mlsanity.com/paper/2202.04719/) (2022)
- [Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Model](https://mlsanity.com/paper/2307.00575/) (2023)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Efficient Tensor Contraction via Fast Count Sketch](https://mlsanity.com/paper/2106.13062/) (2021)
- [On Spectral Learning for Odeco Tensors: Perturbation, Initialization, and Algorithms](https://mlsanity.com/paper/2509.25126/) (2025)
- [Guaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifold](https://mlsanity.com/paper/2510.00569/) (2025)
- [Dual-Channel Tensor Neural Networks: Finite-Sample Theory and Conformal Structure Selection](https://mlsanity.com/paper/2605.19122/) (2026)
- [Tensor Completion using Subspace Information](https://mlsanity.com/paper/2609.24501/) (2026)

## Abstract (arXiv)

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( d1.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 ≤ β 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( dp/2 bigr). The guarantees also include tight perturbation analysis given noisy tensor.