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

Abstract

We study the optimization problem for decomposing $d$ dimensional fourth-order Tensors with $k$ non-orthogonal components. We derive \textit{deterministic} conditions under which such a problem does not have spurious local minima. In particular, we show that if $\kappa =\frac{{\lambda }_{max}}{{\lambda }_{min}}<\frac{5}{4}$, and incoherence coefficient is of the order $O(\frac{1}{\sqrt{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 \sqrt{k{\tau }^3})$ that seems to be the noise floor of non-orthogonal tensor decomposition.

References in corpus (3)

• Gradient Descent Converges to Minimizers
• Learning Mixtures of Gaussians in High Dimensions
• Model Selection for Topic Models via Spectral Decomposition

Cited by in corpus (5)

• From Symmetry to Geometry: Tractable Nonconvex Problems
• Analysis of the Optimization Landscapes for Overcomplete Representation Learning
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• Landscape analysis of an improved power method for tensor decomposition
• WGAN with an Infinitely Wide Generator Has No Spurious Stationary Points