COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Exploiting Structure in Data: Sampling and Signal Processing on Graphs
by Varma, Rohan Anilkumar, Ph.D., Carnegie Mellon University, 2020, 211; 27739115
Abstract (Summary)

With the explosive growth of information and communication, data is being generated at an unprecedented rate from various sources, including multimedia, sensor networks, biological systems, social networks, and physical infrastructure. Research in graph signal processing aims to develop tools for processing such data by providing a framework for the analysis of high-dimensional data defined on irregular graph domains. Graph signal processing extends fundamental signal processing concepts to data supported on graphs that we refer to as graph signals. In this work, we study two fraternal problems: (1) sampling and (2) reconstruction of signals on graphs. Both of these problems are eminent topics in the field of signal processing over the past decades and have meaningful implications for many real-world problems including semi-supervised learning and active learning on graphs. Sampling is the task of choosing or measuring some representative subset of the signal such that we can interpolate and recover the whole signal. In many settings, acquiring samples is expensive and it is desirable to be able to approximate the signal as efficiently as possible. Signal reconstruction refers the task of recovering the true graph signal given noisy, incomplete, or corrupt measurements. It is evident that these two problems are intimately tied to the underlying graph structure.

In this body of work, we study the tasks of sampling and reconstruction for two complementary classes of graph signals that broadly capture characteristics of most graph-structured data: (1) smooth signals that are characterized by slow transitions with respect to graph and (2) piecewise-smooth signals that are characterized by localized behavior, abrupt discontinuities or fast transitions over the underlying graph. We examine why a one-size-fits-all approach may not always be appropriate and consequently design algorithms and frameworks specific to each graph signal model. We first present a sampling theory in the spirit of Shannon and Nyquist and study the limits of sampling these two graph signal models under passive and active settings. We present a framework for the reconstruction or estimation of graph signals and investigate the limitations of these methods. Graph trend filtering is a flexible framework for estimation on graphs that is adaptive to inhomogeneity in the level of smoothness and localized characteristics of an observed signal across nodes. We strengthen the graph trend filtering framework by considering a family of possibly non-convex regularizers that exhibit superior reconstruction performance over minimization for the denoising of piecewise smooth graph signals. We study product graphs which are a generative model that allows us to decompose a large real-world large graph into smaller graphs. We develop frameworks for sampling and reconstruction that both lessen the computational complexity and achieve better performance by availing of the inherent structure in product graphs.

The irregularity of the underlying structure of the data in contrast to the regularity in classical signal processing makes studying these problems on graphs challenging but also compelling. A key theme throughout this work is the interplay between the graph structure and the signal that lies on it. We study how structural properties of both the graph and the signal on the graph inform not only how well we can perform these two tasks but also the design of algorithms and strategies to perform them efficiently. Moreover, we illustrate the power of these proposed tools via vignettes on semi-supervised learning and efficient communication in sensor networks.

Indexing (document details)
Advisor: Kovačević, Jelena
Commitee: Singh, Aarti, Moura, José, Chi, Yuejie
School: Carnegie Mellon University
Department: Electrical and Computer Engineering
School Location: United States -- Pennsylvania
Source: DAI-B 81/8(E), Dissertation Abstracts International
Subjects: Computer science, Electrical engineering, Computer Engineering
Keywords: Graph-structured data, Graphs, Machine learning, Sampling, Signal processing
Publication Number: 27739115
ISBN: 9781658416191
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy