# Polynomial Methods in Learning and Statistics

## Polynomial Methods in Learning and Statistics - Ankur Moitra

Ankur Moitra
I will also present work on the problem of computing the nonnegative rank of a matrix, which is a parameter that is of fundamental importance in machine learning, combinatorics and communication complexity. Here the message will be that systems of polynomial equations are unreasonably expressive, and the nonnegative rank of a matrix can be equivalently encoded as a non-emptiness question for a semi-algebraic set with only a small number of variables. From this, we obtain the first algorithm for computing a nonnegative matrix factorization with inner-dimension $r$ (if one exists) that runs in polynomial time for any fixed $r$.