Toward a generalization of Kruskal's theorem on tensor decomposition

Abstract

Kruskal's theorem states that a sum of product tensors constitutes a unique tensor rank decomposition if the so-called k-ranks of the product tensors are large. In this work, we propose a conjecture in which the k-rank condition of Kruskal's theorem is weakened to the standard notion of rank, and the conclusion is relaxed to a statement on the linear dependence of the product tensors. Our conjecture would imply a generalization of Kruskal's theorem. Several adaptations and generalizations of Kruskal's theorem have already been obtained, but these results still cannot certify uniqueness when the k-ranks are below a certain threshold. Our generalization would contain several of these results, and could certify uniqueness below this threshold. We prove our conjecture over an arbitrary field $\mathbb{F}$ when the underlying multipartite vector space takes any one of three forms: ${\mathbb{F}}^{d_1}\otimes {\mathbb{F}}^{d_2},{\mathbb{F}}^{d_1}\otimes {\mathbb{F}}^{d_2}\otimes {\mathbb{F}}^2,$ or ${\mathbb{F}}^{d_1}\otimes {\mathbb{F}}^2\otimes \cdots \otimes {\mathbb{F}}^2$. As a corollary to the third case, we prove that if $n$ product tensors form a circuit, then they have rank greater than one in at most $n-2$ subsystems. This is a quadratic improvement over a recent bound obtained by Ballico, and is sharp.

arXiv comment31 pages. Significant changes from v1, including: The splitting version of the main conjecture, proofs of several more special cases of the main conjecture, the observation that the main conjecture implies a generalization of Kruskal's theorem, and a proof that the inequality appearing in the main conjecture is sharp

References in corpus (10)

• Tensor Decomposition for Signal Processing and Machine Learning
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• On the Uniqueness of the Canonical Polyadic Decomposition of third-order tensors --- Part 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
• Effective criteria for specific identifiability of tensors and forms
• Geometry of entanglement in the Bloch sphere
• Identifiability beyond Kruskal's bound for symmetric tensors of degree 4
• On the identifiability of ternary forms
• On decomposable correlation matrices

Cited by in corpus (1)

• A generalization of Kruskal's theorem on tensor decomposition