Graph signal processing is an emerging paradigm in signal processing which took birth in the search for a set of consistent mathematical tools to analyze signals which occur over networks or graphs. The viewpoint of signals through graphs is universal and applicable to a large variety of diverse real-world problems. In this thesis, we make contributions to graph signal processing in two different settings: graph signal processing theory and graph signal processing with machine learning. In the first setting, we derive a novel Hilbert transform framework for graph signals in answering the question of whether amplitude and frequency modulations be defined for graph signals. We generalize Gabor’s analytic signal and define amplitude and phase modulations for graph signals via a Hilbert transform which is shown to demonstrate ability to highlight anomalies or singularities over graphs.

In the second setting, we bring together some of the popular machine learning approaches to graph signal processing, demonstrating how the two thought pro- cesses can be mutually coupled meaningfully for significant benefits. Specifically, we deal with the problem of predicting vector target signals which are graph signals over an associated graph. The input is taken to be a general quantity associated to the graph signal, but not necessarily the same physical quantity as that of the graph signal. In this way, we make graph signal output predictions with inputs which are agnostic to a graph structure. We apply this line of thought to extend some of the popular and powerful techniques in machine learning to graph signal setting: kernel regression, multi-kernel regression, Gaussian processes, and extreme learning machines. We show that our approach outperforms the conventional versions when the training samples are scarce and noisy: application to many real-world graph signal applications show that similar prediction performance as that of non-graph- aware versions is achieved with much less training data, and that too corrupted with noise. This also includes the extreme cases where data is partly missing or corrupted with large perturbations. This observation in turn points to the efficiency of our approach in terms of both availability of resources and computational complexity, which usually increases as datasize increases. Our approach stands out uniquely in being able to handle cases where the input and output are different physical quantities. It is also interesting to note that our approach performs reasonably well even in cases where the graph exists but is not known to the user.

We conclude by addressing the general problem of learning graphs from graph signals in two ways. First, we show that learning of connected graphs can be trans- formed into a convex optimization constraint which can be easily augmented to any of the existing graph learning techniques. Second, we propose a sparsity based approach to learn graphs in a hyperparameter-free manner which is computation- ally efficient. In our first contribution in the context of learning graphs, we are concerned with learning connected graphs which describe the data, whereas in the second part, we focus on learning graphs that are effective in making predictions for the signal value at the different nodes.

We develop a multi-kernel based regression method for graph signal processing where the target signal is assumed to be smooth over a graph. In multi-kernel regression, an effective kernel function is expressed as a linear combination of many basis kernel functions. We estimate the linear weights to learn the effective kernel function by appropriate regularization based on graph smoothness. We show that the resulting optimization problem is shown to be convex and propose an accelerated projected gradient descent based solution. Simulation results using real-world graph signals show efficiency of the multi-kernel based approach over a standard kernel based approach.

We propose Hilbert transform and analytic signal construction for signals over graphs. This is motivated by the popularity of Hilbert transform, analytic signal, and modulation analysis in conventional signal processing, and the observation that complementary insight is often obtained by viewing conventional signals in the graph setting. Our definitions of Hilbert transform and analytic signal use a conjugate symmetry-like property exhibited by the graph Fourier transform (GFT), resulting in a 'one-sided' spectrum for the graph analytic signal. The resulting graph Hilbert transform is shown to possess many interesting mathematical properties and also exhibit the ability to highlight anomalies/discontinuities in the graph signal and the nodes across which signal discontinuities occur. Using the graph analytic signal, we further define amplitude, phase, and frequency modulations for a graph signal. We illustrate the proposed concepts by showing applications to synthesized and real-world signals. For example, we show that the graph Hilbert transform can indicate presence of anomalies and that graph analytic signal, and associated amplitude and frequency modulations reveal complementary information in speech signals.

In presence of sparse noise we propose kernel regression for predicting output vectors which are smooth over a given graph. Sparse noise models the training outputs being corrupted either with missing samples or large perturbations. The presence of sparse noise is handled using appropriate use of l(1)-norm along-with use of l(2)-norm in a convex cost function. For optimization of the cost function, we propose an iteratively reweighted least-squares (IRLS) approach that is suitable for kernel substitution or kernel trick due to availability of a closed form solution. Simulations using real-world temperature data show efficacy of our proposed method, mainly for limited-size training datasets.

We address the problem of prediction of multivariate data process using an underlying graph model. We develop a method that learns a sparse partial correlation graph in a tuning-free and computationally efficient manner. Specifically, the graph structure is learned recursively without the need for cross validation or parameter tuning by building upon a hyperparameter-free framework. Our approach does not require the graph to be undirected and also accommodates varying noise levels across different nodes. Experiments using real-world datasets show that the proposed method offers significant performance gains in prediction, in comparison with the graphs frequently associated with these datasets.