Abstract: In this talk, we will discuss various examples how randomized measurement designs for signal processing applications yield improved performance with provable recovery guarantees. We will show how these scenarios give rise to problems of independent interest at the interface of high-dimensional probability and statistical learning theory, whose solutions then help to advance the understanding of the measurement systems.
Firstly, motivated by imaging applications, we discuss the problem of sparse recovery from subsampled random convolutions. We advance techniques related to the theory of empirical processes to establish near-optimal recovery guarantees.
Secondly, we present recent results about the geometry of random polytopes generated by heavy-tailed random vectors and discuss their implications for noise-blind compressed sensing.
Lastly, motivated by applications in wireless communication, we establish local instabilities arising for convex regularizations of the randomized blind deconvolution problem.

These are joint works with the speaker’s PhD students Christian Kümmerle and Dominik Stöger, well as with Olivier Guédon (Université de Paris Est), Shahar Mendelson (Australian National University) and Holger Rauhut (RWTH Aachen University).