Almost lossless analog signal separation and probabilistic uncertainty relations

Authors

David Stotz, Erwin Riegler, Eirikur Agustsson, and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, Vol. 63, No. 9, pp. 5445-5460, Sept. 2017.

Abstract

We propose an information-theoretic framework for analog signal separation. Specifically, we consider the problem of recovering two analog signals, modeled as general random vectors, from the noiseless sum of linear measurements of the signals. Our framework is inspired by the groundbreaking work of Wu and Verdú (2010) on analog compression and encompasses, inter alia, inpainting, declipping, super-resolution, the recovery of signals corrupted by impulse noise, and the separation of (e.g., audio or video) signals into two distinct components. The main results we report are general achievability bounds for the compression rate, i.e., the number of measurements relative to the dimension of the ambient space the signals live in, under either measurability or Hölder continuity imposed on the separator. Furthermore, we find a matching converse for sources of mixed discrete-continuous distribution. For measurable separators our proofs are based on a new probabilistic uncertainty relation which shows that the intersection of generic subspaces with general sets of sufficiently small Minkowski dimension is empty. Hölder continuous separators are dealt with by introducing the concept of regularized probabilistic uncertainty relations. The probabilistic uncertainty relations we develop are inspired by embedding results in dynamical systems theory due to Sauer et al. (1991) and—conceptually—parallel classical Donoho-Stark and Elad-Bruckstein uncertainty principles at the heart of compressed sensing theory. Operationally, the new uncertainty relations take the theory of sparse signal separation beyond traditional sparsity—as measured in terms of the number of non-zero entries—to the more general notion of low description complexity as quantified by Minkowski dimension. Finally, our approach also allows to significantly strengthen key results in Wu and Verdú (2010).

Keywords

Signal separation, compressed sensing, uncertainty relations, Minkowski dimension, Shannon theory

Comments

An online addendum to the paper is available here.

Download this document:

Copyright Notice: © 2017 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.