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

DOI10.1016/J.LAA.2016.10.019MaRDI QIDQ344915zbMATH OpenOpenAlexWikidataFDO

Authors Lieven De Lathauwer, Ignat Domanov

Publication date 25 November 2016

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

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)

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)$.

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

Cites work

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

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
• Solving systems of polynomial equations -- a tensor approach
• Rank of a tensor and quantum entanglement
• Canonical polyadic decomposition with a columnwise orthonormal factor matrix
• On the identifiability of ternary forms
• Coupled canonical polyadic decompositions and (coupled) decompositions in multilinear rank-\((L_{r,n},L_{r,n},1)\) terms. II: Algorithms
• 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
• Identifiability of rank-3 tensors
• Triple decomposition and tensor recovery of third order tensors
• Improved Uniqueness Conditions for Canonical Tensor Decompositions with Linearly Dependent Loadings
• 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
• Computing the polyadic decomposition of nonnegative third order tensors
• High-order tensor estimation via trains of coupled third-order CP and Tucker decompositions
• Line search and trust region strategies for canonical decomposition of semi-nonnegative semi-symmetric 3rd 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
• Coherent signal parameter estimation by exploiting decomposition of 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
• 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

Describes a project that uses

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)