Abstract of David Gross

Recovering low-rank matrices from few coefficients in any basis
The "low-rank matrix completion" problem is: reconstruct a rank-r (n x n)-matrix given information about only (r n polylog(n)) randomly selected matrix elements. Quite recently, it has been shown that the problem can be solved computationally efficiently by a suitable semi-definite program (the invoked techniques are non-commutative analogues of "compressed sensing"). However, the fact remained that the original proof was extremely complicated, covering dozens of pages of intricate math. I present new results which achieve several objectives. Most importantly, the proof complexity is greatly reduced - the argument is now a series of relatively elementary steps. The methods are also more general, in that they extend to the situation where a low-rank matrix is to be reconstructed from few expansion coefficients with respect to an arbitrary matrix basis. Lastly, the bounds thus obtained are slightly tighter than previously known ones (in some cases tight up to constants). In the talk, I will concentrate on the basic intuition and geometry underlying the problem. Technical details can be supplied depending on the interests of the audience.


Lars Grasedyck (MPI Leipzig, Germany)
Wolfgang Hackbusch (MPI Leipzig, Germany)
Boris Khoromskij (MPI Leipzig, Germany)