
Algorithms for Overcomplete Tensor Decomposition
Pravesh Kothari, of Princeton University, presents a seminar talk at the Institute for Advanced Study on decomposing an n by n by n tensor into the smallest possible sum of rank-one terms. He explains why the problem is NP-hard in general, how Jennrich's algorithm handles the case where the number of components r is at most n, and why the overcomplete regime, where r exceeds n, has resisted efficient algorithms despite its relevance to statistical estimation. Kothari describes joint work with Ankur Moitra and Alexander Wein that gives an efficient algorithm whenever r is at most (2 minus epsilon) times n for any constant epsilon greater than zero. The key technical tool is a new rank-detection gadget built on Koszul Young flattenings, which reduces the hard problem of certifying tensor rank to the more tractable problem of certifying matrix rank.