Abstract
Graph signal processing provides an innovative framework to handle data residing on distributed networks, smart grids, neural networks, social networks and many other irregular domains. By leveraging applied harmonic analysis and graph spectral theory, graph signal processing has been extensively exploited, and many important concepts in classical signal processing have been extended to the graph setting such as graph Fourier transform, graph wavelets and graph filter banks. Similarly, many optimization problems in machine learning, sensor networks, power systems, control theory and signal processing can be modeled using underlying network structure. In modern applications, the size of a network is large, and amount of data needed to store and analyze is massive. Due to privacy and security concern, storage limitations and communication cost, a traditional centralized optimization methods are not suitable to solve these optimization problems, and distributed optimization methods are desirable. Graph filters and their inverses have been widely used in denoising, smoothing, sampling, interpolating and learning. Implementation of an inverse filtering procedure on spatially distributed networks (SDNs) is a remarkable challenge, as each agent on an SDN is equipped with a data processing subsystem with limited capacity and a communication subsystem with confined range due to engineering limitations. In this dissertation, we implement the filtering procedure associated with a polynomial graph filter of multiple shifts at the vertex level in a distributed network, where each vertex is equipped with a data processing subsystem for limited computation power and data storage, and a communication subsystem for direct data exchange to its adjacent vertices. We also consider the implementation of inverse filtering procedure associated with a polynomial graph filter of multiple shifts, and we propose two iterative approximation algorithms applicable in a distributed network and in a central facility. We also introduce a preconditioned gradient descent algorithm to implement the inverse filtering procedure associated with a graph filter having small geodesic-width. It is applicable for any invertible graph filters with small geodesic-width. The proposed algorithm converges exponentially, and it can be implemented at vertex level and applied to time-varying inverse filtering on SDNs. Eigenspaces of some matrix on a network have been used for understanding the spectral clustering and influence of a vertex. Following the preconditioned gradient descent algorithm, for a matrix with small geodesic-width, we propose a distributed iterative algorithm to find eigenvectors associated with its given eigenvalue. We also consider the implementation of the proposed algorithm at the vertex/agent level in a spatially distributed network with limited data processing capability and confined communication range.
Notes
If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu
Graduation Date
2020
Semester
Fall
Advisor
Sun, Qiyu
Degree
Doctor of Philosophy (Ph.D.)
College
College of Sciences
Department
Mathematics
Degree Program
Mathematics
Format
application/pdf
Identifier
CFE0008321; DP0023758
URL
https://purls.library.ucf.edu/go/DP0023758
Language
English
Release Date
December 2020
Length of Campus-only Access
None
Access Status
Doctoral Dissertation (Open Access)
STARS Citation
Emirov, Nazar, "Distributed Algorithms and Inverse Graph Filtering" (2020). Electronic Theses and Dissertations, 2020-2023. 350.
https://stars.library.ucf.edu/etd2020/350