In several applications, one is interested in the recovery/estimation of
low-rank matrices of very large size. A popular approach in practice has been to
parameterize such a matrix as the product of two much smaller matrices - one
"tall" and one "fat" - and then to estimate these matrices instead. This is seen
to allow gains in storage, computation, and oftentimes, statistical performance
as well. However there has been a lack of corresponding analytical guarantees
for such procedures; one reason is that the bi-linear parameterization makes for
non-convex problems.

In this talk we present provable guarantees for three low-rank recovery
problems using alternating minimization - matrix completion, matrix sensing, and
phase recovery.