Canonical polyadic decomposition of third-order tensors: relaxed uniqueness conditions and algebraic algorithm

DOI10.1016/J.LAA.2016.10.019zbMATH Open1349.15065arXiv1501.07251OpenAlexW2964313686WikidataQ60307029 ScholiaQ60307029MaRDI QIDQ344915FDOQ344915

Lieven De Lathauwer, Ignat Domanov

Publication date: 25 November 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: Canonical Polyadic Decomposition (CPD) of a third-order tensor is a minimal decomposition into a sum of rank-$1$ tensors. We find new mild deterministic conditions for the uniqueness of individual rank-$1$ tensors in CPD and present an algorithm to recover them. We call the algorithm "algebraic" because it relies only on standard linear algebra. It does not involve more advanced procedures than the computation of the null space of a matrix and eigen/singular value decomposition. Simulations indicate that the new conditions for uniqueness and the working assumptions for the algorithm hold for a randomly generated $IimesJimesK$ tensor of rank $RgeqKgeqJgeqIgeq2$ if $R$ is bounded as $Rleq(I+J+K-2)/2+(K-sqrt(I-J{)}^2+4K)/2$ at least for the dimensions that we have tested. This improves upon the famous Kruskal bound for uniqueness $Rleq(I+J+K-2)/2$ as soon as $Igeq3$. In the particular case $R=K$, the new bound above is equivalent to the bound $Rleq(I-1)(J-1)$ which is known to be necessary and sufficient for the generic uniqueness of the CPD. An existing algebraic algorithm (based on simultaneous diagonalization of a set of matrices) computes the CPD under the more restrictive constraint $R(R-1)leqI(I-1)J(J-1)/2$ (implying that $R<(J-frac12)(I-frac12)/sqrt2+1$). On the other hand, optimization-based algorithms fail to compute the CPD in a reasonable amount of time even in the low-dimensional case $I=3$, $J=7$, $K=R=12$. By comparison, in our approach the computation takes less than $1$ sec. We demonstrate that, at least for $Rleq24$, our algorithm can recover the rank-$1$ tensors in the CPD up to $Rleq(I-1)(J-1)$.

Full work available at URL: https://arxiv.org/abs/1501.07251

zbMATH Keywords

tensoreigenvalue decompositionsingular value decompositionCANDECOMP/PARAFAC decompositioncanonical polyadic decompositionCP decompositionuni-mode uniquenessuniqueness of CPD

Mathematics Subject Classification ID

Factorization of matrices (15A23) Multilinear algebra, tensor calculus (15A69)

Cites Work

• PARAFAC: Parallel factor analysis
• Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
• Tensor Decompositions and Applications
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• On the uniqueness of the canonical polyadic decomposition of third-order tensors. I: Basic results and uniqueness of one factor matrix
• On the uniqueness of the canonical polyadic decomposition of third-order tensors. II: Uniqueness of the overall decomposition
• Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition
• Generic Uniqueness Conditions for the Canonical Polyadic Decomposition and INDSCAL
• A Link between the Canonical Decomposition in Multilinear Algebra and Simultaneous Matrix Diagonalization
• Kruskal's Permutation Lemma and the Identification of CANDECOMP/PARAFAC and Bilinear Models with Constant Modulus Constraints
• Uni-mode uniqueness conditions for CANDECOMP/PARAFAC decomposition of \(n\)-way arrays with linearly dependent loadings
• Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-\((L_r,L_r,1)\) terms, and a new generalization
• Uni-mode and partial uniqueness conditions for CANDECOMP/PARAFAC of three-way arrays with linearly dependent loadings
• A Decomposition for Three-Way Arrays
• On Generic Identifiability of 3-Tensors of Small Rank

Cited In (25)

• An ATLD-ALS method for the trilinear decomposition of large third-order tensors
• New Uniqueness Conditions for the Canonical Polyadic Decomposition of Third-Order Tensors
• Decomposition of a tensor into multilinear rank-\((M_r,N_r,\cdot)\) terms
• A Recursive Eigenspace Computation for the Canonical Polyadic Decomposition
• Minimality and uniqueness for decompositions of specific ternary forms
• The Power of Tensor-Based Approaches in Cardiac Applications
• Rank of a tensor and quantum entanglement
• Solving systems of polynomial equations -- a tensor approach
• $(L_r,L_r,1)$-Decompositions, Sparse Component Analysis, and the Blind Separation of Sums of Exponentials
• On the identifiability of ternary forms
• Bilinear factorizations subject to monomial equality constraints via tensor decompositions
• A note on nonclosed tensor formats
• A normal form algorithm for tensor rank decomposition
• Computing the unique CANDECOMP/PARAFAC decomposition of unbalanced tensors by homotopy method
• Fiber Sampling Approach to Canonical Polyadic Decomposition and Application to Tensor Completion
• Improved Uniqueness Conditions for Canonical Tensor Decompositions with Linearly Dependent Loadings
• Identifiability of rank-3 tensors
• High-order tensor estimation via trains of coupled third-order CP and Tucker decompositions
• Online subspace learning and imputation by tensor-ring decomposition
• Line search and trust region strategies for canonical decomposition of semi-nonnegative semi-symmetric 3rd order tensors
• Coherent signal parameter estimation by exploiting decomposition of tensors
• Overcomplete Order-3 Tensor Decomposition, Blind Deconvolution, and Gaussian Mixture Models
• Pencil-Based Algorithms for Tensor Rank Decomposition are not Stable
• A robust Parafac model for compositional data
• A Riemannian gradient ascent algorithm with applications to orthogonal approximation problems of symmetric tensors

Uses Software

• PARAFAC

This page was built for publication: Canonical polyadic decomposition of third-order tensors: relaxed uniqueness conditions and algebraic algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344915)