A Generalization of Kruskal's Theorem on Tensor Decomposition
Date and Time
Location
This talk will take place virtually via Teams.
Details
Speaker: Benjamin Lovitz. (Fourth-year PhD candidate in the Department of Applied Math and the Institute for Quantum Computing at the University of Waterloo. He studies tensors, with applications in algebraic statistics and quantum information theory. He is supported by the government of Ontario and the University of Waterloo through an Ontario Graduate Scholarship.)
Abstract:
Tensors are natural generalizations of matrices to higher-way arrays. Decompositions of tensors into sums of product (rank-one) tensors are useful in many areas for compressing and interpreting the information stored in a tensor. The tensor rank, which naturally generalizes matrix rank, is the smallest number of product tensors that can decompose a given tensor. In contrast to matrices, tensor rank decompositions are often unique (up to trivialities). Uniqueness is useful in applications, as it corresponds to a unique interpretation of the information stored in a tensor. I will review a concrete application of uniqueness in unsupervised learning.
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 (matroidal) proof technique, contains many of these extensions, and can certify uniqueness below this threshold.
This talk is based on joint work with Pavel Gubkin and Fedor Petrov.