In this talk, we will consider algorithmic problems which follow the following template: given a real-valued multivariate polynomial f(x) of degree d, is it approximately equal to a sum of a few "simple" polynomials, i.e Is f ~= g_1(x) + g_2(x) + ... + g_r(x)? Examples/special cases of this problem template are low-rank approximation of a matrix and tensor decomposition. We will see many applications including independent component analysis, subspace clustering, Learning Gaussian mixture models and (language) topic modelling. In the next part, we will see how techniques from algebraic complexity can potentially be used to algorithmically solve such problems efficiently. We will formulate some conjectures in this regard. We resolve one such conjecture which leads to a more noise-resilient algorithm for the relatively well-studied problem of tensor decomposition.
YouTube Link - https://www.youtube.com/watch?v=ZCU74TXmG9o
