Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition

Abstract

Canonical Polyadic Decomposition (CPD) of a third-order tensor is decomposition in a minimal number of rank-$1$ tensors. We call an algorithm algebraic if it is guaranteed to find the decomposition when it is exact and if it only relies on standard linear algebra (essentially sets of linear equations and matrix factorizations). The known algebraic algorithms for the computation of the CPD are limited to cases where at least one of the factor matrices has full column rank. In the paper we present an algebraic algorithm for the computation of the CPD in cases where none of the factor matrices has full column rank. In particular, we show that if the famous Kruskal condition holds, then the CPD can be found algebraically.

32 pages = 25 pages of paper itself + 7 pages of supplementary materials

Cited by in corpus (25)

• Tensor Decomposition for Signal Processing and Machine Learning
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• Tensor Completion from Regular Sub-Nyquist Samples
• Decoupling Multivariate Polynomials Using First-Order Information
• Double Coupled Canonical Polyadic Decomposition for Joint Blind Source Separation
• Effective criteria for specific identifiability of tensors and forms
• Estimating multivariate latent-structure models
• Modelling matrix time series via a tensor CP-decomposition
• Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective
• A condition number for the tensor rank decomposition
• Pencil-based algorithms for tensor rank decomposition are not stable
• Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization
• Personalized Coupled Tensor Decomposition for Multimodal Data Fusion: Uniqueness and Algorithms
• A generalization of Kruskal's theorem on tensor decomposition
• Tensor decomposition for learning Gaussian mixtures from moments
• Guaranteed Simultaneous Asymmetric Tensor Decomposition via Orthogonalized Alternating Least Squares
• A Normal Form Algorithm for Tensor Rank Decomposition
• Hankel tensor decompositions and ranks
• Low Rank Approximation of Tensors via Sparse Optimization
• Finding a low-rank basis in a matrix subspace
• Generic identifiability of pairs of ternary forms
• Toward a generalization of Kruskal's theorem on tensor decomposition
• Rank Approximation of a Tensor with Applications in Color Image and Video Processing
• CP-TT: using TT-SVD to greedily construct a Canonical Polyadic tensor approximation
• Low Rank Symmetric Tensor Approximations