Overcomplete Tensor Decomposition via Koszul-Young Flattenings

Certain non-trivial flattenings of tensors to matrices have been useful for proving lower bounds on the rank of explicit tensors such as the matrix multiplication tensor. I will show how this tool can also be used to obtain algorithmic results for the tensor decomposition problem. This is the task of finding the minimum-rank decomposition of a given tensor as the sum of rank-1 tensors, somewhat analogous to the SVD for matrices. Specifically, we give a polynomial-time algorithm for decomposing generic n-by-n-by-n tensors of rank r < (2-epsilon)n, whereas the classical result needs r <=n. Based on joint work with Pravesh Kothari and Ankur Moitra, available at: https://arxiv.org/abs/2411.14344

This seminar is part of the Problems in Algebraic Geometry Coming from Complexity Theory series.