Events Calendar

PhD Defense: Sampling Theory for Graph Signals with Applications to Semi-supervised Learning

Speaker: Aamir Anis, USC

Talk Title: PhD Defense: Sampling Theory for Graph Signals with Applications to Semi-supervised Learning

Abstract: The representation, processing and analysis of large-scale data as signals defined over graphs has drawn much interest recently. Graphs allow us to embed natural inter-connectivities between data points and exploit them during processing. As a result, graph signal processing has laid a strong foothold in various modern application domains such as machine learning, analysis of social, transportation, web and sensor networks, and even traditional areas such as image processing and video compression. Although powerful, this research area is still in its infancy. Recent efforts have therefore focused on translating well-developed tools of traditional signal processing for handling graph signals.

An important aspect of graph signal processing is defining a notion of frequency for graph signals. A frequency domain representation for graph signals can be defined using the eigenvectors and eigenvalues of variation operators (e.g., graph Laplacian) that take into account the underlying graph connectivity. These operators can also be used to design graph spectral filters. The primary focus of our work is to develop a theory of sampling for graph signals that answers the following questions: 1. When can one recover a graph signal from its samples on a given subset of nodes of the graph? 2. What is the best choice of nodes to sample a given graph signal? Our formulation primarily works under the assumption of bandlimitedness in the graph Fourier domain, which amounts to smoothness of the signal over the graph. The techniques we employ to answer these questions are based on the introduction of special quantities called graph spectral proxies that allow our algorithms to operate in the vertex domain, thereby admitting efficient, localized implementations.

We also explore the sampling problem in the context of designing wavelet filterbanks on graphs. This problem is fundamentally different since one needs to choose a sampling scheme jointly over multiple channels of the filterbank. We explore constraints for designing perfect reconstruction two-channel critically-sampled filterbanks with low-degree polynomial filters, and conclude that such a design is in general not possible for arbitrary graphs. This leads us to propose an efficient technique for designing a critical sampling scheme that, given pre-designed filters, aims to minimize the overall reconstruction error of the filterbank. We also explore M-channel filterbanks over M-block cyclic graphs (that are natural extensions of bipartite graphs), and propose a tree-structured design in a simpler setting when M is a power of 2.

As an application, we study the graph-based semi-supervised learning problem from a sampling theory point of view. A crucial assumption here is that class labels form a smooth graph signal over a similarity graph constructed from the feature vectors. Our analysis justifies this premise by showing that in the asymptotic limit, the bandwidth (a measure of smoothness) of any class indicator signal is closely related to the geometry of the dataset. Using the sampling theory perspective, we also quantitatively show that the label complexity (i.e., the amount of labeling required for perfect prediction of unknown labels) matches its theoretical value, thereby adding to the appeal of graph-based techniques for semi-supervised learning.

Biography: Aamir Anis received his Bachelor and Master of Technology degree in Electronics and Electrical Communication Engineering from the Indian Institute of Technology (IIT), Kharagpur, India, in 2012. He joined the Electrical Engineering department at the University of Southern California (USC), Los Angeles, in 2012, where he has been working towards a Ph.D. degree in Electrical Engineering. He has been the recipient of the Best Student Paper award at ICASSP 2014. His research interests include graph signal processing with applications in machine learning, and multimedia compression.

Host: Dr. Antonio Ortega

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gloria Halfacre