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.