Theses and Dissertations
Permanent URI for this collectionhttp://ir.daiict.ac.in/handle/123456789/1
Browse
3 results
Search Results
Item Open Access Downsampling of signals on graphs: an algebraic perspective(Dhirubhai Ambani Institute of Information and Communication Technology, 2018) Vaishnav, Nileshkumar; Tatu, AdityaReal-world data such as weather data, seismic activity data, sensor networks data and social network data can be represented and processed conveniently using a mathematical structure called Graph. Graphs are a collection of vertices and edges. The relational structure between the vertices can be represented in form of a matrix called the adjacency matrix. A Graph Signal is a signal supported on a given graph. The framework of processing of signals on graphs is called Graph Signal Processing (GSP). Various signal processing concepts (e.g. Fourier Transform, filtering, translation, downsampling) need to be defined in the context of graphs. A common approach is to define a Fourier Transform for a graph (called Graph Fourier Transform - GFT), and use it to define other signal processing concepts. There are two popular approaches to define GFT for a graph: 1) using Graph Laplacian 2) using adjacency matrix. In the first method, GFT is interpreted as expansion of a given signal in the eigenvectors of the Graph Laplacian. The second method, i.e., using the adjacency matrix, results in an algebraic framework for graph signals and shift invariant filters. In the study of Graph Signal Processing, we often encounter signals which are smooth in nature. Such signals, which have low variations, can be represented efficiently using samples on fewer number of vertices. The process of selecting such vertices is called graph downsampling. As graphs do not exhibit a natural ordering of data, selection of vertices is not trivial. In this thesis, we analyze a class of graphs called Bipartite Graphs from downsampling perspective and then provide a GFT based approach to downsample signals on arbitrary graphs. For bandlimited signals on a graph, a test is provided to identify whether signal reconstruction is possible from the given downsampled signal. Moreover, if the signal is not bandlimited, we provide a quality measure for comparing different downsampling schemes. Using this quality measure, we propose a greedy downsampling algorithm. The proposed method is applicable to directed graphs, undirected graphs, and graphs with negative edge-weights. We provide several experiments demonstrating our downsampling scheme, and compare our quality measure with other existing measures (e.g. cut-index). We also provide a method to assign adjacency matrix to the downsampled vertices using an analogy from the bipartite graphs. We also examine the concepts of homomorphism and isomorphism between two graphs from signal processing point of view, and refer to them as GSP-isomorphism and GSP-homomorphism, respectively. Collectively, we refer to these concepts as Structure Preserving Maps. The fact that linear combination of signals and linear transforms on signals are meaningful operations has implications on the GSP-isomorphism and GSP-homomorphism, which diverges from the topological interpretations of the same concepts (i.e. graph-isomorphism and graphhomomorphism). When Structure Preserving Maps exist between two graphs, signals and filters can be mapped between them while preserving spectral properties. We examine conditions on adjacency matrices for such maps to exist. We also show that isospectral graphs form a special case of GSP-isomorphism and that GSP-isomorphism and GSP-homomorphism is intrinsic to resampling and downsampling process.Item Open Access The Study of Vertex Coloring Algorithms Using Heuristic Approaches(Dhirubhai Ambani Institute of Information and Communication Technology, 2018) Lodha, Pratik; Muthu, RahulGraph vertex coloring is one of the most studied NP-complete optimization problem (READ, 1972) [2]. The problem is that; given a graph G, determine the number of colors required to color G, so that no two adjacent vertices share the same color. And the minimum number of colors required to color graph is known as Chromatic Number and is denoted by ?(G). By using existing properties of eccentricity, BFS, DFS (West, 2000) [3] and graph components we have proposed three new heuristic algorithms to obtain approximated chromatic number of a given graph G. And these approaches are as follows: 1. Eccentricity based coloring 2. DFS based coloring, and 3. Maximum degree based coloring.Item Open Access The Study of Cycles in 2-connected Graphs Specifically Odd Graphs(Dhirubhai Ambani Institute of Information and Communication Technology, 2018) Thakker, Avani; Muthu, RahulCounting the number of cycles in an undirected graph is a classical problemwhich is known to be intractable and so research on this problem typically focuses on approximation algorithms, special cases, heuristics and some variants of the problem. This problem has been extensively studied for its applications in areas of communication systems, artificial intelligence and signal processing. In Complexity theory, this problem lies in the class of #P-complete problem. There may be exponentially many simple cycles in a graph. We observed growth in the number of cycles by adding ears to a 2-connected graph. As analyzed, the growth was exponential. Counting or finding cycles and paths of graphs like complete graphs, presents no interest, in particular since everything is already known analytically. Hence, we studied the cycle structure in Odd Graphs. We analytically obtained cycle lengths that are certainly present in an odd graph without traversing the graph structure. Further, we added minimal number of edges to an odd graph to make the graph pancyclic.