The "lowrank matrix completion" problem is: reconstruct a rankr (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 semidefinite program (the
invoked techniques are noncommutative 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 lowrank 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.
