Martin Genzel – “A Non-Uniform Perspective on Analysis Sparsity in Compressed Sensing”
“A Non-Uniform Perspective on Analysis Sparsity in Compressed Sensing”
Abstract: Within the last decade, compressed sensing has emerged as a novel acquisition technique that allows for the efficient reconstruction of signals from highly undersampled measurements, assuming sparsity with respect to a certain transform domain. Of particular importance in this field is the analysis formulation, according to which the signal-of-interest can be effectively sparsified by a (possibly redundant) analysis operator. However, despite many successful applications in practice, a rigorous theoretical understanding of the analysis formulation is still missing.
In this talk, we establish a non-uniform guarantee for robust and stable recovery via the standard analysis basis pursuit, enabling for accurate predictions of its sample complexity. The corresponding bounds on the number of required samples do explicitly depend on the Gram matrix of the analysis operator and therefore take account of its mutual coherence structure. These findings defy conventional wisdom in previous compressed sensing research which suggests that the sparsity of the analysis coefficients is the crucial performance indicator to be studied. In fact, this “uniform” perspective becomes useless in many situations of practical interest, for instance, when using a redundant (multilevel) frame as sparsifying transform. By contrast, it is demonstrated that the proposed theoretical sampling-rate bounds can reliably predict the reconstruction capability of various types of analysis operators, such as redundant Haar wavelets systems, total variation, or random frames. In this context, we will also discuss some recent advances in 1D total variation, where the gap between uniform and non-uniform recovery becomes unexpectedly striking.
This is joint work with Gitta Kutyniok (TU Berlin), Maximilian März (TU Berlin), and Robert Seidel (TU Berlin).
Bio: Martin Genzel is a postdoc at the Technical University of Berlin, Germany, where he is part of the Applied Functional Analysis Group. There, he also completed his B.Sc. and M.Sc. in Mathematics in 2013 and 2015, respectively, as well as his Ph.D. in 2019 under the supervision of Gitta Kutyniok. His research is focusing on topics at the interface of applied mathematics, signal processing, and machine learning, in particular, inverse problems, compressed sensing, high-dimensional statistics, and deep learning.