A Caltech Library Service

Signals on Networks: Random Asynchronous and Multirate Processing, and Uncertainty Principles


Teke, Oguzhan (2021) Signals on Networks: Random Asynchronous and Multirate Processing, and Uncertainty Principles. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/44dx-3g83.


The processing of signals defined on graphs has been of interest for many years, and finds applications in a diverse set of fields such as sensor networks, social and economic networks, and biological networks. In graph signal processing applications, signals are not defined as functions on a uniform time-domain grid but they are defined as vectors indexed by the vertices of a graph, where the underlying graph is assumed to model the irregular signal domain. Although analysis of such networked models is not new (it can be traced back to the consensus problem studied more than four decades ago), such models are studied recently from the view-point of signal processing, in which the analysis is based on the "graph operator" whose eigenvectors serve as a Fourier basis for the graph of interest. With the help of graph Fourier basis, a number of topics from classical signal processing (such as sampling, reconstruction, filtering, etc.) are extended to the case of graphs.

The main contribution of this thesis is to provide new directions in the field of graph signal processing and provide further extensions of topics in classical signal processing. The first part of this thesis focuses on a random and asynchronous variant of "graph shift," i.e., localized communication between neighboring nodes. Since the dynamical behavior of randomized asynchronous updates is very different from standard graph shift (i.e., state-space models), this part of the thesis focuses on the convergence and stability behavior of such random asynchronous recursions. Although non-random variants of asynchronous state recursions (possibly with non-linear updates) are well-studied problems with early results dating back to the late 60's, this thesis considers the convergence (and stability) in the statistical mean-squared sense and presents the precise conditions for the stability by drawing parallels with switching systems. It is also shown that systems exhibit unexpected behavior under randomized asynchronicity: an unstable system (in the synchronous world) may be stabilized simply by the use of randomized asynchronicity. Moreover, randomized asynchronicity may result in a lower total computational complexity in certain parameter settings. The thesis presents applications of the random asynchronous model in the context of graph signal processing including an autonomous clustering of network of agents, and a node-asynchronous communication protocol that implements a given rational filter on the graph.

The second part of the thesis focuses on extensions of the following topics in classical signal processing to the case of graph: multirate processing and filter banks, discrete uncertainty principles, and energy compaction filters for optimal filter design. The thesis also considers an application to the heat diffusion over networks.

Multirate systems and filter banks find many applications in signal processing theory and implementations. Despite the possibility of extending 2-channel filter banks to bipartite graphs, this thesis shows that this relation cannot be generalized to M-channel systems on M-partite graphs. As a result, the extension of classical multirate theory to graphs is nontrivial, and such extensions cannot be obtained without certain mathematical restrictions on the graph. The thesis provides the necessary conditions on the graph such that fundamental building blocks of multirate processing remain valid in the graph domain. In particular, it is shown that when the underlying graph satisfies a condition called M-block cyclic property, classical multirate theory can be extended to the graphs.

The uncertainty principle is an essential mathematical concept in science and engineering, and uncertainty principles generally state that a signal cannot have an arbitrarily "short" description in the original basis and in the Fourier basis simultaneously. Based on the fact that graph signal processing proposes two different bases (i.e., vertex and the graph Fourier domains) to represent graph signals, this thesis shows that the total number of nonzero elements of a graph signal and its representation in the graph Fourier domain is lower bounded by a quantity depending on the underlying graph. The thesis also presents the necessary and sufficient condition for the existence of 2-sparse and 3-sparse eigenvectors of a connected graph. When such eigenvectors exist, the uncertainty bound is very low, tight, and independent of the global structure of the graph.

The thesis also considers the classical spectral concentration problem. In the context of polynomial graph filters, the problem reduces to the polynomial concentration problem studied more generally by Slepian in the 70's. The thesis studies the asymptotic behavior of the optimal solution in the case of narrow bandwidth. Different examples of graphs are also compared in order to show that the maximum energy compaction and the optimal filter depends heavily on the graph spectrum.

In the last part, the thesis considers the estimation of the starting time of a heat diffusion process from its noisy measurements when there is a single point source located on a known vertex of a graph with unknown starting time. In particular, the Cramér-Rao lower bound for the estimation problem is derived, and it is shown that for graphs with higher connectivity the problem has a larger lower bound making the estimation problem more difficult.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Networked signal processing, randomized algorithms, asynchronous updates.
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Minor Option:Applied And Computational Mathematics
Awards:Charles and Ellen Wilts Prize, 2021.
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Vaidyanathan, P. P.
Thesis Committee:
  • Chandrasekaran, Venkat (chair)
  • Vaidyanathan, P. P.
  • Wierman, Adam C.
  • Abu-Mostafa, Yaser S.
Defense Date:24 July 2020
Record Number:CaltechTHESIS:09242020-094028488
Persistent URL:
Related URLs:
URLURL TypeDescription's Caltech website. adapted for ch. 2 adapted for ch. 2 adapted for ch. 2 adapted for ch. 2 adapted for ch. 2 adapted for ch. 3 adapted for ch. 3 adapted for ch. 4 adapted for ch. 6 adapted for ch. 6 adapted for ch. 6 adapted for ch. 6 adapted for ch. 6 adapted for ch. 6 adapted for ch. 7 adapted for ch. 7 adapted for ch. 7 adapted for ch. 8 adapted for ch. 9
Teke, Oguzhan0000-0002-1131-5206
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13965
Deposited By: Oguzhan Teke
Deposited On:29 Sep 2020 23:30
Last Modified:03 Nov 2021 20:24

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page