# When Does Non-Orthogonal Tensor Decomposition Have No Spurious Local Minima?

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2019.

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

- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Landscape analysis of an improved power method for tensor decomposition](https://mlsanity.com/paper/2110.15821/) (2021)
- [WGAN with an Infinitely Wide Generator Has No Spurious Stationary Points](https://mlsanity.com/paper/2102.07541/) (2021)

## Abstract (arXiv)

We study the optimization problem for decomposing d dimensional fourth-order Tensors with k non-orthogonal components. We derive textitdeterministic conditions under which such a problem does not have spurious local minima. In particular, we show that if kappa = fracλmaxλmin < frac54, and incoherence coefficient is of the order O(frac1√d), then all the local minima are globally optimal. Using standard techniques, these conditions could be easily transformed into conditions that would hold with high probability in high dimensions when the components are generated randomly. Finally, we prove that the tensor power method with deflation and restarts could efficiently extract all the components within a tolerance level O(kappa √kτ3) that seems to be the noise floor of non-orthogonal tensor decomposition.