Mini-Workshop: Mathematical Physics meets Sparse Recovery

Abstract

In recent years, there have been several fruitful interchanges of methods between the fields of sparse and low-rank recovery on the one hand and quantum information theory on the other hand. One way to understand this seemingly surprising coincidence is that the analysis of vector- and matrix-valued randomized constructions plays an important role in both fields. An example is the realization that certain matrix-valued large deviation bounds can be employed to substantially simplify and generalize the analysis of low-rank matrix recovery schemes.

In this workshop, the participants worked to identify and collaborate on further mathematical problems that are being researched in parallel by the two communities. Topics that have been discussed include

• Tools for the analysis of vector- and matrix-valued randomized constructions and their application to phase retrieval problems

• Conversely, tools for de-randomizing such protocols, based, e.g., on spherical designs.

• Uncertainty relations, e.g., for the task of lower-bounding the number of measurements required for signal identification.

• Time-frequency methods (known as phase-space methods in physics).

• Matrix- and tensor norms: computational tools, complexity, relaxations and their application to tensor recovery.