A generalization of Kruskal’s theorem on tensor decomposition

DOI10.1017/FMS.2023.20zbMATH Open1518.14077arXiv2103.15633OpenAlexW3145796852WikidataQ122599563 ScholiaQ122599563MaRDI QIDQ6043382FDOQ6043382

Authors: Benjamin Lovitz, F. V. Petrov 

Publication date: 5 May 2023

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2103.15633

Recommendations

• A concise proof of Kruskal's theorem on tensor decomposition
• On Uniqueness of the Canonical Tensor Decomposition with Some Form of Symmetry
• Kruskal's uniqueness inequality is sharp
• On the uniqueness of the canonical polyadic decomposition of third-order tensors. I: Basic results and uniqueness of one factor matrix
• On Generic Identifiability of 3-Tensors of Small Rank

zbMATH Keywords

splitting theoremtensor decompositionKruskal's theorem

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Algebraic statistics (62R01) Combinatorial aspects of matroids and geometric lattices (05B35) Secant varieties, tensor rank, varieties of sums of powers (14N07)

Cites Work

• Title not available (Why is that?)
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Power sums, Gorenstein algebras, and determinantal loci. With an appendix `The Gotzmann theorems and the Hilbert scheme' by Anthony Iarrobino and Steven L. Kleiman
• Title not available (Why is that?)
• 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
• On generic identifiability of symmetric tensors of subgeneric rank
• Transformations on tensor spaces
• Characterizing operations preserving separability measures via linear preserver problems
• Rank and optimal computation of generic tensors
• A concise proof of Kruskal's theorem on tensor decomposition
• Title not available (Why is that?)
• Hilbert functions and tensor analysis
• Tensor Decomposition for Signal Processing and Machine Learning
• Multi-partite separable states with unique decompositions and construction of three qubit entanglement with positive partial transpose
• Effective criteria for specific identifiability of tensors and forms
• Bounds on the tensor rank
• Coupled canonical polyadic decompositions and (coupled) decompositions in multilinear rank-\((L_r,n,L_r,n,1)\) terms. I: Uniqueness
• Kruskal's uniqueness inequality is sharp
• Independence and port oracles for matroids, with an application to computational learning theory
• New Uniqueness Conditions for the Canonical Polyadic Decomposition of Third-Order Tensors
• On decomposable correlation matrices

Cited In (7)

• On unique tensor rank decomposition of 3-tensors
• Kruskal's uniqueness inequality is sharp
• An algorithm for the non-identifiability of rank-3 tensors
• Decompositions and Terracini loci of cubic forms of low rank
• A concise proof of Kruskal's theorem on tensor decomposition
• Decompositions of a Higher-Order Tensor in Block Terms—Part I: Lemmas for Partitioned Matrices
• A constructive arbitrary-degree Kronecker product decomposition of tensors.

This page was built for publication: A generalization of Kruskal’s theorem on tensor decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6043382)