Linear and nonlinear matrix recovery

The Netflix problem is the problem that asks one to predict the ratings a user would give a movie or TV show given previous ratings the user has given, without any other information about the user. This problem is an example of matrix completion. Matrix completion is the problem of filling in missing entries to a data matrix under the assumption that the data lies on a low dimensional subspace. The first part of this talk will highlight some results and solution methods for this problem. In the second part of this talk I will turn to the problem of nonlinear matrix completion and highlight recent results in a paper of Florentin Doyens, Coralia Cartis and Armin Eftekhari. For this part, instead of assuming linear relations among the columns of our data matrix, we assume they obey nonlinear relations (i.e. they lie on the union of subspaces or some other algebraic variety). This part will give an overview on how one can formulate this problem as well as algorithms to solve them.

This is a preparatory lecture for the ICM talk of Coralia Cartis.