M.Sc Thesis
M.Sc Student Vichik Sergey Covariance Selection, and Algorithms for Distributed Estimation Based on Gaussian Graphical Models Department of Aerospace Engineering Professor Yaakov Oshman

Abstract

We consider the problem of estimating a Gaussian random field using a distributed estimation approach based on Gaussian graphical models. For example, a swarm of aerial vehicles estimating wind magnitude at each vehicle position. The estimated values can be computed in a distributed manner using Gaussian graphical models from each vehicle’s local measurements.

The Gaussian graphical model consists of a probability distribution of the state vector, that is represented by a covariance matrix, and a graph that represents conditional independence between the states. Distributed estimation algorithms can be applied efficiently when the graph has a small number of edges. Therefore, the best model for estimation is required to use a constrained covariance matrix, due to the induced conditional independence property.

The research treats the problem of building a Gaussian graphical model suitable for distributed estimation. This problem entails two major questions. One question is how to create the graph that best suits the distributed estimation needs. The second question is: given the (unconstrained) a priori covariance of the random field, and the conditional independence constraints, how should one select the constrained covariance, optimally representing the (given) a priori covariance, but also satisfying the constraints? In 1972, Dempster provided a solution, optimal in the maximum likelihood sense, to the above problem. We rigorously prove herein that Dempster’s covariance is not optimal in most minimum mean squared error (MMSE) estimation problems. We also propose a method for finding the MMSE optimal covariance, and study its properties. We then illustrate the analytical results via a numerical example, that demonstrates the estimation performance advantage gained by using the optimal covariance vs Dempster’s covariance. The numerical example also shows that, for the particular estimation scenario examined, Dempster’s covariance violates the necessary conditions for optimality.

In addition, we propose a method for building a graph for the Gaussian graphical model, that allows good estimation performance with minimal communication between the vehicles. We study the performance of the estimation algorithm, that uses the proposed Gaussian graphical model, via extensive simulations with various swarm geometries and sizes. The numerical results show that, with the proposed model, the estimation error may be reduced significantly, compared to standalone estimation, and is comparable to that of a full centralized, and, therefore, unconstrained, estimator. For all examined scenarios, the model that selects the optimal covariance is shown to outperform the model with Dempster’s covariance.