Tackling problems in physics and AI with convex programming, and solving certain SDPs quickly
We will discuss three stories revolving around convex programming. The first is of a new algorithmic framework for a century old problem in physics called phase retrieval, which involves recovering vectors from quadratic measurements and naturally connects to questions in quantum mechanics and theoretical CS. The second is on recovering the 3D structure of a scene from a collection of images, a fundamental task in computer vision which requires algorithms that are robust to a large fraction of arbitrary corruptions in the input data. Lastly, we will present new non-convex guarantees for solving certain semidefinite programs quickly by exploiting parsimony in their solutions.