Tata Institute of Fundamental Research
Approximating a polynomial as a sum of simple polynomials
STCS Colloquium
Speaker:
Neeraj Kayal (Microsoft Research)
Organiser:
Arkadev Chattopadhyay
Date:
Tuesday, 26 Jan 2021, 16:00 to 17:00
Venue:
(Scan to add to calendar)
Abstract:
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
| Speaker: | Neeraj Kayal (Microsoft Research) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Tuesday, 26 Jan 2021, 16:00 to 17:00 |
| Venue: |
(Scan to add to calendar)
Abstract:
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
YouTube Link - https://www.youtube.com/watch?v=ZCU74TXmG9o