Fitting a low-rank matrix to data is an inherently non-convex problem; correspondingly, an increasingly common instinct has been to relax the rank constraint to a convex one, with the resulting estimator shown to be consistent under further statistical/structural assumptions. However, this approach is rarely taken in practice, because it wastefully increases both the computational complexity and the search space of solutions. In this talk, we describe the basic geometric intuition behind some of our recent work, which shows that simple “heuristics” (gradient descent and alternating minimization on the compact non-convex bi-linear representation of the low-rank matrix) can be provably consistent under the *same* statistical settings where convex methods are known to work. We will see its applications to matrix completion, robust PCA, etc.