Open Lecture — Finding Low-Rank Matrices: From Matrix Completion to Recent Trends

The problem of finding low-rank matrices that are consistent with some observations and constraints arises in many application fields, including recommendation systems in machine learning, phase retrieval in optical signal processing, identification of dynamical systems, and community detection in networks.

We first examine the problem from the viewpoint of reconstruction from compressed measurements. Historically, the theory of compressed sensing (for sparse signals) inspired the first theoretical guarantees on low-rank matrix recovery and completion (reconstruction from a small number of entries) by minimizing the matrix nuclear norm. This led to a rich framework that extends to more general structures than low-rank. Next, we discuss an open challenge arising from simultaneous structures: while we know how to optimally reconstruct a matrix that is either sparse or low-rank, for a simultaneously sparse and low-rank matrix, we show a fundamental gap that cannot be overcome by combining existing best approaches for each structure. We then briefly survey the algorithm side: in addition to convex optimization algorithms for nuclear norm minimization, recent approaches consider more memory-efficient but nonconvex formulations, as well as a sketched convex formulation.

Light refreshments will be served before the lecture at 3:30 p.m.