Ricerc@Sapienza

The goal of this paper is to derive a small perturbation analysis for networks subject to random changes of a small number of edges. Small perturbation theory allows us to derive, albeit approximate, closed form expressions that make possible the theoretical statistical characterization of the network topology changes. The analysis is instrumental to formulate a graph-based optimization algorithm, which is robust against edge failures.

The goal of this paper is to expand graph signal processing tools to deal with cases where the graph topology is not perfectly known. Assuming that the uncertainty affects only a limited number of edges, we make use of small perturbation analysis to derive closed form expressions instrumental to formulate signal processing algorithms that are resilient to imperfect knowledge of the graph topology. Then, we formulate a Bayesian approach to estimate the presence/absence of uncertain edges based only on the observed data and on the statistics of the data.