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. We prove a "splitting theorem" for sets of product tensors, in which the k-rank condition of Kruskal's theorem is weakened to the standard notion of rank, and the conclusion of uniqueness is relaxed to the statement that the set of product tensors splits (i.e. is disconnected as a matroid). Our splitting theorem implies a generalization of Kruskal's theorem. While several extensions of Kruskal's theorem are already present in the literature, all of these use Kruskal's original permutation lemma, and hence still cannot certify uniqueness when the k-ranks are below a certain threshold. Our generalization uses a completely new proof technique, contains many of these extensions, and can certify uniqueness below this threshold. We obtain several other useful results on tensor decompositions as consequences of our splitting theorem. We prove sharp lower bounds on tensor rank and Waring rank, which extend Sylvester's matrix rank inequality to tensors. We also prove novel uniqueness results for non-rank tensor decompositions.

arXiv comment48 pages. Feedback welcome!

References in corpus (14)

• 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
• On the Uniqueness of the Canonical Polyadic Decomposition of third-order tensors --- Part I: Basic Results and Uniqueness of One Factor Matrix
• On generic identifiability of symmetric tensors of subgeneric rank
• Effective criteria for specific identifiability of tensors and forms
• Characterizing Operations Preserving Separability Measures via Linear Preserver Problems
• Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability
• Geometry of entanglement in the Bloch sphere
• Multi-partite separable states with unique decompositions and construction of three qubit entanglement with positive partial transpose
• Linearly dependent and concise subsets of a Segre variety depending on k factors
• On decomposable correlation matrices
• Toward a generalization of Kruskal's theorem on tensor decomposition

Cited by in corpus (4)

• New techniques for bounding stabilizer rank
• Decompositions and Terracini loci of cubic forms of low rank
• Learning latent causal graphs via mixture oracles
• Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS