CIF: Small: Collaborative Research: Blue-Noise Graph Sampling

University Of Kentucky Research Foundation, Lexington KY

Investigators

Abstract

This project presents a collaborative research and education effort in graph signal processing where interesting phenomena in nature can often be captured by graphs since objects and data are invariably interrelated in some sense. Social networks, ecological networks, and the human brain are a few examples of such networks. A feature that these networks of interest have in common, is that they define very large graphs. Algorithms used to compute properties of complete graphs, rapidly become impractical when the graphs under study become very large. Graph sampling thus becomes essential. The research explores a somewhat radical departure from the prior work on graph sampling and is based on the notion of stochastic sampling in irregular sampling grids. In concert with the advancing the scientific goals of the project, the investigators will also jointly develop a short course on graph signal processing and its applications so as to introduce this emerging field to a broad set of students. While fixed-time sampling is well known, this project focuses on stochastic sampling theory to graph signal processing and, in particular, graph sub-sampling with and without knowledge of the signal. In the case of sampling without signal knowledge, investigators intend to design optimal sub-sampling grids that minimize low frequency energy in a binary signal where investigators intend to develop low computational complexity dither algorithms that closely mimic the ideal patterns. In the case of sub-sampling with signal knowledge, the developed adaptive sub-sampling algorithms will adjust the sampling rate based on the local frequency content of the signal to, thereby, sample at just above the Nyquist rate of the sample within a small region of interest. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.