Source-linked AI summary
An algorithm for generic and low-rank specific identifiability of complex tensors
Luca Chiantini, Giorgio Ottaviani, Nick Vannieuwenhoven
TL;DR
Tensor-decomposition uniqueness is important in applications, but its theoretical foundations remain incomplete. The paper develops an algebraic-geometric condition and algorithm, establishing generic identifiability in many spaces below dimension 15000 and extending the approach to specific decompositions when nonsingularity is shown.
Problem
Tensor rank-decomposition uniqueness matters in applications, while its theoretical foundations and tests for identifiability remain incomplete.
Source: §1 · pp. 1–2Method
Results
In spaces of dimension less than 15000, the algorithm verifies generic identifiability for subgeneric ranks except known cases; it also proves a specific 5×5×5 tensor of rank 7 identifiable.
Source: §1 · p. 4, §6 · p. 20Takeaways & Limitations
For specific identifiability, the criterion can in principle reach the optimal rank when a suitable nonsingularity test is available.
Source: §6 · p. 20Little is known about singularities of Segre secant varieties, limiting the specific cases currently verifiable and only slightly improving existing ranges.
Source: §6 · p. 20
Abstract
from arXiv · showhide
We propose a new sufficient condition for verifying whether generic rank-r complex tensors of arbitrary order admit a unique decomposition as a linear combination of rank-1 tensors. A practical algorithm is proposed for verifying this condition, with which it was established that in all spaces of dimension less than 15000, with a few known exceptions, listed in the paper, generic identifiability holds for ranks up to one less than the generic rank of the space. This is the largest possible rank value for which generic identifiability can hold, except for spaces with a perfect shape. The algorithm can also verify the identifiability of a given specific rank-r decomposition, provided that it can be shown to correspond to a nonsingular point of the r-th order secant variety. For sufficiently small rank, which nevertheless improves upon the known bounds for specific identifiability, some local equations of this variety are known, allowing us to verify this property. As a particular example of our approach, we prove the identifiability of a specific 5x5x5 tensor of rank 7, which cannot be handled by the conditions recently provided in [I. Domanov and L. De Lathauwer, On the Uniqueness of the Canonical Polyadic Decomposition of third-order tensors--Part II: Uniqueness of the overall decomposition, SIAM J. Matrix Anal. Appl. 34(3), 2013]. Finally, we also present a surprising new class of weakly-defective Segre varieties that nevertheless turns out to admit a generically unique decomposition.
1. Introduction
The introduction frames tensor identifiability as important for applications and theoretically incompletely understood, then presents a new condition and algorithm for generic identifiability. It also extends the approach to specific decompositions when nonsingularity can be established.
1. Introduction
- Identifiability matters in practice because rank-decomposition uniqueness is tied to recovering chemical-component emission-excitation spectra.Source: §1 · p. 1
- Earlier specific-identifiability criteria include Kruskal’s condition, while theoretical foundations remain incomplete and cited criteria are weak for cubic tensors.The introduction also notes stronger generic results for cubic tensors by Strassen, extended to any n in.Source: §1 · p. 2
- The condition targets the largest possible subgeneric rank; generic (r + 1)-identifiability does not hold beyond that bound, except for perfect shapes.The algorithm is not designed to handle the (r + 1)-secant in the perfect-shape case.Source: §1 · p. 3
- Using the proposed algorithm, the authors verified generic r-identifiability for a large number of complex tensor spaces, providing additional evidence that ’s list is complete for the varieties tested.Source: §1 · p. 3
- For specific identifiability, the generic algorithm applies when a rank-r decomposition is a nonsingular point of the secant variety; local equations can test this at low order.The paper demonstrates the approach on an identifiable 5×5×5 tensor of rank 7.Source: §1 · p. 4
2. A sufficient condition for generic identifiability
The section gives a sufficient condition for generic identifiability based on the tangential contact locus and a practical Hessian-based test. It also identifies Segre varieties that remain generically identifiable despite weak defectivity.
2. A sufficient condition for generic identifiability
- The algorithm constructs Cartesian equations for the tangential contact locus and uses linear and multilinear operations to test the condition.Its Hessian computation determines the local dimension of the contact locus.Source: §2 · pp. 4, 7
- For a nondefective variety, generic non-identifiability implies that the tangential contact locus contains a curve through the general decomposition points.Thus, a zero-dimensional contact locus supplies the sufficient identifiability test.Source: §2 · pp. 5–6
- If the stacked Hessian has maximal rank, the nondefective Segre variety is generically r-identifiable.The criterion checks whether the tangential contact locus is zero-dimensional at a general point.Source: §2 · pp. 6, 8
- The criterion requires a nondefective secant variety; a nonmaximal Hessian rank leaves identifiability unresolved and may reflect an unfortunate point choice.Repeated failures may indicate tangential weak defectivity, which does not by itself settle identifiability.Source: §2 · p. 8
2.1. Unanticipated weakly defective varieties.
- The smallest reported instance of this new class is PC8×PC3×PC3×PC2, embedded in PC144.The examples satisfy Theorem 2.7’s stacked-Hessian condition.Source: §2.1 · p. 9
- Some tangentially weakly defective Segre varieties are nevertheless generically identifiable under the stated stacked-Hessian rank condition.The result shows that the proposed sufficient condition is not necessary.Source: §2.1 · pp. 9–10
3. An algorithm verifying generic identifiability
The paper gives an algorithm for testing a sufficient condition for generic identifiability, using finite-field computations to keep number representation bounded. Its experiments extend prior results and establish generic identifiability for tested spaces up to the largest possible subgeneric rank, except for perfect shapes.
3. An algorithm verifying generic identifiability
- The algorithm samples general points, constructs tangent-space and Hessian matrices, and uses their ranks to test the sufficient condition.If its checks do not establish identifiability, it reports that it cannot prove it for those points.Source: §3 · p. 10
- Finite-field computations keep the number of bits per represented value constant, while floating-point arithmetic introduces roundoff errors requiring propagation analysis.The implementation uses a prime field; the authors note that floating-point methods may be faster in practice.Source: §3 · p. 11, §3.1 · p. 11
3.1. Experimental results.
- The experiments tested spaces with Π ≤ 15,000 and up to 13 factors, extending prior experiments by two orders of magnitude.Results for varieties with at least seven factors were original, as were most results for fewer factors.Source: §3.1 · p. 11
- For all 75,993 tested spaces, the algorithm proved generic r-identifiability, including odd-dimensional PC^n × PC^n × PC^3 spaces that fail at rank r + 1.The latter varieties are defective at that next rank.Source: §3.1 · p. 11
- The sufficient condition considerably improves on the best results from Domanov–De Lathauwer [24] and is optimal except for perfect shapes.For perfect shapes, the algorithm is not designed to handle the relevant (r + 1)-secant.Source: §3.1 · p. 12, Table 1 · p. 12
4. A sufficient condition for specific identifiability
For a specific decomposition, the Hessian criterion gives a uniqueness test when the tensor is a nonsingular point of the secant variety. The section also shows why singular points can defeat the test and gives a subspace reduction for identifiability.
4. A sufficient condition for specific identifiability
- A tensor in a strict tensor subspace is r-identifiable exactly when its reduced tensor in the basis coordinates is r-identifiable.The reduction writes A as (Q1, . . . , Qd)·A′.Source: §4 · p. 13
- A general rank-6 tensor in C^n × C^n × C^n can inherit nonidentifiability from a rank-6 tensor in C^4 × C^4 × C^4, despite generic identifiability in the larger space.The smaller tensor has two decompositions, and the larger-space example lies in a measure-zero set where identifiability fails locally.Source: §4 · pp. 13–14
- The stacked Hessian detects local behavior on one fold, so it may miss a specific tensor lying on the singular locus of the secant variety.In the example, the secant variety is two-folded at a general point of the embedded smaller Segre variety.Source: §4 · p. 14
- A decomposition at a nonsingular point of σr(S) is unique if the stacked Hessian has maximal rank, equal to Σ, at every component.The criterion requires the nonsingularity premise; the authors show that a direct application can fail at singular points.Source: §4 · pp. 14–15
- The specific-identifiability test applies the Hessian criterion to the given decomposition’s components, provided the corresponding secant-variety point is nonsingular.The algorithm’s random-point step is removed, and the Hessian check is repeated for each component.Source: §4 · p. 15
- Local equations for low-order secant varieties are proposed as a way to test whether a given decomposition corresponds to a nonsingular point.The paper notes that little is known about singularities of these varieties.Source: §4 · p. 16
5. Identifiability of specific tensors beyond Kruskal’s bound
The section develops local secant-variety equations and smoothness tests for extending specific identifiability checks beyond Kruskal’s bound. It demonstrates the approach on a rank-7 tensor whose uniqueness the established criteria cannot verify.
5. Identifiability of specific tensors beyond Kruskal’s bound.
- For sufficiently small ranks, known local secant-variety equations can support specific-identifiability checks beyond Kruskal’s range, provided the tensor corresponds to a nonsingular point.The section notes that the relevant equations are known in a range that often exceeds Kruskal’s bound.Source: §5 · p. 16, §5.1 · p. 17
5.1. Some equations of secant varieties to Segre varieties.
- Minors of contraction maps provide equations for secant varieties, while ordinary flattenings yield nontrivial equations only when r<n1.The Strassen equations are a particular case of the contraction-map construction.Source: §5.1 · pp. 16–17
- For higher-rank equations, the section uses more general contraction maps, whose matrices are called Young flattenings.The construction defines the map on rank-1 tensors and extends it by linearity.Source: §5.1 · pp. 16–17
- For parameter cases listed in Table 2, the proposed minors’ zero locus contains the secant variety as an irreducible component, enabling a smoothness test outside a measure-zero subset.For P9 × P9 × P9, the joint minors have this property for r≤16.Source: §5.1 · pp. 18–19
5. Identifiability of specific tensors beyond Kruskal’s bound.
- The method’s broader reach is constrained because little is known about secant-variety singularities, and its current specific-identifiability gains are only slight over existing criteria.Applying the criterion requires showing that the specific decomposition corresponds to a nonsingular secant-variety point.Source: §5 · p. 16, §5.1 · p. 18
5.2. The algorithm at work for a specific tensor.
- Rank 7: a specific 5×5×5 tensor has a unique decomposition beyond Kruskal’s and Domanov–De Lathauwer’s criteria, after smoothness at its secant point was verified.The algorithm’s final stacked Hessian has rank 12 for each of the seven points.Source: §5.2 · p. 19
6. Conclusions
The paper presents a verifiable sufficient condition for generic and specific tensor identifiability. Its algorithm establishes generic identifiability for subgeneric ranks in spaces below dimension 15000, with known exceptions, while specific checks depend on verifying nonsingularity.
6. Conclusions
- In spaces of dimension below 15000, the algorithm establishes generic identifiability for subgeneric ranks, except for the paper’s listed cases.The paper describes this as a result for spaces of practical size.Source: §6 · p. 20
- The criterion also applies to specific decompositions when they can be shown to correspond to nonsingular points of the relevant secant variety.The paper presents this as a direction that could reach optimal rank values if suitable nonsingularity tests are designed.Source: §6 · p. 20
- Specific-identifiability results currently improve only slightly on existing conditions because singularities of secant varieties are poorly understood.Further characterization of secant-variety equations and singularities could extend the approach’s reach.Source: §6 · p. 20