Spring 2016

Sum of Squares SDP Relaxations on Random Tensors

Friday, May 6, 2016 11:45 am12:30 pm PDT

Add to Calendar


Calvin Lab

The injective norm of a k-tensor is a notoriously difficult quantity to approximate.  For example, given a random 4-tensors, spectral techniques yield the best known sqrt{n}-approximation to the injective norm.  In this talk, I will describe how n^{\epsilon}-degree SoS SDP hierarchy can be used to improve this approximation to a n^{1/2 -\delta} for some \delta.