Non-convex optimization for low-rank matrix reconstruction

A " low-rank matrix reconstruction problem " consists in identifying, from a small amount of information, a matrix (i.e. an array of numbers), knowing that it is " low-rank " (which, very informally, is equivalent to saying that its rows and columns have high similarities to each other). The best-known example is the " Netflix problem " : people who use Netflix assign ratings to the films they watch ; from this information, can we guess what rating each user would have given to each of the films available ? In this case, the matrix to be identified is the set of ratings that each person would have given to each film ; the information is the ratings actually given, i.e. a small portion of the numbers in the matrix.

Since low-rank matrices occur naturally in most scientific fields, these problems have many applications. Among the algorithms designed to solve them, those known as " non-convex " generally consist in choosing an arbitrary low-rank matrix and then gradually modifying it to make it more and more consistent with the accessible information, while ensuring that it remains low-rank. At first glance, these algorithms seem naïve : why should these successive modifications correctly identify the unknown matrix ? Is there not a risk of getting lost in an infinite series of small, contradictory modifications, without ever arriving at a matrix that simultaneously conforms to all the information given ? And yet, in practice, non-convex algorithms often work well, successfully solving a priori difficult reconstruction problems.

This empirical finding is difficult to explain rigorously. For a given problem and non-convex algorithm, we are generally unable to determine in advance whether the algorithm will succeed in solving the problem ; when it does, we don't know why. Significant progress has nevertheless been made over the last ten years, with the development of general methods that allow us to analyze certain classes of problems and algorithms, albeit under restrictive assumptions. The aim of this lecture is to present these methods.