CIF: Small: Wavelets on Graphs - Theory and Applications

CIF：小：图上的小波--理论和应用--1018977PI：Antonio Ortega(南加州大学)最近的一个主要趋势是可收集用于分析的数据量急剧增加。例如，在线社交网络、在线搜索日志、DNA分析、监控等等。一个主要的挑战是从这些庞大的数据集中提取有用的信息，以至于这些数据中的许多可能没有得到充分利用。这项研究的目的是开发创新的数据表示工具，以便能够显著地更快和更准确地分析这些新兴的数据集。这项研究的动机是两个观察：i)这些新兴数据集中的数据点通常可以被视为大图的一部分；ii)图上的数据分析工具本质上倾向于全局的，使得很难识别在图的相对较小的区域中表现出来的趋势。受过去20年发展起来的小波技术的启发，这项工作研究了定义在图上的一类新的小波。这个项目研究了图上这些小波的基本理论，包括局部化、可逆和临界采样变换的设计。该团队还讨论了两个具体的应用，以说明这些方法的潜在好处。在一个应用中，这些新工具被应用于基因组数据集(其中图形对应于遗传路径)和社交网络中的数据分析。第二类应用包括将这些新的转换应用于图像和视频处理的新工具的开发。

CIF:Small:Wavelets on Graphs -- Theory and Applications -- 1018977PI: Antonio Ortega (University of Southern California) A key recent trend has been towards dramatic increases in the amounts of data that can be gathered for analysis. Examples include online social networks, online search logs, DNA analysis, surveillance, among many others. A major challenge is to extract useful information from these large data-sets, to the point that there is a risk that much of these data could be underutilized. This research aims at developing innovative data representation tools to enable significantly faster and more accurate analysis of these emerging data-sets.This research is motivated by two observations: i) data points in these emerging data-sets can often be seen as part of a large graph and ii) tools for analysis of data on graphs tend to be global in nature, making it difficult to identify trends that manifest themselves in relatively small regions of the graph. Inspired by wavelet techniques developed over the past 20 years, this work studies a new class of wavelets that are defined on graphs. This project studies the underlying theory for these wavelets on graphs, including the design of localized, invertible and critically sampled transforms. The team is also addressing two concrete applications to illustrate the potential benefits of these methods. In one application these new tools are applied to Genomic data sets (where graphs correspond to genetic pathways) and to analysis of data in social networks. The second class of applications consists of applying these new transforms to the development of new tools for image and video processing.