This talks considers a fundamental class of matrix optimization problems with low-rank solutions. We show it possible to solve these problems using far less memory than the natural size of the decision variable when both the problem data and solution have a concise representation. We present an algorithmic framework, which provably solves these optimization problems using optimal storage. Our convex optimization framework operates with a sketched version of the decision variable, and can recover the solution from this sketch. Importantly, and in contrast to recent work on non-convex methods for this problem class, our framework is fully convex, and inherits all the benefits of convex optimization, including robustness, flexibility, and a well understood convergence theory. In particular, our convergence guarantees do not rely on statistical assumptions on the problem data. Computational evidence establishes that the algorithm solves ill-conditioned problems beyond the reach of standard non-convex methods, and scales to huge instances while retaining the advantages of convex optimization.