國立虎尾科技大學 |

Exploiting Structure in Data: Sampling and Signal Processing on Graphs.

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
正題名/作者:	Exploiting Structure in Data: Sampling and Signal Processing on Graphs./
作者:	Varma, Rohan Anilkumar.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2020,
面頁冊數:	211 p.
附註:	Source: Dissertations Abstracts International, Volume: 81-09, Section: B.
Contained By:	Dissertations Abstracts International81-09B.
標題:	Computer science. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=27739115
ISBN:	9781658416191

Exploiting Structure in Data: Sampling and Signal Processing on Graphs.
Varma, Rohan Anilkumar.

Exploiting Structure in Data: Sampling and Signal Processing on Graphs. - Ann Arbor : ProQuest Dissertations & Theses, 2020 - 211 p.

Source: Dissertations Abstracts International, Volume: 81-09, Section: B.

Thesis (Ph.D.)--Carnegie Mellon University, 2020.

This item must not be sold to any third party vendors.

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.

ISBN: 9781658416191Subjects--Topical Terms:

573171
Computer science.
Subjects--Index Terms:

Graph-structured data

Exploiting Structure in Data: Sampling and Signal Processing on Graphs.
LDR:04827nam a2200373 4500 001 951896
005 20200821052221.5
008 200914s2020 ||||||||||||||||| ||eng d
020 $a 9781658416191
035 $a (MiAaPQ)AAI27739115
035 $a AAI27739115
040 $a MiAaPQ $c MiAaPQ
100 1 $a Varma, Rohan Anilkumar. $3 1241393
245 1 0 $a Exploiting Structure in Data: Sampling and Signal Processing on Graphs.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2020
300 $a 211 p.
500 $a Source: Dissertations Abstracts International, Volume: 81-09, Section: B.
500 $a Advisor: Kovacevic, Jelena.
502 $a Thesis (Ph.D.)--Carnegie Mellon University, 2020.
506 $a This item must not be sold to any third party vendors.
520 $a 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.
590 $a School code: 0041.
650 4 $a Computer science. $3 573171
650 4 $a Electrical engineering. $3 596380
650 4 $a Computer engineering. $3 569006
653 $a Graph-structured data
653 $a Graphs
653 $a Machine learning
653 $a Sampling
653 $a Signal processing
690 $a 0984
690 $a 0544
690 $a 0464
710 2 $a Carnegie Mellon University. $b Electrical and Computer Engineering. $3 1182305
773 0 $t Dissertations Abstracts International $g 81-09B.
790 $a 0041
791 $a Ph.D.
792 $a 2020
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=27739115