BIRS Workshop Lecture Videos
Polynomial-time tensor decomposition with sum-of-squares Steurer, David
Tensor decomposition is at the heart of many computational problems that arise in machine learning and other kinds of data analyses. However, unlike for matrices, it is NP-hard to compute good decompositions for higher-order tensors. Nevertheless, a sequence of results shows that under simple mild assumptions on the instances good tensor decompositions can be found in polynomial time. I will present a recent framework for tensor decompositon based on the sum-of-squares method that unifies and extends these results. As a consequence, we obtain the first polynomial-time algorithm to decompose overcomplete 4-tensors in the smoothed analysis settings even in the presence of a polynomial amount of noise. Based on a joint work with Tengyu Ma and Jonathan Shi (to appear at FOCS 2016).
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International