Workshop on Phaseless Reconstruction

The low-rank matrix completion problem asks under which conditions an (n x n)-matrix of rank r can be recovered from only rn expansion coefficients with respect to a given matrix basis. This seemingly abstract problem underpins manifold applications, as diverse as the prediction of user preferences in online shops (an early motivation for the field, also known as the "Netflix problem") over quantum state estimation (my personal original motivation), to recent new algorithms in phaseless estimation. I will give a short introduction to these questions and explain how methods originally developed in quantum physics lead to a simple and general technique for proving reconstruction theorems. These methods include in particular a certain set of large deviation bounds for matrix-valued random variables which I will emphasize. Time permitting, I will talk about matrix bases with certain advantageous, "universal" incoherence properties and connections to Gabor analysis.