LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Algorithms for Overcomplete Tensor Decomposition
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Algorithms for Overcomplete Tensor Decomposition

130 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 148 Computer Science lectures
Runtime2 h 10 m
Compared with Computer ScienceLonger than 98%
Source channelInstitute for Advanced Study (YouTube)