Uncertainty relations and sparse signal recovery

Authors

Erwin Riegler and Helmut Bölcskei

Reference

Chapter in Information-theoretic Methods in Data Science, M. Rodrigues and Y. Eldar, Eds., Cambridge University Press, 2021.

[BibTeX, LaTeX, and HTML Reference]

Abstract

This chapter provides a principled introduction to uncertainty relations underlying sparse signal recovery. We start with the seminal work by Donoho and Stark, 1989, which defines uncertainty relations as upper bounds on the operator norm of the band-limitation operator followed by the time-limitation operator, generalize this theory to arbitrary pairs of operators, and then develop—out of this generalization—the coherence-based uncertainty relations due to Elad and Bruckstein, 2002, as well as uncertainty relations in terms of concentration of 1-norm or 2-norm. The theory is completed with the recently discovered set-theoretic uncertainty relations which lead to best possible recovery thresholds in terms of a general measure of parsimony, namely Minkowski dimension. We also elaborate on the remarkable connection between uncertainty relations and the “large sieve”, a family of inequalities developed in analytic number theory. It is finally shown how uncertainty relations allow to establish fundamental limits of practical signal recovery problems such as inpainting, declipping, super-resolution, and denoising of signals corrupted by impulse noise or narrowband interference. Detailed proofs are provided throughout the chapter.

Keywords

Donoho-Stark uncertainty relations, signal recovery, sparsity, redundant dictionaries

Download this document:

 

Copyright Notice: © 2021 E. Riegler and H. Bölcskei.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.