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

该项目提出了一个合作的研究和教育工作的图形信号处理，有趣的现象在自然界中往往可以捕捉到的图形，因为对象和数据总是在某种意义上相互关联。 社交网络、生态网络和人脑是这种网络的几个例子。这些感兴趣的网络的一个共同特征是它们定义了非常大的图。用于计算完全图的性质的算法，当所研究的图变得非常大时，迅速变得不切实际。因此，图形采样变得至关重要。这项研究探讨了一个有点激进的偏离以前的工作图采样，是基于不规则的采样网格中的随机采样的概念。为了推进该项目的科学目标，研究人员还将共同开发一个关于图形信号处理及其应用的短期课程，以便向广大学生介绍这一新兴领域。虽然固定时间采样是众所周知的，但该项目侧重于随机采样理论，以图形信号处理，特别是图形子采样，无论是否知道信号。在没有信号知识的采样的情况下，研究人员打算设计最佳的子采样网格，使二进制信号中的低频能量最小化，其中研究人员打算开发低计算复杂度的抖动算法，紧密模仿理想模式。在利用信号知识进行子采样的情况下，所开发的自适应子采样算法将基于信号的局部频率内容来调整采样率，从而，该奖项反映了NSF的法定使命，并被认为是值得通过使用基金会的智力价值和更广泛的影响审查评估的支持的搜索.

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.