Uncertainty relations and sparse signal recovery for pairs of general signal sets

Authors

Patrick Kuppinger, Giuseppe Durisi, and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, Vol. 58, No. 1, pp. 263-277, Jan. 2012.

DOI: 10.1109/TIT.2011.2167215

Abstract

We present an uncertainty relation for the representation of signals in two different general (possibly redundant or incomplete) signal sets. This uncertainty relation is relevant for the analysis of signals containing two distinct features each of which can be described sparsely in a suitable general signal set. Furthermore, the new uncertainty relation is shown to lead to improved sparsity thresholds for recovery of signals that are sparse in general dictionaries. Specifically, our results improve on the well-known (1+1/d)/2-threshold for dictionaries with coherence d by up to a factor of two. Furthermore, we provide probabilistic recovery guarantees for pairs of general dictionaries that also allow us to understand which parts of a general dictionary one needs to randomize over to “weed out” the sparsity patterns that prohibit breaking the square-root bottleneck.

Keywords

Basis pursuit, frame theory, orthogonal matching pursuit, signal recovery, sparsity, uncertainty relations

Download this document:

Copyright Notice: © 2012 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

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.