CIF: Small: Graph Signal Sampling: Theory and Applications

University Of Southern California, Los Angeles CA

Investigators

Abstract

Modern society is increasingly reliant on large scale, distributed, interconnected, and complex systems, such as the Internet, smart grids, intelligent buildings or highways. Furthermore, much of the information now being generated is also interconnected in complex ways (e.g., the Web). While these systems and datasets can be monitored by recording relevant data, the volumes of such data make it difficult to address critical tasks, such as anomaly detection, in a timely manner. These datasets often exhibit a natural graph structure, with graph nodes representing measurements or information (e.g., the temperature of a sensor or data from a web page), and graph edges representing the relationships between nodes (e.g., distance between sensors or links between webpages). This project develops novel methods for sampling of very large scale graph datasets, with the goal of making it possible to measure only a small fraction of carefully selected nodes, while preserving the ability to analyze the whole system. Sampling theory is a major element of signal processing theory and applications, but has only recently been considered for graph signals. While recent progress has been made under the assumption that the graph is fully known, these techniques are prohibitively expensive for practical datasets of interest. This project addresses fundamental questions for the challenging problem of sampling when only partial graph information is available (e.g., decisions based on smaller subsets of connected nodes). For example, given local graph connectivity information and assumptions about the graph signals of interest, such as their frequency localization, the goal is to identify the best set of vertices to sample locally in order to obtain a reliable estimate of the corresponding global graph signals.