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

该项目展示了在图形信号处理方面的合作研究和教育努力，其中自然中的有趣现象通常可以通过图形捕获，因为对象和数据在某种意义上总是相互关联的。社会网络、生态网络和人类大脑就是这些网络的几个例子。这些感兴趣的网络有一个共同的特点，那就是它们定义了非常大的图。当研究的图变得非常大时，用于计算完全图性质的算法很快变得不切实际。因此，图采样变得至关重要。该研究在一定程度上与先前的图采样工作有所不同，并基于不规则采样网格中的随机采样概念。为配合该项目的科学目标，研究人员还将共同开发一门关于图形信号处理及其应用的短期课程，以便向广大学生介绍这一新兴领域。虽然固定时间采样是众所周知的，但本项目侧重于随机采样理论，以图信号处理，特别是在有和没有信号知识的情况下的图子采样。在没有信号知识的采样情况下，研究人员打算设计最优的子采样网格，以最大限度地减少二进制信号中的低频能量，研究人员打算开发低计算复杂度的抖动算法，以接近模拟理想模式。在具有信号知识的子采样情况下，所开发的自适应子采样算法将根据信号的局部频率内容调整采样率，从而在小范围内以刚好高于样本的奈奎斯特速率进行采样。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.