Description

The sparse information-form provides an important method for obtaining least-squares solutions to very large systems. However, the fill-in resulting from marginalisation (and also the Cholesky factorisation required for solving the system) can become an impediment to efficiency. This paper investigates a method to reintroduce sparseness after marginalisation while maintaining an upper bound on the covariance estimate. This latter constraint is essential for consistent data fusion. The key result of this paper is to show that, following a link removal, the optimal upper bound is attainable while altering only those nodes within the Markov blanket of the originally linked nodes. This proves that conservative sparsification is cost effective for arbitrarily large systems. While the results in this paper are applied to the SLAM problem, we expect the method of conservative sparsification to have wide application. Being able to sparsify the structure of large systems is especially pertinent to increasing the scale of distributed and decentralised systems; sensor networks, cooperative navigation, and the like.

Abstract

This paper presents a new technique for sparsification of the information matrix of a multi-dimensional Gaussian distribution. We call this technique Conservative Sparsification (CS) and show that it produces estimates which are consistent with respect to an optimal filter. This technique was applied to the Simultaneous Localisation and Mapping (SLAM) problem, and compared with two existing sparsification approaches; the Sparse Extended Information Filter (SEIF) and the Data Discarding Sparse Extended Information Filter (DDSEIF). Simulation demonstrates that CS is a consistent approach and provides a tighter upper bound than existing conservative methods.

Download

Full paper [pdf] (308 kb, 8 pages)