Non-Bayesian Estimation Framework for Signal Recovery on Graphs

Graph signals arise from physical networks, such as power and communication systems, or as a result of a convenient representation of data with complex structure, such as social networks. We consider the problem of general graph signal recovery from noisy, corrupted, or incomplete measurements and under structural parametric constraints, such as smoothness in the graph frequency domain. In this paper, we formulate the graph signal recovery as a non-Bayesian estimation problem under a weighted mean-squared-error (WMSE) criterion, which is based on a quadratic form of the Laplacian matrix of the graph, and its trace WMSE is the Dirichlet energy of the estimation error w.r.t. the graph. The Laplacian-based WMSE penalizes estimation errors according to their graph spectral content and is a difference-based cost function which accounts for the fact that in many cases signal recovery on graphs can only be achieved up to a constant addend. We develop a new Cramér-Rao bound (CRB) on the Laplacian-based WMSE and present the associated Lehmann unbiasedness condition w.r.t. the graph. We discuss the graph CRB and estimation methods for the fundamental problems of 1) a linear Gaussian model with relative measurements; and 2) bandlimited graph signal recovery. We develop sampling allocation policies that optimize sensor locations in a network for these problems based on the proposed graph CRB. Numerical simulations on random graphs and on electrical network data are used to validate the performance of the graph CRB and sampling policies.

I. Introduction

Graphs are fundamental mathematical structures that are widely used in various fields for network data analysis to model complex relationships within and between data, signals, and processes. Many complex systems in engineering, physics, biology, and sociology constitute networks of interacting units that result in signals that are supported on irregular structures and, thus, can be modeled as signals over the vertices (nodes) of a graph [1], i.e. graph signals. Thus, graph signals arise in many modern applications, leading to the emergence of the area of graph signal processing (GSP) in the last decade (see, e.g. [2]–[5]). GSP theory extends concepts and techniques from traditional digital signal processing (DSP) to data indexed by generic graphs. However, most of the research effort in this field has been devoted to the purely deterministic setting, while methods that exploit statistical information generally lead to better average performance compared to deterministic methods and are better suited to describe practical scenarios that involve uncertainty and randomness [6], [7]. In particular, the development of performance bounds, such as the well-known Cramér-Rao bound (CRB), on various estimation problems that are related to the graph structure is a fundamental step towards attaining statistical GSP tools.