CIF: Small: Wavelets on Graphs - Theory and Applications

University Of Southern California, Los Angeles CA

Investigators

Abstract

CIF:Small:Wavelets on Graphs -- Theory and Applications -- 1018977 PI: 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.