Max Planck Institute for Dynamics and Self-Organization -- Department for Nonlinear Dynamics and Network Dynamics Group
Personal tools
Log in


Monday, 15.11.2010 11 c.t.

A tour of compressed sensing: from single pixel cameras to quantum state tomography

by Dr. David Gross
from ETH Zürich

Contact person: Dirk Witthaut


Seminarraum Haus 2, 4. Stock (Bunsenstr.)


The talk has two parts: the first part is phenomenological (and "commutative"); the second part more technical (and "non-commutative"). I can shift emphasis according to the wishes of the audience. 1. Every 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 - and back up the claims with some pictures taken by "single pixel cameras". 2. A basis-independent notion of the sparsity of a matrix is its rank. One is thus naturally led to the "low-rank matrix recovery" problem: reconstruct an unknown rank-r (n x n)-matrix from only O(r n) linear measurements. Recently, a rigorous understanding of when and how this is possible has been obtained. I will explain the theory and may touch on applications to quantum state estimation. References (for the second part): D. Gross et al, Phys. Rev. Lett. 105, 150401 (2010). D. Gross, arxiv:0910.1879, IEEE Trans. Inf. Theo. (in press).

back to overview