When Does Non-Orthogonal Tensor Decomposition Have No Spurious Local Minima?
This addresses a fundamental optimization challenge in machine learning and data analysis for researchers and practitioners working with tensor decompositions, providing theoretical guarantees for global convergence in non-orthogonal settings.
The paper tackles the problem of non-orthogonal tensor decomposition by deriving deterministic conditions under which the optimization has no spurious local minima, showing that if the condition number κ < 5/4 and incoherence is O(1/√d), all local minima are globally optimal, and it proves that the tensor power method can extract components within a tolerance of O(κ√(kτ³)).
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 $κ= \frac{λ_{max}}{λ_{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(κ\sqrt{kτ^3})$ that seems to be the noise floor of non-orthogonal tensor decomposition.