Topics in Harmonic Analysis on Combinatorial Graphs
Genre
Thesis/DissertationDate
2014Author
Gidelew, Getnet AbebeAdvisor
Pesenson, I. Z. (Isaak Zalmanovich)Committee member
Berhanu, ShiferawMendoza, Gerardo A.
Nowak, Krzysztof G.
Department
MathematicsSubject
MathematicsAverage Sampling On Graphs
Harmonic Analysis On Graphs
Multi-resolution On Graphs
Quadratures On Graphs
Sampling On Graphs
Signal Approximation On Graphs
Permanent link to this record
http://hdl.handle.net/20.500.12613/2914Metadata
Show full item recordDOI
http://dx.doi.org/10.34944/dspace/2896Abstract
In recent years harmonic analysis on combinatorial graphs has attracted considerable attention. The interest is stimulated in part by multiple existing and potential applications of analysis on graphs to information theory, signal analysis, image processing, computer sciences, learning theory, and astronomy. My thesis is devoted to sampling, interpolation, approximation, and multi-resolution on graphs. The results in the existing literature concern mainly with these theories on unweighted graphs. My main objective is to extend existing theories and obtain new results about sampling, interpolation, approximation, and multi-resolution on general combinatorial graphs such as directed, undirected and weighted.ADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.eduCollections
Related items
Showing items related by title, author, creator and subject.
-
Explicit Bounds from the Alon–Boppana Theorem© 2018, © 2018 Taylor & Francis. The purpose of this article is to give explicit methods for bounding the number of vertices of finite k-regular graphs with given second eigenvalue. Let X be a finite k-regular graph and μ1(X) the second largest eigenvalue of its adjacency matrix. It follows from the well-known Alon–Boppana theorem that for any ε > 0 there are only finitely many such X with μ1(X) < (2 − ϵ)√k − 1, and we effectively implement Serre's quantitative version of this result. For any k and ε, this gives an explicit upper bound on the number of vertices in a k-regular graph with μ1(X) < (2 − ϵ)√k − 1).
-
EXPLORING MULTIPLEX NETWORKSComplex network theory has been well established as one of the main tools for understanding and analyzing the behavior of the natural systems that surround us. Social networks, genetic and protein interaction networks, airline and road traffic networks, brain connectivity networks and web graphs are only some of the examples. As network theory evolves it becomes more apparent that these complex systems are often composed of multiple types of interactions, each carrying a different piece of information, and therefore are commonly represented in the form of multiplex networks, where each layer represents a different type of interaction among nodes. In addition to the interactions among the nodes of the networks, these systems also present correlations among the various types of interactions, as represented by the intrinsic structure and the associations of the various layers of the graph. For example, in social sciences, a network with a large overlap between two layers that represent two distinct types of people interactions i.e. friendship and professional ties might indicate that there is an interconnection between the two in the given network. In another example, in transportation networks, where nodes represent airports connected by flights operated by specific airlines (each airline representing a layer of the graph), the structure of the layers can provide information about the airline: traditional airlines such as Lufthansa tend to have a large overlap in activity pattern with other airlines, whereas low-cost airlines such as easyJet tend to avoid such overlaps. Due to their ability to represent such complex entity interactions, multiplex networks have lately been the focus of a large part of the research community, studying a variety of aspects, such as structural measures, node communities detection, layer reducibility, network generative models, and information spreading. In this work we focus on techniques for the exploration of the intrinsic structure of multiplex networks, and contemplate ways of addressing common challenges of learning from multiplex networks. In particular, our work focuses on three main directions: structured regression, graph summarization and graph similarity. We analyze and discuss the main challenges of each of these research directions, and then we propose novel methods to address them. For each problem, we utilize artificial data to study their effectiveness, understand their intrinsic properties and evaluate their behavior under a controlled network structure. Then, we report applications on real-world data sets, from variety of domains, and compare our proposed methods with state-of-the-art and well established baseline methods. Through this work, we aim to offer proof that the networks' intrinsic structure, when utilized, can increase the informative power of network theory models and allow researchers to build more educated algorithms.
-
Graph-based Modern Nonparametrics For High-dimensional DataDeveloping nonparametric statistical methods and inference procedures for high-dimensional large data have been a challenging frontier problem of statistics. To attack this problem, in recent years, a clear rising trend has been observed with a radically different viewpoint--``Graph-based Nonparametrics," which is the main research focus of this dissertation. The basic idea consists of two steps: (i) representation step: code the given data using graphs, (ii) analysis step: apply statistical methods on the graph-transformed problem to systematically tackle various types of data structures. Under this general framework, this dissertation develops two major research directions. Chapter 2—based on Mukhopadhyay and Wang (2019a)—introduces a new nonparametric method for high-dimensional k-sample comparison problem that is distribution-free, robust, and continues to work even when the dimension of the data is larger than the sample size. The proposed theory is based on modern LP-nonparametrics tools and unexplored connections with spectral graph theory. The key is to construct a specially-designed weighted graph from the data and to reformulate the k-sample problem into a community detection problem. The procedure is shown to possess various desirable properties along with a characteristic exploratory flavor that has practical consequences. The numerical examples show surprisingly well performance of our method under a broad range of realistic situations. Chapter 3—based on Mukhopadhyay and Wang (2019b)—revisits some foundational questions about network modeling that are still unsolved. In particular, we present unified statistical theory of the fundamental spectral graph methods (e.g., Laplacian, Modularity, Diffusion map, regularized Laplacian, Google PageRank model), which are often viewed as spectral heuristic-based empirical mystery facts. Despite half a century of research, this question has been one of the most formidable open issues, if not the core problem in modern network science. Our approach integrates modern nonparametric statistics, mathematical approximation theory (of integral equations), and computational harmonic analysis in a novel way to develop a theory that unifies and generalizes the existing paradigm. From a practical standpoint, it is shown that this perspective can provide adequate guidance for designing next-generation computational tools for large-scale problems. As an example, we have described the high-dimensional change-point detection problem. Chapter 4 discusses some further extensions and application of our methodologies to regularized spectral clustering and spatial graph regression problems. The dissertation concludes with the a discussion of two important areas of future studies.
