PaperlayerView exact revision on arXiv

Source-linked AI summary

Consensus+Innovations Distributed Kalman Filter with Optimized Gains

Subhro Das, José M. F. Moura

arXiv:1605.06096v2cs.ITcs.SYeess.SYmath.ITmath.OC

TL;DR

Distributed field estimation is challenging when centralized fusion burdens computation and communication. The paper proposes CIKF, which distributes pseudo-state estimation and optimizes its gains; it reports lower MSE and faster convergence than DIKF, subject to a tracking-capacity condition.

Abstract

from arXiv · show

In this paper, we address the distributed filtering and prediction of time-varying random fields represented by linear time-invariant (LTI) dynamical systems. The field is observed by a sparsely connected network of agents/sensors collaborating among themselves. We develop a Kalman filter type consensus+innovations distributed linear estimator of the dynamic field termed as Consensus+Innovations Kalman Filter. We analyze the convergence properties of this distributed estimator. We prove that the mean-squared error of the estimator asymptotically converges if the degree of instability of the field dynamics is within a pre-specified threshold defined as tracking capacity of the estimator. The tracking capacity is a function of the local observation models and the agent communication network. We design the optimal consensus and innovation gain matrices yielding distributed estimates with minimized mean-squared error. Through numerical evaluations, we show that, the distributed estimator with optimal gains converges faster and with approximately 3dB better mean-squared error performance than previous distributed estimators.

I. INTRODUCTION

The paper introduces a distributed Kalman-filter-style estimator for time-varying random fields, analyzes when its error remains bounded, and designs gains to minimize estimation error. It models the field as an LTI system observed by agents with local measurements and neighbor communication.

I. INTRODUCTION

  • Earlier designs require fast exchanges, local observability, or complete networks; CIKF targets sparse single-timescale sensing and needs only global detectability and connectivity.Its MSE convergence condition requires field-dynamics instability to lie within a tracking capacity determined by local observation models and network connectivity.Source: §I · pp. 1–2
  • 3 dB lower MSE than DIKF, with faster convergence, is reported for CIKF.The introduction also reports that this reduces by half the gap to the centralized optimal Kalman filter.Source: §I · p. 2

II. SYSTEM, OBSERVATION, AND COMMUNICATION

  • The framework combines field dynamics, local observations, and neighbor communication across physical and cyber layers.Agents may communicate with geographically nearest neighbors to reduce communication costs.Source: §II · p. 2, Figure 2 · p. 3

A. Physical layer: dynamical system

  • The physical layer models a spatial temperature field as a site-state vector evolving under LTI coupling dynamics with process noise.The dynamics matrix encodes physical-layer coupling and sparsity.Source: A. Physical layer: dynamical system · pp. 2–3

B. Cyber layer: local observations

  • A network of sensors observes subsets of the field through local measurement models; nonlinear temperature measurements are first-order approximated as linear.Each sensor observes only a few sites, and its observation matrix represents the pattern and strength of its measurements.Source: B. Cyber layer: local observations · p. 3

C. Cyber layer: neighborhood communication

Agents communicate over a sparse, connected cyber network, while the paper’s modeling setup also specifies sparse system components and a centralized estimator for benchmarking. The section introduces the single-time-scale distributed solution.

C. Cyber layer: neighborhood communication

  • The cyber layer is a sparse, time-invariant, connected graph whose agents exchange readings or estimates with neighboring agents.The paper describes geographically nearest-neighbor communication as a way to reduce communication costs.Source: C. Cyber layer: neighborhood… · p. 3

D. Modeling assumptions

  • The large-scale setup assumes sparse dynamics, observation, and network Laplacian matrices, with no deterministic input unless it is known.Each agent communicates with only a few neighbors.Source: D. Modeling assumptions · p. 4

E. Centralized Information filter

  • The centralized benchmark sends all agents’ measurements to a fusion center, which performs the computations.The paper notes that this centralized setup is not practical for the problem studied.Source: E. Centralized Information filter · p. 4

A. Pseudo-state model

The pseudo-state is constructed from summed local pseudo-observations and modeled with its own dynamics and observations. The paper uses it to enable distributed estimation without requiring the observation matrix G to be invertible.

A. Pseudo-state model

  • The centralized information filter aggregates local pseudo-observations into z_i, whose Gx_i component carries state information while the other term is noise.The paper calls the state-bearing quantity the pseudo-state and describes it as a noise-reduced version of the summed pseudo-observations.Source: A. Pseudo-state model · pp. 4–5
  • The pseudo-state has a discrete-time linear state-space model, with local pseudo-observations serving as its measurements.The paper develops a distributed estimator to produce unbiased pseudo-state and state estimates with minimized mean-squared error.Source: A. Pseudo-state model · pp. 4–5
  • CIKF relaxes the DIKF requirement that G be invertible, allowing general dynamics-observation models under global detectability.The paper notes that the associated matrix eI is low-rank in most cases.Source: A. Pseudo-state model · p. 5
  • Sharing distributed pseudo-state estimates yields 3 dB better MSE performance than DIKF, which shares summed pseudo-observations.The paper attributes the pseudo-state to a noise-reduced version of the sum of pseudo-observations.Source: A. Pseudo-state model · p. 5

B. Consensus+Innovations Kalman Filter (CIKF)

CIKF uses agents’ local pseudo-observations and neighboring pseudo-state estimates to form distributed filtered and predicted estimates. Its deterministic gains can be precomputed, and the resulting updates provide minimized-MSE distributed estimates.

B. Consensus+Innovations Kalman Filter (CIKF)

  • Each agent combines its own current pseudo-observation with prior pseudo-state estimates received from its neighbors to update its pseudo-state estimate.The state estimate is conditioned on the current pseudo-state estimate.Source: B. Consensus+Innovations Kalman Filter… · p. 5
  • The distributed field estimate is optimal given the available pseudo-state estimates, but not given all observations.The corresponding prediction estimates use quantities available up to the previous time step.Source: B. Consensus+Innovations Kalman Filter… · p. 5
  • CIKF uses deterministic consensus and innovation gains that can be precomputed and saved at each agent.With these gains, its filter and prediction updates provide minimized-MSE distributed state estimates.Source: B. Consensus+Innovations Kalman Filter… · p. 5

C. CIKF: Assumptions

CIKF’s stated convergence assumptions are global detectability and a connected communication network, without requiring distributed observability. The section then outlines local updates and develops unbiased error and covariance recursions.

C. CIKF: Assumptions

  • CIKF assumes global detectability and a connected communication network, but does not require distributed observability.The model need not be locally detectable at every agent; the paper characterizes these as minimal assumptions.Source: C. CIKF: Assumptions · p. 6

D. CIKF: Update algorithm

  • Each agent runs Algorithm 1 locally, using model parameters and precomputed gains to process observations and perform filter and prediction updates.The update procedure receives neighboring pseudo-state estimates and transforms local observations into pseudo-observations.Source: D. CIKF: Update algorithm · p. 6

IV. ERROR ANALYSIS

  • CIKF’s state and pseudo-state estimates are unbiased, and their filter and prediction error covariances follow Lyapunov-type iterations.The trace of the state prediction error covariance is the MSE measure; convergence analysis establishes when it is bounded.Source: §IV · pp. 6–7

V. TRACKING CAPACITY

CIKF convergence is governed by the stability of its prediction-error processes: stable error dynamics and bounded noise covariances yield bounded error covariances.

V. TRACKING CAPACITY

  • Asymptotically stable prediction-error dynamics also imply asymptotic stability of the filter-error processes.The analysis therefore studies prediction-error processes.Source: §V · p. 7

A. Asymptotic stability of error processes

  • The error-process noises are zero-mean Gaussian sequences.Their distributions and covariances are specified in Lemma 3.Source: A. Asymptotic stability of error… · p. 7
  • The prediction-error processes are asymptotically stable if and only if both error-dynamics spectral radii are below one and their noise covariances are bounded.These conditions are necessary and sufficient for CIKF convergence.Source: A. Asymptotic stability of error… · p. 7

B. Tracking capacity for unstable systems

The CIKF tracking capacity bounds the instability of systems it can track with bounded MSE and depends on communication and observation structure. The optimal-gain design builds on transforming correlated updates into uncorrelated new information.

B. Tracking capacity for unstable systems

  • If the system dynamics satisfy ∥A∥2 < C, suitable consensus and innovation gains yield CIKF convergence with bounded MSE.For stable systems, gains satisfying the convergence conditions always exist; for unstable systems, the tracking capacity sets an upper threshold.Source: B. Tracking capacity for unstable… · pp. 7–8
  • The tracking capacity depends on both network connectivity and local observation models, and increases with communication connectivity and observation density.It is infinite for a complete communication graph or when every agent observes the entire system.Source: B. Tracking capacity for unstable… · p. 8

A. New uncorrelated information

  • The CIKF transforms new information correlated with prior estimates into uncorrelated information before combining it with those estimates for current filtering.The new information consists of linear combinations of Gaussian sequences and is itself Gaussian.Source: A. New uncorrelated information · p. 8

B. Consensus and innovation gains

The CIKF uses designed consensus and innovation gains to minimize distributed estimate MSE. Its deterministic gains can be computed offline for online use.

B. Consensus and innovation gains

  • The design computes intermediate matrices and uses them to obtain the optimal consensus and innovation gains.The resulting gains provide distributed minimized-MSE field estimates.Source: B. Consensus and innovation gains · p. 9
  • The gain matrix combines blocks associated with an agent and its neighbors, while the innovation gain is block diagonal.The consensus-gain structure follows the graph Laplacian's block pattern.Source: B. Consensus and innovation gains · p. 9
  • The proposed gain design produces minimized-MSE distributed estimates by applying the Gauss-Markov theorem to the consensus and innovation gains.The gains are deterministic and can be precomputed offline for online implementation.Source: B. Consensus and innovation gains · p. 9
  • The offline gain-design algorithm and online filtering algorithm together provide minimized-MSE estimates at each agent.The method does not require A, H_n, or L to be sparse, although sparsity can reduce computation and storage costs.Source: B. Consensus and innovation gains · p. 9

VII. NUMERICAL EVALUATION

The numerical evaluation compares CIKF with centralized CKF and distributed DIKF under an unstable field model and sparse sensing and communication. CIKF converges faster than DIKF and improves its MSE by 3 dB, while remaining 3 dB above CKF.

VII. NUMERICAL EVALUATION

  • The study computes theoretical CIKF MSE from error-covariance traces and uses Monte Carlo simulations to evaluate CIKF, DIKF, and CKF.The gain matrices and theoretical CIKF error covariances are computed before the simulated estimators are compared.Source: §VII · p. 9, B. Optimized gains and theoretical MSE · p. 10

A. Model specifications

  • The evaluation uses a 50-site field monitored by 50 agents, each observing two sites, with unstable dynamics satisfying ∥A∥2 = 1.05.The connected communication graph has 50 nodes and 138 edges; individual agents' observation pairs are not detectable, while the overall pair is detectable.Source: A. Model specifications · pp. 9–10

B. Optimized gains and theoretical MSE

  • 3 dB lower MSE than DIKF and 3 dB higher MSE than CKF; CIKF also converges faster than DIKF.The reported MSE gap to CKF is attributed to its access to all sensors' observations, unlike CIKF's local observations and delayed neighbor information.Source: B. Optimized gains and theoretical MSE · p. 10, Figure 4 · p. 11, Figure 4b

VIII. CONCLUSIONS

  • CIKF provides unbiased distributed estimates with bounded and minimized MSE, and its gains yield about 3 dB better performance than DIKF.The conclusion also states that CIKF does not require DIKF's strict distributed observability assumption.Source: §VIII · p. 10, Figure 4b
  • Gauss-Markov optimized gains give the CIKF's dynamic averaging step lower MSE than DIKF's.The paper identifies pseudo-state use as central to this distributed field-estimation approach.Source: §VIII · p. 11

APPENDIX

The appendix supplies proofs for the paper’s propositions, lemmas, and theorems.

A. Proof of Proposition 1

  • The proof derives the pseudo-state dynamics and pseudo-observation relations used in the filter.The pseudo-state dynamics are obtained from equations (8) and (1), and the pseudo-observations from (4) and (2).Source: A. Proof of Proposition 1 · p. 11

B. Proof of Lemma 1

  • Expected filtering and prediction errors are used to establish the error relations in Lemma 1.The proof takes expectations of the filtering error definitions and the prediction errors.Source: B. Proof of Lemma 1 · p. 11

C. Proof of Lemma 2

  • Vector forms of the pseudo-state and state updates are expanded into filtering and prediction error dynamics.The proof also uses Gaussian state, pseudo-state, initial-condition, and noise assumptions to establish Gaussian errors.Source: C. Proof of Lemma 2 · pp. 11–12

D. Proof of Lemma 3

  • The proof uses Gaussian error processes and zero-mean noises to derive relations involving the error terms and matrices F1, F2, and F3.Those matrices are defined in equations (64)–(66).Source: D. Proof of Lemma 3 · p. 12

E. Proof of Lemma 4

The appendix proves the uncorrelated-innovations property and derives the consensus+innovations filter and prediction updates.

E. Proof of Lemma 4

  • The new uncorrelated information vectors are shown to be zero-mean Gaussian and uncorrelated across time.The proof expresses them using filtering and prediction errors and notes its similarity to Lemma 5 in, with conditioning on the pseudo-observations.Source: E. Proof of Lemma 4 · p. 12

F. Proof of Theorem 1

  • The Innovations Property gives a one-to-one correspondence between pseudo-observations and observations, supporting the consensus+innovations filtering update.The proof combines gain blocks with corresponding agent estimates and also gives the pseudo-state and state prediction updates.Source: F. Proof of Theorem 1 · pp. 12–13
  • The appendix states the pseudo-state and state prediction updates as part of the filter construction.The update equations are identified in the proof of Theorem 1.Source: F. Proof of Theorem 1 · p. 13

G. Proof of Theorem 2

The appendix derives covariance recursions, establishes a sufficient condition for bounded-MSE convergence, and identifies gains that minimize MSE.

G. Proof of Theorem 2

  • The filter and predictor error covariances follow Lyapunov-type iterations derived from the error definitions and dynamics.The proof states that the error processes are zero-mean Gaussian.Source: G. Proof of Theorem 2 · p. 13

H. Proof of Theorem 3

  • If ∥A∥2 < C, the CIKF converges with bounded MSE, given global detectability and bounded error-noise covariances.The proof obtains this conclusion from the stability condition ρ(eF) < 1 and the covariance relations in (48)–(49).Source: H. Proof of Theorem 3 · p. 13

I. Proof of Theorem 4

  • The optimal gains yield minimized-MSE estimates of the pseudo-state and field at each agent.The proof characterizes the gains using the Innovations Property and Gauss-Markov principle.Source: §I · p. 13
Loading 1605.06096v2…