CIF: Small: Wavelets on Graphs - Theory and Applications

CIF：小：图上的波动--理论与应用--1018977 PI：安东尼奥·奥尔特加（南加州大学）最近的一个关键趋势是可以收集用于分析的数据量急剧增加。例子包括在线社交网络、在线搜索日志、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.