Low rank matrices lie at the heart of many techniques in scientific computing and machine learning such as dimensionality reduction, clustering, recommendation systems and many more. In this talk, we will examine two scenarios in which the goal is to recover an underlying low rank matrix from compressed or incomplete measurements; in both of these instances, we seek to solve an appropriate optimization problem with a rank constraint. We will enforce the rank constraint explicitly via the quadratic representation , , leading to a non-convex problem in . Instead of analyzing convex relaxations, which tend to be complicated and computationally expensive, we will operate directly on the natural non-convex problems and prove both local and global optimality guarantees for a family of algorithms. This is a thesis defense.