Learning representations for signal and data processing on directed graphs

Thesis (Ph. D.)--University of Rochester. Department of Electrical and Computer Engineering, 2020.Network processes are becoming increasingly ubiquitous, with examples ranging from the measurements of neural activities at different regions of the brain to infectious states of individuals in a population affected by an epidemic. Such network data can be conceptualized as graph signals supported on the vertices of the adopted graph abstraction to the network. Under the natural assumption that the signal properties relate to the underlying graph topology, the goal of graph signal processing (GSP) is to develop algorithms that fruitfully exploit this relational structure. This dissertation contributes to this effort by advancing signal representations for information processing on (possibly directed) networks. An instrumental GSP tool is the graph Fourier transform (GFT), which decomposes a graph signal into orthonormal components describing different modes of variation with respect to the graph topology. In the first part of this dissertation, we study the problem of constructing a graph Fourier transform (GFT) for directed graphs (digraphs). Unlike existing approaches, to capture low, medium, and high frequencies, we seek a digraph (D)GFT such that the orthonormal frequency components are as spread as possible in the graph spectral domain. To that end, we advocate a two-step design whereby we: (i) find the maximum directed variation (i.e., a novel notion of frequency on a digraph) a candidate basis vector can attain; and (ii) minimize a smooth spectral dispersion function over the achievable frequency range to obtain a spread DGFT basis. Both steps involve non-convex, orthonormality-constrained optimization problems, which are tackled via a provably-convergent feasible optimization method on the Stiefel manifold. We discuss a data-adaptive variant whereby a sparsifying orthonormal transform is learnt to encourage parsimonious representations of bandlimited signals. Distributed graph filtering based on the learnt transform is investigated as well. Graph frequency analyses require a specification of the underlying digraph which might not be readily available. In the second part of this thesis, we consider inferring a network given observations of graph signals generated by linear diffusion dynamics on the sought graph. Observations are modeled as the outputs of a linear graph filter (i.e., a polynomial on a diffusion graph-shift operator encoding the unknown graph topology), excited with input graph signals with arbitrarily-correlated nodal components. In this context, we first rely on observations of the output signals along with prior statistical information on the inputs to identify the diffusion filter. Such problem entails solving a system of quadratic matrix equations which we recast as standard optimization problems with provable performance guarantees. Subsequent identification of the network topology boils down to finding a sparse graph-shift operator that is simultaneously diagonalizable with the given filter estimate. We further develop an (online) adaptive scheme to track the (possibly) time-varying network structure, and affect memory and computational savings by processing the data on-the-fly as they are acquired. We illustrate the effectiveness of the novel DGFT and topology inference algorithms through numerical tests on synthetic and real-world networks