2015/01/28 by Ignat Domanov, Domanov, Ignat, Lieven De Lathauwer +1 · 1 citation
Computer Science · Mathematics · #15A23 #15A69 #Algorithms and Data Compression #FOS: Mathematics #Matrix Theory and Algorithms #Spectral Theory (math.SP) #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.1501.07251
openalex publication_date 2015/01/28 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
Canonical Polyadic Decomposition (CPD) of a third-order tensor is a minimal\ndecomposition into a sum of rank-1 tensors. We find new mild deterministic\nconditions for the uniqueness of individual rank-1 tensors in CPD and present\nan algorithm to recover them. We call the algorithm "algebraic" because it\nrelies only on standard linear algebra. It does not involve more advanced\nprocedures than the computation of the null space of a matrix and\neigen/singular value decomposition. Simulations indicate that the new\nconditions for uniqueness and the working assumptions for the algorithm hold\nfor a randomly generated I\× J\× K tensor of rank R\≥ K\≥ J\≥\nI\≥ 2 if R is bounded as R\≤ (I+J+K-2)/2 + (K-\√((I-J)2+4K))/2 at\nleast for the dimensions that we have tested. This improves upon the famous\nKruskal bound for uniqueness R\≤ (I+J+K-2)/2 as soon as I\≥ 3.\n In the particular case R=K, the new bound above is equivalent to the bound\nR\≤(I-1)(J-1) which is known to be necessary and sufficient for the generic\nuniqueness of the CPD. An existing algebraic algorithm (based on simultaneous\ndiagonalization of a set of matrices) computes the CPD under the more\nrestrictive constraint R(R-1)\≤ I(I-1)J(J-1)/2 (implying that\nR<(J-\(1)/(2))(I-\(1)/(2))/\√(2)+1). On the other hand,\noptimization-based algorithms fail to compute the CPD in a reasonable amount of\ntime even in the low-dimensional case I=3, J=7, K=R=12. By comparison, in\nour approach the computation takes less than 1 sec. We demonstrate that, at\nleast for R\≤ 24, our algorithm can recover the rank-1 tensors in the CPD\nup to R\≤(I-1)(J-1).\n