Uncertainty Principles for Signal Concentrations

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 result...

In many applications, the observations can be represented as a signal defined over the vertices of a graph. The analysis of such signals requires the extension of standard signal processing tools. In this work, first, we provide a class of graph signals that are maximally concentrated on the graph domain and on its dual. Then, building on this framework, we derive an uncertainty principle for graph signals and illustrate the conditions for the recovery of band-limited signals...

Uncertainty principles present an important theoretical tool in signal processing, as they provide limits on the time-frequency concentration of a signal. In many real-world applications the signal domain has a complicated irregular structure that can be described by a graph. In this paper, we focus on the global uncertainty principle on graphs and propose new connections between the uncertainty bound for graph signals and graph eigenvectors delocalization. We also derive unc...

The aim of this paper is to establish a few uncertainty principles for the Fourier and the short-time Fourier transforms. Also, we discuss an analogue of Donoho--Stark uncertainty principle and provide some estimates for the size of the essential support of the short-time Fourier transform.

Uncertainty principles such as Heisenberg's provide limits on the time-frequency concentration of a signal, and constitute an important theoretical tool for designing and evaluating linear signal transforms. Generalizations of such principles to the graph setting can inform dictionary design for graph signals, lead to algorithms for reconstructing missing information from graph signals via sparse representations, and yield new graph analysis tools. While previous work has foc...

We develop new discrete uncertainty principles in terms of numerical sparsity, which is a continuous proxy for the 0-norm. Unlike traditional sparsity, the continuity of numerical sparsity naturally accommodates functions which are nearly sparse. After studying these principles and the functions that achieve exact or near equality in them, we identify certain consequences in a number of sparse signal processing applications.

In this paper, the uncertainty principle of discrete signals associated with Quaternion Fourier transform is investigated. It suggests how sparsity helps in the recovery of missing frequency.

Timelimited functions and bandlimited functions play a fundamental role in signal and image processing. But by the uncertainty principles, a signal cannot be simultaneously time and bandlimited. A natural assumption is thus that a signal is almost time and almost bandlimited. The aim of this paper is to prove that the set of almost time and almost bandlimited signals is not excluded from the uncertainty principles. The transforms under consideration are integral operators wit...

The paper obtains the optimal form of the uncertainty principle in the special case of convolution of sets.

In an incoherent dictionary, most signals that admit a sparse representation admit a unique sparse representation. In other words, there is no way to express the signal without using strictly more atoms. This work demonstrates that sparse signals typically enjoy a higher privilege: each nonoptimal representation of the signal requires far more atoms than the sparsest representation-unless it contains many of the same atoms as the sparsest representation. One impact of this fi...