PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs

Soummya Kar, Jose' M. F. Moura

arXiv:1011.1677v1cs.ITmath.OCmath.PR

TL;DR

The paper asks when sparsely connected sensors, each observing only part of a static field, can estimate the full parameter through gossip communication. It develops mixed-time-scale linear estimators and establishes distributed observability and information-rate results. Under suitable unquantized gossip conditions, the distributed estimator can match optimal centralized asymptotic performance, including under fading observations when centralized consistency holds.

  • Problem

    The paper studies how distributed sensors with partial local observations can consistently estimate a large static parameter and achieve centralized convergence rates despite intermittent communication.

  • Method

    The paper analyzes linear estimators that combine gossip-based consensus and local innovation updates on separate gain sequences, together with distributed observability and Fisher information rate notions.

  • Results

    Under global observability and mean connectedness, distributed estimates are consistent and asymptotically normal, and unquantized gossip can attain centralized asymptotic variance.

  • Takeaways & Limitations

    As long as the centralized estimator remains consistent under growing measurement noise, the distributed gossip estimator remains consistent as well.

Abstract

from arXiv · show

The paper considers gossip distributed estimation of a (static) distributed random field (a.k.a., large scale unknown parameter vector) observed by sparsely interconnected sensors, each of which only observes a small fraction of the field. We consider linear distributed estimators whose structure combines the information \emph{flow} among sensors (the \emph{consensus} term resulting from the local gossiping exchange among sensors when they are able to communicate) and the information \emph{gathering} measured by the sensors (the \emph{sensing} or \emph{innovations} term.) This leads to mixed time scale algorithms--one time scale associated with the consensus and the other with the innovations. The paper establishes a distributed observability condition (global observability plus mean connectedness) under which the distributed estimates are consistent and asymptotically normal. We introduce the distributed notion equivalent to the (centralized) Fisher information rate, which is a bound on the mean square error reduction rate of any distributed estimator; we show that under the appropriate modeling and structural network communication conditions (gossip protocol) the distributed gossip estimator attains this distributed Fisher information rate, asymptotically achieving the performance of the optimal centralized estimator. Finally, we study the behavior of the distributed gossip estimator when the measurements fade (noise variance grows) with time; in particular, we consider the maximum rate at which the noise variance can grow and still the distributed estimator being consistent, by showing that, as long as the centralized estimator is consistent, the distributed estimator remains consistent.

I. INTRODUCTION

The paper studies linear gossip estimators for large static fields observed locally by sparsely connected sensors, combining intermittent consensus with local innovations. It characterizes distributed observability and convergence conditions, and compares distributed asymptotic performance with centralized estimation.

  • Motivation: Sensors observe only small field subsets, so global estimation requires local cooperation without a fusion center.Communication is intermittent and may involve random scheduling, link failures, and packet dropouts.
  • Approach: The estimator combines consensus updates from communicated neighbor estimates with innovation updates from new local observations.These two mechanisms operate on different gain sequences, producing mixed time scales.
  • Distributed observability: Global observability and mean connectedness of the time-varying communication graph are sufficient for consistent estimates at every sensor under full cooperation.The condition links sensor observations with the network’s information-dissemination structure.
  • Performance limits: The paper defines a distributed Fisher information rate as a lower bound on the asymptotic variance of distributed schemes.It also investigates distributed estimators that attain this bound.
  • Centralized comparison: Under unquantized, otherwise appropriate gossip conditions, distributed estimators can match the asymptotic variance of optimal centralized linear estimators.With noisy or quantized communication, distributed asymptotic variance is higher than the centralized counterpart.
  • Trade-offs: The mixed-time-scale tuning makes information dissemination dominate uncertainty reduction, but this tuning is unavailable with noisy or quantized transmissions.Consensus noise prevents proper adjustment of the gain sequences.

B. Notation

This section introduces notation for Euclidean spaces, matrices, graph structures, Kronecker products, iteration indices, and parameter estimates.

  • Basic notation: Rk denotes the k-dimensional Euclidean space, while Ik denotes the k × k identity matrix.The vectors 1k and 0k denote the corresponding all-ones and all-zeros vectors.
  • Parameter estimates: Each sensor’s estimate of the unknown parameter θ∗ at time i is denoted xn(i) ∈ RM×1.Initial estimates are assumed non-random for notational simplicity, and random-variable inequalities are interpreted almost surely.
  • Graphs: A graph G = (V, E) contains sensor nodes V and edges E representing inter-sensor connections.The adjacency matrix records edges, and the degree matrix records node degrees.
  • Spectral graph theory: The graph Laplacian’s second eigenvalue λ2(L) is positive for a connected graph and is called algebraic connectivity.This eigenvalue characterizes a network’s connectivity in the reviewed graph-theoretic notation.
  • Kronecker products: Kronecker products extend graph and parameter matrices, so L⊗IM has dimension NM × NM.The paper uses these products for vector-valued sensor parameters.

II. PROBLEM FORMULATION

The paper formulates estimation of a high-dimensional static parameter from noisy local linear observations collected by a time-varying gossip sensor network. It specifies observability, fading-noise, and communication conditions for distributed consistency.

  • Observation model: A network of N sensors estimates an M-dimensional parameter θ∗, while each sensor observes only a small subset of its components.Typically, each sensor observes Mn ≪ M components, so isolated sensors can estimate only part of the parameter.
  • Observation model: The local observations are noise-corrupted linear functions of the parameter, with temporally independent noise that may be spatially correlated.The model allows applications such as distributed target localization.
  • Distributed consistency: Under mean connectedness and appropriate observability conditions, local inter-sensor communication can yield consistent estimates at every sensor.The paper requires global observability and uses average graph connectivity rather than connectivity at every iteration.
  • Fading observations: Fading measurements are modeled by a nondecreasing γ(i), with noise variance growing as γ^2(i) and SNR decreasing as 1/γ^2(i).The constant-SNR case is recovered when γ(i) = 1.
  • Communication network: The communication graph is time varying because links can fail, and link failures may be spatially dependent while independent across time.Individual graph realizations need not be connected; average connectedness is sufficient in the stated framework.

A. Algorithm GLU

GLU is a class of linear distributed recursive estimators that combines consensus and innovation updates using separate gain sequences. The paper analyzes how these gains and model assumptions determine convergence.

  • Mixed time scales: GLU uses different weight sequences for consensus and innovation, creating mixed time-scale behavior.The algorithm class includes choices of α(i) and β(i) that produce different convergence characteristics.
  • Distributed update: At each step, a sensor combines its previous estimate, communicated neighbor estimates, and a new observation.The communication is assumed unquantized in GLU, and the innovation gain includes a general matrix K.
  • Algorithm definition: GLU updates the stacked estimate using a Laplacian consensus term and a gain-weighted innovation term.The compact update is x(i + 1) = x(i) − β(i)(L(i) ⊗ IM)x(i) + α(i)(IN ⊗ K)...
  • Assumptions: The GLU analysis imposes moment and gain-sequence conditions, including a slightly greater-than-quadratic moment for observation noise.The gain matrix K is positive definite and is assumed to commute with G.

B. Centralized linear estimators

The paper restricts comparison to linear centralized estimators and defines a class of “good” estimators through their gain and weight parameters. It establishes parameter conditions for universal consistency and uses this class as the benchmark for GLU.

  • Centralized benchmark: The analysis compares distributed GLU algorithms with linear centralized estimators that have access to all sensor observations.A centralized scheme is modeled as a fusion center receiving all sensor data at every time.
  • Estimator design: A centralized estimator uses a weight sequence parameterized by ac and τc, together with a positive definite gain matrix Kc.Kc is required to commute with the relevant Grammian.
  • Consistency conditions: The admissible consistency range is .5 + γ0 < τc ≤ 1, and this condition is necessary and sufficient for universal consistency from all initial conditions.The paper also states that consistency requires γ0 to be strictly less than .5.
  • Centralized benchmark: The best linear centralized estimator belongs to this class, so GLU is compared against good centralized estimators.The paper states that suitable GLU parameters can match the centralized estimator’s τc, ac, and Kc.

III. SOME INTERMEDIATE RESULTS

This section develops stochastic-recursion tools and characterizes centralized estimators’ consistency and asymptotic variance. It identifies the parameter ranges needed for consistency and the gain achieving the centralized Fisher information rate under Gaussian noise.

  • Recursion tools: The intermediate analysis establishes stochastic-recursion and mixed-time-scale lemmas used in the convergence proofs.The results include pathwise convergence-rate arguments and positivity conditions requiring β(i)/α(i) to diverge.
  • Centralized consistency: For Gaussian observations, a centralized estimator is inconsistent when τc ≤ γ0 + .5 or τc > 1.The lower failure boundary comes from cumulative noise, while τc > 1 makes the updates summable and potentially prevents progress from the initial estimate.
  • Centralized consistency: Under assumptions (A.1), (A.2), and (A.5), good centralized estimators are universally consistent from all initial conditions.Universal consistency is defined as consistency irrespective of the noise distribution, subject to the moment assumption.
  • Asymptotic variance: With γ0 = 0 and τc = 1, the centralized estimator has an asymptotic variance characterized by its gain and weight parameters.The stated result requires ac > N.
  • Asymptotic variance: Choosing Kc = K∗ makes the estimator best linear in asymptotic variance, and under Gaussian noise its variance equals the centralized Fisher information rate.The paper identifies this estimator as optimal centralized under Gaussian observation noise.

IV. MAIN RESULTS

The main theorems show that GLU estimates are consistent whenever centralized linear estimation is consistent and can match centralized asymptotic variance. Mixed time scales make this performance independent of network topology under the stated conditions.

  • Consistency: For 0 ≤ γ0 < .5, every distributed GLU estimator satisfying the assumptions yields consistent estimates at every sensor.This is exactly the fading-parameter range in which a centralized estimator can estimate consistently.
  • Asymptotic variance: A GLU estimator can achieve the same asymptotic variance Sc(K) as a centralized estimator with gain K.The matching construction uses τ1 = τc, a = ac, K = Kc, and a suitable τ2.
  • Topology independence: The allowable fading range and the GLU convergence rate are independent of network topology when the stated random-network connectivity conditions hold.The paper states that any random network satisfying mean connectivity is sufficient.
  • Optimality: With K = K∗ = G^-1, GLU achieves the best linear centralized asymptotic variance at every sensor.Under Gaussian observation noise, the resulting sensor estimators are asymptotically efficient.
  • Topology independence: Mixed time-scale design enables topology-invariant asymptotic variance, unlike the earlier single-time-scale scheme with τ1 = τ2.The consensus and innovation time scales are selected separately through τ1 and τ2.
  • Distributed implementation: GLU requires only sparse local communication at each step while achieving centralized performance asymptotically.The comparison is with centralized transmission of all sensor data to a fusion center.

V. GLU: CONVERGENCE PROPERTIES

The convergence analysis separates sensor disagreement from network-averaged estimation and then relates the averaged process to centralized estimators. The resulting conditions establish centralized convergence-rate inheritance and asymptotic-variance equivalence.

  • Proof technique: The mixed-time-scale analysis does not permit the standard stochastic-averaged estimate sequence to be used directly.A separate lemma is used to relate the averaged process to the centralized estimator.
  • Centralized comparison: The averaged local innovation is not the centralized innovation, so the analysis studies the rate at which the averaged estimator approaches centralized estimators.This comparison is then used to infer convergence of local estimates to θ∗.
  • Main convergence conclusions: Theorems 10 and 11 establish conditions under which local estimates inherit the centralized convergence rate to θ∗.They also establish equivalence between distributed and centralized schemes in asymptotic variance.
  • Pathwise boundedness: The analysis first proves pathwise boundedness of the GLU estimate sequence using supermartingale arguments.A finite random bound is obtained for the relevant Lyapunov process.
  • Network averaging: Lemma 15 characterizes how sensor estimates converge toward a network-averaged estimate, thereby quantifying information flow.The averaged sequence is used as an intermediate object between local estimates and the parameter.
  • Proof technique: The proof requires truncation because pathwise bounds are not uniform over sample paths.The paper introduces componentwise truncation and combines it with convergence-in-probability arguments.

A. Proof of Theorem 10

The proof selects centralized-estimator design parameters satisfying the required assumption, then applies prior propositions and lemmas to establish consistency and the theorem’s remaining assertions.

  • Choosing τc = τ1 and Kc = K makes the centralized estimator’s design parameters good under assumption (A.6).
  • The centralized estimator is consistent by Proposition 7 once its design parameters are good.
  • The first assertion of Theorem 10 follows from equations (123)–(124) and Lemma 16.
  • The second assertion of Theorem 10 follows directly from Lemmas 15 and 16.

B. Proof of Theorem 11

The proof verifies Theorem 11 by selecting τ0 under the hypothesis, comparing distributed and centralized estimators, and choosing K = K∗ for the second assertion.

  • Under Theorem 11’s hypothesis, τ0 can be chosen to satisfy the required condition.
  • With centralized design parameters ac = a and τc = τ1, the comparison estimator is specified for the proof.
  • Because τ0 in (128) exceeds .5, {xn(i)} and {u(i)} are indistinguishable on the relevant scale.
  • The proof invokes standard stochastic-convergence properties after establishing the scale comparison.
  • The second assertion follows by choosing K = K∗ in the first assertion.

VII. CONCLUSIONS

The paper develops gossip linear estimators for sparsely observed large-scale fields, establishes observability and asymptotic performance results, and identifies gain-sequence tradeoffs and communication-noise limits.

  • Motivation: Sensors observe only small fractions of a large-scale random field, so cooperation is required to obtain a global estimate.
  • Estimator structure: The estimator combines neighbor-based consensus updates with local innovations from new measurements.
  • Estimator structure: The two gain sequences create mixed time scales, with consensus decaying more slowly than innovations.
  • Analysis: Because gossip innovations are not martingale differences, the analysis derives pathwise strong approximations to a martingale difference process.
  • Distributed observability: Distributed observability requires global observability of sensing devices together with mean connectedness of the gossip communication network.
  • Performance: Under distributed observability, gossip estimators are consistent and asymptotically normal, with performance approaching optimal centralized estimation.
  • Performance: For conditionally independent observations, distributed estimation achieves the best centralized linear estimator’s asymptotic variance.
  • Fading measurements: The allowable growth rate of observation-noise variance for consistency is the same for centralized and gossip linear estimators.
Loading 1011.1677v1…