Blue noise and optimal sampling on graphs
Date
2019
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
New data science tools are emerging to process signals on graph structures and concepts of algebraic and spectral graph theory are being merged with methods used in computational harmonic analysis to analyze these signals. A common problem in these networks is to determine which nodes play the most important role, assuming there is a quantity of interest defined on the network. Graph signal sampling thus becomes essential. In the first part of this dissertation, we explore a novel departure from prior work, inspired by sampling patterns in traditional dithering and halftoning. Specifically, we design graph signal sampling techniques that promote the maximization of the distance between sampling nodes on the vertex domain and that are characterized on some subclasses of graphs by a low frequency energy. Sampling patterns with these characteristics are referred to in the spatial dithering literature as blue-noise. The connection between existing theoretical results about sampling signals on graphs and blue noise sampling patterns on graphs is established, showing also how the spectral characteristics of these patterns are shaped by their vertex domain attributes. Additionally, for the generation of blue noise patterns a void and cluster algorithm on graphs is proposed exploiting the vertex-domain distribution of the sampling nodes. Numerical experiments show that the reconstruction error obtained with these patterns is similar to the one obtained by the state of the art approaches. Additionally, we explore the uniqueness sets for signals on cographs. Using the structure of the tree representation of a cograph, we proposed an algorithm that find its uniqueness sets from very simple small size graphs without any spectral decomposition or extensive searches on the vertex domain. The analysis performed on threshold graphs allowed us to calculate a closed form solution for the uniqueness sets. ☐ In the second part of this dissertation we consider the problem of sampling on regular grids for compressed sensing applications. We design optimal sampling patterns in coded apertures for CASSI systems and compressive X-ray tomosynthesis architectures, providing closed form solutions that outperform the results achieved using designs obtained with previous approaches, at a very low computational cost. Additionally, a rigorous estimate of the spectral resolution in general colored CASSI systems is provided exploiting the structure of the non-ideal sampling patterns obtained when wide spectral filters are considered.