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

Abstract

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\left(d^{1.5}\right)$ 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 \beta d$ (for arbitrary constant $\beta >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\left(d^{p/2}\right)$. The guarantees also include tight perturbation analysis given noisy tensor.

We have added an additional sub-algorithm to remove the (approximate) residual error left after the tensor power iteration

Cited by in corpus (25)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• When Are Nonconvex Problems Not Scary?
• The Non-convex Geometry of Low-rank Matrix Optimization
• Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
• Analyzing Tensor Power Method Dynamics in Overcomplete Regime
• Tensorial Neural Networks: Generalization of Neural Networks and Application to Model Compression
• Convolutional Phase Retrieval via Gradient Descent
• Tensor Methods for Additive Index Models under Discordance and Heterogeneity
• Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use
• Factor Models for High-Dimensional Tensor Time Series
• Training Input-Output Recurrent Neural Networks through Spectral Methods
• Provable Tensor Methods for Learning Mixtures of Generalized Linear Models
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition
• Efficient Dictionary Learning with Gradient Descent
• An end-to-end Differentially Private Latent Dirichlet Allocation Using a Spectral Algorithm
• Guaranteed Simultaneous Asymmetric Tensor Decomposition via Orthogonalized Alternating Least Squares
• Provable Sparse Tensor Decomposition
• Strongly Refuting Random CSPs Below the Spectral Threshold
• Tensor SVD: Statistical and Computational Limits
• Optimal Sparse Singular Value Decomposition for High-dimensional High-order Data
• Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data
• Dynamic Tensor Clustering
• Evaluation of Spectral Learning for the Identification of Hidden Markov Models