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

Authors: 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

Recommendations

• Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition
• On Uniqueness of the nth Order Tensor Decomposition into Rank-1 Terms with Linear Independence in One Mode
• On the uniqueness of the canonical polyadic decomposition of third-order tensors. I: Basic results and uniqueness of one factor matrix
• On Uniqueness of the Canonical Tensor Decomposition with Some Form of Symmetry
• New Uniqueness Conditions for the Canonical Polyadic Decomposition of Third-Order Tensors

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 (38)

• An ATLD-ALS method for the trilinear decomposition of large third-order tensors
• An algebraic solution for the Candecomp/PARAFAC decomposition with circulant factors
• New Uniqueness Conditions for the Canonical Polyadic Decomposition of Third-Order Tensors
• Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms
• Decomposition of a tensor into multilinear rank-\((M_r,N_r,\cdot)\) terms
• Minimality and uniqueness for decompositions of specific ternary forms
• Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-\((L_r,L_r,1)\) terms, and a new generalization
• Pencil-based algorithms for tensor rank decomposition are not stable
• Overcomplete order-3 tensor decomposition, blind deconvolution, and Gaussian mixture models
• Rank of a tensor and quantum entanglement
• Solving systems of polynomial equations -- a tensor approach
• Canonical polyadic decomposition with a columnwise orthonormal factor matrix
• Coupled canonical polyadic decompositions and (coupled) decompositions in multilinear rank-\((L_{r,n},L_{r,n},1)\) terms. II: Algorithms
• 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
• An iterative algorithm for third-order tensor multi-rank minimization
• A recursive eigenspace computation for the canonical polyadic decomposition
• Computing the unique CANDECOMP/PARAFAC decomposition of unbalanced tensors by homotopy method
• Triple decomposition and tensor recovery of third order tensors
• Improved Uniqueness Conditions for Canonical Tensor Decompositions with Linearly Dependent Loadings
• Identifiability of rank-3 tensors
• A CAS aided survey of CP decomposition and rank-1 approxition of a 3rd-order tensor
• Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition
• High-order tensor estimation via trains of coupled third-order CP and Tucker decompositions
• Computing the polyadic decomposition of nonnegative third order tensors
• \((L_r,L_r,1)\)-decompositions, sparse component analysis, and the blind separation of sums of exponentials
• 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
• 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
• Coherent signal parameter estimation by exploiting decomposition of tensors
• Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition
• A robust Parafac model for compositional data
• A Riemannian gradient ascent algorithm with applications to orthogonal approximation problems of symmetric tensors
• The power of tensor-based approaches in cardiac applications
• Fiber sampling approach to canonical polyadic decomposition and application to tensor completion

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)