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.