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.
|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|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be