Source-linked AI summary
Gossip and Distributed Kalman Filtering: Weak Consensus under Weak Detectability
Soummya Kar, José M. F. Moura
TL;DR
The paper studies collaborative estimation with intermittent inter-sensor communication and asks how filtering errors reach consensus in random networks. It presents GIKF results showing stochastic boundedness and weak consensus under weak detectability.
Problem
The paper addresses collaborative estimation in random networks and examines how filtering errors reach consensus across sensors.
Method
The GIKF achieves inter-sensor collaboration through intermittent exchanges of filtering states, with error covariances analyzed through a random dynamical system.
Results
The error process is stochastically bounded, and the conditional error covariance at a randomly selected sensor converges in distribution to an invariant measure.
Takeaways & Limitations
The results establish weak consensus of filtering errors in the gossip distributed filtering setting.
Takeaways & Limitations
The results rely on a weak detectability assumption.
Abstract
from arXiv · showhide
The paper presents the gossip interactive Kalman filter (GIKF) for distributed Kalman filtering for networked systems and sensor networks, where inter-sensor communication and observations occur at the same time-scale. The communication among sensors is random; each sensor occasionally exchanges its filtering state information with a neighbor depending on the availability of the appropriate network link. We show that under a weak distributed detectability condition: 1. the GIKF error process remains stochastically bounded, irrespective of the instability properties of the random process dynamics; and 2. the network achieves \emph{weak consensus}, i.e., the conditional estimation error covariance at a (uniformly) randomly selected sensor converges in distribution to a unique invariant measure on the space of positive semi-definite matrices (independent of the initial state.) To prove these results, we interpret the filtered states (estimates and error covariances) at each node in the GIKF as stochastic particles with local interactions. We analyze the asymptotic properties of the error process by studying as a random dynamical system the associated switched (random) Riccati equation, the switching being dictated by a non-stationary Markov chain on the network graph.
A. Background and Motivation
The paper develops GIKF for distributed Kalman filtering with random, intermittent inter-sensor communication at the same time-scale as sensing. Under weak distributed detectability, it establishes stochastic boundedness and weak consensus despite potentially unstable dynamics.
- Motivation and approach: GIKF combines local Kalman filtering with occasional asynchronous state exchanges over a random communication network.Sensors exchange filtering states with randomly selected neighbors before processing current observations.
- Motivation and approach: Each sensor may observe only part of the process, so individual sensors cannot necessarily resolve the estimation problem alone.The paper studies collaborative estimation that provides reliable estimates at every sensor.
- Main guarantees: Weak distributed detectability guarantees stochastic boundedness of the GIKF error process irrespective of the instability properties of the random dynamics.The condition is also necessary for bounded-error estimation in the centralized setting for unstable systems.
- Main guarantees: Weak consensus means that a uniformly randomly selected sensor’s conditional error covariance converges in distribution to a unique invariant measure independent of the initial state.The same invariant measure describes the asymptotic distribution of error processes across sensors.
- Analysis framework: The analysis models filtered states as interacting stochastic particles and studies a switched random Riccati equation driven by a non-stationary Markov chain.This particle viewpoint avoids directly analyzing the more complicated, non-Markov sensor covariance sequence.
- Scope: The paper resolves existence conditions for the invariant measure but does not characterize that measure as a function of communication and observation policies.It emphasizes minimal conditions for stability rather than an analytic formula for the limiting measure.
B. Notation and Preliminaries
This section establishes the mathematical setting for probability measures, weak convergence, and ordered spaces of symmetric positive semidefinite matrices. These objects provide the state space and convergence framework for the later Riccati analysis.
- Ordered matrix space: The cone of positive semidefinite matrices induces a partial order, while its nonempty interior defines a strong ordering.Normality provides a norm comparison for matrices ordered within the cone.
- Ordered matrix space: The analysis uses the separable Banach space of symmetric n × n matrices equipped with the induced 2-norm.Positive semidefinite matrices form a closed, convex, solid, normal, minihedral cone in this space.
- Probability measures: Weak convergence of probability measures is defined through convergence of integrals against bounded continuous functions.The paper also identifies weak convergence with convergence in distribution.
- Probability measures: The Prohorov metric metrizes weak convergence on the probability-measure space used by the analysis.The resulting metric space is complete and separable.
A. Problem setup
The problem is distributed estimation of a linear dynamical system when sensors communicate randomly and observe at the same time-scale. The paper imposes weak connectivity and weak detectability conditions to support stable collaborative filtering.
- Networked estimation model: The network consists of sensors that exchange filtering states with neighbors while communication and observation occur at the same time-scale.The communication structure is modeled by an undirected graph with randomly varying adjacency matrices.
- Communication model: A generic random communication protocol allows each sensor to communicate with only a fraction of its allowable neighbors at a given instant.The protocol encompasses gossiping and graph-matching communication schemes.
- Connectivity and observability: Weak connectivity is represented through an irreducible and aperiodic mean adjacency matrix, whose associated Markov chain has a unique uniform invariant distribution.Positive recurrence supports information dissemination through random walks on the network.
- Connectivity and observability: Weak detectability requires a graph walk whose accumulated observations provide the needed detectability for the signal dynamics.The condition is minimal because centralized estimation also requires it for arbitrary signal dynamics.
- Main objective: The setup seeks asymptotically equally good estimates at every sensor despite limited sensing and communication capabilities.The paper studies the resulting notion of consensus for distributed filtering errors.
B. An Interacting Particle Representation
The paper reindexes distributed covariance evolution as interacting particles moving through the network. Each particle follows a Markov chain and applies location-dependent Riccati maps, producing a tractable semi-Markov representation.
- Particle model: The link-formation process can be represented by particles moving on the graph as identical Markov chains.A particle’s location records the sensor whose Riccati operator governs its covariance update.
- Markov structure: Each particle location process is Markov and ergodic, with the uniform distribution on network nodes as its attracting invariant distribution.Finite-state irreducibility and aperiodicity provide the convergence properties.
- Particle model: Each particle’s switched Riccati sequence is governed by its Markov-chain location and does not directly equal the covariance sequence at a fixed sensor.This distinction motivates studying particle sequences instead of the more dependent sensor sequences.
- Markov structure: The particle Riccati sequence is semi-Markov when conditioned on its Markov switching sequence.This structure supplies the basis for analyzing its asymptotic behavior.
- Consensus analysis: Weak consensus for the particle sequences is used to establish weak consensus for the original conditional error covariance sequences.Random permutations connect particle trajectories back to sensor-indexed quantities.
III. MAIN RESULTS
Under the paper’s assumptions, Theorem 10 establishes distributional convergence and stochastic bounds for GIKF error covariances, including weak consensus across sensors. The results also compare random-walk-based estimates with estimates obtained from a uniformly selected sensor and note that the invariant measure is not analytically characterized.
- Riccati-operator analysis: The convergence analysis uses compositions of Riccati operators switched by a Markov chain, with convergence in distribution for arbitrary initial laws independent of that chain.The paper also notes that numerical characterization of µ is possible through repeated process instantiations.
- Weak consensus: Theorem 10 shows that the conditional error covariance at a uniformly randomly selected sensor converges in distribution to an invariant measure µ.The selected-sensor estimate can therefore be used throughout while retaining a stochastically bounded conditional error covariance under weak detectability and connectivity assumptions.
- Weak consensus: For every sensor n, the error-covariance sequence is stochastically dominated by µ in the stated closed-set ordering.The theorem also gives pathwise stochastic domination for the error associated with the corresponding randomly permuted sensor estimate.
- Weak consensus: The error processes at different sensors converge in distribution to the same invariant measure, establishing weak consensus.The convergence concerns the limiting distribution of conditional error covariances and, consequently, the pathwise filtering error.
- Random-walk estimates: Random-walk estimates collected along the graph are asymptotically at least as good as the estimate obtained by probing one uniformly selected node.Whether they are strictly better asymptotically remains unresolved, and the theorem’s upper bound is described as highly conservative.
- Boundedness and scope: Weak detectability, necessary for stochastic boundedness in the centralized setting, is sufficient in the distributed gossip setting for stochastically bounded sensor-estimation errors.The paper states this result irrespective of individual-sensor observability, while noting that it does not analytically characterize the resulting invariant measure µ.
IV. THE AUXILIARY SEQUENCE { ePt}: RDS FORMULATION
The paper reformulates the auxiliary Riccati sequence as a random dynamical system driven by a stationary Markov chain on a two-sided canonical path space. This formulation enables analysis of the sequence’s asymptotic distributional properties.
- Canonical path space: The switching process is represented by a stationary Markov chain on a two-sided canonical path space.The stationary chain has uniform marginal distributions over the network nodes.
- RDS formulation: The auxiliary sequence is analyzed through an RDS formulation on the space of positive semidefinite matrices.The RDS uses random Riccati iterates whose randomness is induced by the switching process.
- Distributional equivalence: The auxiliary sequence is distributionally equivalent to the original non-stationary switching sequence.This lets the paper study the auxiliary stationary formulation while preserving the relevant distributional behavior.
- Canonical path space: Two-sided sequences and the left-shift operator provide the metric dynamical system underlying the RDS.The resulting system is also ergodic.
- RDS construction: The RDS cocycle is constructed to be jointly measurable and continuous in its phase variable through the corresponding Riccati operator.This establishes the regularity required for the RDS analysis.
B. Properties of the RDS (θR, ϕR)
The RDS has order-preserving, conditionally compact, and strongly sublinear properties, leading to a unique equilibrium probability measure. Each auxiliary sequence converges to that same measure from every initial condition, establishing weak consensus.
- RDS properties: The RDS is shown to be conditionally compact, order-preserving, and strongly sublinear.These properties follow from finite dimensionality, Riccati monotonicity, and concavity.
- Equilibrium measure: Under the stated assumptions, a unique equilibrium probability measure exists on the space of positive semidefinite matrices.The equilibrium measure is common to the auxiliary sequences indexed by the sensors.
- Equilibrium measure: The equilibrium measure does not depend on the sensor index or initial state, but depends on network topology and the randomized communication protocol.The theorem therefore yields the same asymptotic measure across sequences despite differing initial conditions.
- Stochastic boundedness: Weak detectability is sufficient in the distributed gossip setting for sensor estimates to have stochastically bounded errors.The result is stated as sufficient under the paper’s assumptions, alongside stochastic boundedness of the GIKF error process.
- Weak consensus: Each error-covariance sequence converges in distribution to the unique invariant measure.The convergence is established for every sensor index under the theorem’s assumptions.
B. Proof of Theorem 10
The proof establishes stochastic boundedness and weak consensus for the GIKF by analyzing interacting Riccati processes under random network switching. It combines stationary approximations, Markov-chain arguments, and weak-convergence results to obtain a unique invariant measure.
- Convergence argument: The proof relates nonstationary switching processes to stationary Markov-chain constructions and uses weak convergence, total-variation bounds, and approximation arguments.Auxiliary processes are compared through finite-state switching sequences and Prohorov-metric estimates.
- Proof strategy: The GIKF models filtering states as interacting stochastic particles and analyzes their conditional error covariances through a random dynamical system.Inter-sensor collaboration occurs through intermittent exchanges, while switching is governed by a network connectivity process.
- Boundedness: Under weak detectability and weak connectivity, each sensor’s estimation error process remains stochastically bounded, regardless of signal-dynamics instability.The boundedness result is established for the error process at each sensor rather than only for a network average.
- Weak consensus: The conditional error covariance at a uniformly randomly selected sensor converges in distribution to a unique invariant measure.The limiting measure is independent of the initial state, yielding the paper’s weak-consensus conclusion.
- Scope boundary: The invariant measure depends on the network communication process, but its sensitivity to perturbations in the communication policy is left for future study.The paper identifies characterizing the mapping from communication dynamics to the invariant measure as difficult.
APPENDIX A RANDOM DYNAMICAL SYSTEMS: FACTS AND RESULTS
The appendix introduces random dynamical systems and the order, compactness, and equilibrium concepts used in the paper’s convergence analysis. It then states a limit-set dichotomy for strongly sublinear, order-preserving systems.
- Random dynamical systems: An RDS consists of a measure-preserving dynamical system and a continuous cocycle that generates random state iterates.The cocycle satisfies identity and composition properties over the base transformations.
- Order and sublinearity: Order-preserving RDSs maintain the partial order on the positive cone under their evolution.Sublinearity and stronger forms impose additional scaling inequalities on the random evolution.
- Equilibria: An equilibrium is a random variable invariant under the cocycle, so its iterates have the same distribution under measure-preserving base transformations.The appendix distinguishes almost equilibria, for which invariance holds outside a null set.
- Asymptotic analysis: Pull-back orbits are introduced because their asymptotic properties are comparatively convenient to establish and imply corresponding forward-orbit distributional results.The equivalence follows from measure preservation of the base transformations.
- Limit-set dichotomy: Conditional compactness controls pull-back orbits through convergence toward random compact sets, supporting the stated limit-set dichotomy.Under the theorem’s assumptions, precisely one alternative applies, including existence of a unique almost equilibrium on a full-measure invariant set.
APPENDIX B PROOFS IN SECTION V
The appendix proves boundedness of Riccati-filtering errors by constructing suboptimal estimators and connecting large covariance events to recurrence of favorable switching cycles. Finite-state Markov-chain recurrence then supplies the asymptotic bound.
- Approximate filtering: The proof first constructs an approximate filter whose error is bounded using a rank condition on an observability Grammian.Kalman-filter optimality transfers the bound from the suboptimal estimator to the optimal filter.
- Riccati contraction: A favorable sequence of Riccati updates contracts covariance iterates into a bounded conic interval independently of their initial value.The argument uses uniform boundedness of Riccati compositions and ergodicity of the switching Markov chain.
- Probability reduction: A large covariance event is bounded by the probability that no favorable switching cycle occurs within a preceding time window.The cycle event implies a covariance bound, producing the event inclusion used in the proof.
- Augmented Markov chain: The proof augments the switching chain with length-ℓ histories, yielding a finite-state Markov chain that inherits irreducibility, aperiodicity, and stationarity.The augmented chain records consecutive switching states and targets a specified favorable cycle.
- Asymptotic boundedness: Positive recurrence makes the probability of avoiding the favorable cycle over an increasingly long window vanish, which establishes asymptotic stochastic boundedness.The conclusion follows using k(J) → ∞ and dominated convergence.