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.
-
Products of Farey graphs are totally geodesic in the pants graph© 2016 World Scientific Publishing Company. We show that for a surface ∑, the subgraph of the pants graph determined by fixing a collection of curves that cut ∑ into pairs of pants, once-punctured tori, and four-times-punctured spheres is totally geodesic. The main theorem resolves a special case of a conjecture made in [2] and has the implication that an embedded product of Farey graphs in any pants graph is totally geodesic. In addition, we show that a pants graph contains a convex n-flat if and only if it contains an n-quasi-flat.
-
ON CONVOLUTIONAL NEURAL NETWORKS FOR KNOWLEDGE GRAPH EMBEDDING AND COMPLETIONData plays the key role in almost every field of computer sciences, including knowledge graph field. The type of data varies across fields. For example, the data type of knowledge graph field is knowledge triples, while it is visual data like images and videos in computer vision field, and textual data like articles and news in natural language processing field. Data could not be utilized directly by machine learning models, thus data representation learning and feature design for various types of data are two critical tasks in many computer sciences fields. Researchers develop various models and frameworks to learn and extract features, and aim to represent information in defined embedding spaces. The classic models usually embed the data in a low-dimensional space, while neural network models are able to generate more meaningful and complex high-dimensional deep features in recent years. In knowledge graph field, almost every approach represent entities and relations in a low-dimensional space, because there are too many knowledge and triples in real-world. Recently a few approaches apply neural networks on knowledge graph learning. However, these models are only able to capture local and shallow features. We observe the following three important issues with the development of feature learning with neural networks. On one side, neural networks are not black boxes that work well in every case without specific design. There is still a lot of work to do about how to design and propose more powerful and robust neural networks for different types of data. On the other side, more studies about utilizing these representations and features in many applications are necessary. What's more, traditional representations and features work better in some domains, while deep representations and features perform better on other domains. Transfer learning is introduced to bridge the gap between domains and adapt various type of features for many tasks. In this dissertation, we aim to solve the above issues. For knowledge graph learning task, we propose a few important observations both theoretically and practically for current knowledge graph learning approaches, especially for knowledge graph learning based on Convolutional Neural Networks. Besides the work in knowledge graph field, we not only develop different types of feature and representation learning frameworks for various data types, but also develop effective transfer learning algorithm to utilize the features and representations. The obtained features and representations by neural networks are utilized successfully in multiple fields. Firstly, we analyze the current issues on knowledge graph learning models, and present eight observations for existing knowledge graph embedding approaches, especially for approaches based on Convolutional Neural Networks. Secondly, we proposed a novel unsupervised heterogeneous domain adaptation framework that could deal with features in various types. Multimedia features are able to be adapted, and the proposed algorithm could bridge the representation gap between the source and target domains. Thirdly, we propose a novel framework to learn and embed user comments and online news data in unit of sessions. We predict the article of interest for users with deep neural networks and attention models. Lastly, we design and analyze a large number of features to represent dynamics of user comments and news article. The features span a broad spectrum of facets including news article and comment contents, temporal dynamics, sentiment/linguistic features, and user behaviors. Our main insight is that the early dynamics from user comments contribute the most to an accurate prediction, while news article specific factors have surprisingly little influence.
-
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.
