Exact tensor completion via sum of squares

Computer Science/Discrete Mathematics Seminar II
Topic:Exact tensor completion via sum of squares
Speaker:Aaron Potechin
Affiliation:Member, School of Mathematics
Date:Tuesday, November 8
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2016/11/08-AaronPotechin

In the matrix completion problem, we have a matrix $M$ where we are only given a small number of its entries and our goal is to fill in the rest of the entries. While this problem is impossible to solve for general matrices, it can be solved if $M$ has additional structure, such as being low rank. In this talk, I will describe how the matrix completion problem can be solved by nuclear norm minimization and how this can be generalized to tensor completion via the sum of squares hierarchy.