Uncertainty Relations for Shift-Invariant Analog Signals

Abstract

The past several years have witnessed a surge of research investigating various aspects of sparse representations and compressed sensing. Most of this work has focused on the finite-dimensional setting in which the goal is to decompose a finite-length vector into a given finite dictionary. Underlying many of these results is the conceptual notion of an uncertainty principle: a signal cannot be sparsely represented in two different bases. Here, we extend these ideas and results to the analog, infinite-dimensional setting by considering signals that lie in a finitely-generated shift-invariant (SI) space. This class of signals is rich enough to include many interesting special cases such as multiband signals and splines. By adapting the notion of coherence defined for finite dictionaries to infinite SI representations, we develop an uncertainty principle similar in spirit to its finite counterpart. We demonstrate tightness of our bound by considering a bandlimited lowpass train that achieves the uncertainty principle. Building upon these results and similar work in the finite setting, we show how to find a sparse decomposition in an overcomplete dictionary by solving a convex optimization problem. The distinguishing feature of our approach is the fact that even though the problem is defined over an infinite domain with infinitely many variables and constraints, under certain conditions on the dictionary spectrum our algorithm can find the sparsest representation by solving a finite-dimensional problem.

Accepted to IEEE Trans. on Inform. Theory

References in corpus (5)

• From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals
• Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors
• Time Delay Estimation from Low Rate Samples: A Union of Subspaces Approach
• Compressed Sensing of Analog Signals in Shift-Invariant Spaces
• Beyond Bandlimited Sampling: Nonlinearities, Smoothness and Sparsity

Cited by in corpus (14)

• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals
• Structured Compressed Sensing: From Theory to Applications
• Xampling: Signal Acquisition and Processing in Union of Subspaces
• Coherence-Based Performance Guarantees for Estimating a Sparse Vector Under Random Noise
• Time Delay Estimation from Low Rate Samples: A Union of Subspaces Approach
• Multichannel Sampling of Pulse Streams at the Rate of Innovation
• Theoretical Analysis for Extended Target Recovery in Randomized Stepped Frequency Radars
• Recovery Conditions of Sparse Signals Using Orthogonal Least Squares-Type Algorithms
• Signal Recovery in Unions of Subspaces with Applications to Compressive Imaging
• Recovering Signals from Lowpass Data
• Theoretical Analysis of Compressive Sensing via Random Filter
• Sparse Signal Recovery in Hilbert Spaces
• Limits of Deterministic Compressed Sensing Considering Arbitrary Orthonormal Basis for Sparsity