Talk on
Compressed Sensing and Matrix Completion: From Single Pixel Cameras to Quantum State Tomography

Prof. David Gross (Uni Freiburg)

very time the release button of a digital camera is pressed, several megabytes
of raw data are recorded. But the size of a typical jpeg output file is only 10%
of that. What a waste! Can't we design a process which records only the relevant
10% of the data to begin with? The recently developed theory of compressed sensing
achieves this trick for sparse signals. I will give a short introduction to the
ideas and the math behind compressed sensing.

A basis-independent notion of "sparsity" for a matrix is its rank. One is thus
naturally led to the "low-rank matrix recovery" problem: can one reconstruct and
unknown low-rank matrix from few linear measurements? The answer is affirmative.
The arguably simplest proof to date is based on ideas from quantum information
theory. In the second half of the presentation, I will talk about applications
and proof techniques for the matrix theory, including the links to quantum.