We analyze the performance of a distributed Kalman filter proposed in recent work on distributed dynamical systems. This approach to distributed estimation is novel in that it admits a systematic analysis of its performance as various network quantities su

Ourcentralassumptionisthatthenetworkis“fasterthanthephysicalprocess”,inthesensethatforeachphys-icalupdateindext,thenetworkcarriesoutn>1messageexchangesoneachedge.Theworkin[9]presentsamech-anismformessageexchangeanddecentralizedestimationthatisequivalenttoapurelylocalKalman lterforn=0,andachievestheperformanceoftheglobalKalman lterinthelimitasnbecomeslarge.Thisresultstemsfromtheindependenceofthenoiseprocesses,whichimpliesthatitissuf cienttoperformthespatialfusionbeforethetime-propagation.Itisthussuf cientforeachsensortorunalocalKalman lter,takingasinputstheinstantaneousspa-tialleast-squaresfusionoftheinputmeasurements

1 yt)= LS(Q 1(t)

Q 1

ii(t)yi(t)

i∈V

i∈V

andtheassociatedspatially-fusedcovariance

1Q(t)=

LSQ 1

i(t)

.i∈V

Thedistributed lterproposedin[9]providesamech-anismfortrackingtheaverageoftheinverse-covariance-weightedmeasurements

¯y(t)=1 N

Q 1

i(t)yi(t)i∈V

andthetime-varyingaverage inverse-covariance

Q¯(t)=1

N

Q 1i(t).i∈V

Clearly,thesetwoquantitiesaresuf cienttoreconstruct

yLS(t)bysolvingalinearsystemofequationsateachtimet.Further,knowledgeofthenumberofnodes(available,forexample,fromadistributedminimumspanningtree)allowsoneto ndtheassociatedcovariancesignal.

Thealgorithmrequireseachnodetomaintainavec-torvariablexi(t)∈RmandamatrixvariableMi(t)∈

Rm×m.TheseareallinitializedtoQ 1 1

Thealgorithmrunateachi(0)yi(0)andQnodeisasfollows:

i(0)respectively.foreachtimet

xi←xi+Q 1yi(t) Q 1

i(t)i(t 1)yi(t 1)

Mi←Mi+Q 1t) Q 1

i(i(t 1)fork=1,2,...,n

x←x

ii+γ j∈Ni(xj xi)

M

i←Mi+γj∈Ni(Mj Mi)

endend

Itwasshownin[9]andMitrack¯y

andQ¯thatthisalgorithmmakeseachxi

respectivelyandsoeachnodecanthuslocallycomputeM 1ixiand(NMi) 1,treatingtheseasapproximationstoyLSandQLS.Thealgorithmde-scribedtracks¯y

andQ¯withzeroerrorin“steady-state”1.Thisasymptoticresultholdsforarbitrarynetworkintercon-nectionandforarbitraryn,butthetransientperformanceofthesystemdependsonthenetworktopology,connec-tiondensity,andthenumberofmessagesperunittimen(aproxyforbandwidth).

Theparameterγisastepsize,andmustbechosentoensurestabilityoftheupdatingscheme.Thisissomewhattrickyinthatstabilitycan,inprinciple,dependonthegraphstructureofthenetwork.Anecessaryandsuf cientcon-ditionforstabilityunderarbitraryinterconnectionofthesensorsisγdmax<1,wheredmaxisthemaximumnode-degreeinthenetwork.Thereisa“natural”choice

γ=

1dmax+1

whichhasthepropertythatifeverysensorisconnectedto

everyothersensor,theglobalKalman lterperformanceisrecoveredwithasinglemessageexchangeperunittime,i.e.evenwithn=1.Thus,withγasaboveandcompletein-terconnectionthisschemeisequivalenttothatofRaoandDurrant-Whyte[1].Wewillassumehereafterthatγischo-seninthisway.Thiswillonlyaffecttheconstantsenteringtheexpressionstocome,andnotanyofthequalitativere-sults.

Finally,wewillmakeuseoftheLaplacianmatrixasso-ciatedwiththegraphG.TheLaplacianisde nedasfol-lows:

Lij= 1L if(i,j)∈E,else0ii

=Lij.

j=i

Thisisasymmetricpositive-semi-de nitematrix,andthe

assumptionthatGisconnectedimpliesthatLhasexactlyonezeroeigenvalueandassociatedeigenvector1(thevec-torofallones).Thus,repeatedmultiplicationofavectorby(I γL),whereIistheN×Nidentity,driveseachcomponentofthevectortotheaverageofthecomponentsoftheinitialvector(see[6]).

NotethateachcomponentofthexiandMivariablesisupdatedindependently.Ifforanyonesuchcomponent,weconsideralltheassociatedvaluesacrossthenetworkstacked

1Here

“steady-state”meansthatboththemeasurementsandthecovari-ancematricesapproachalimitast→∞.Forexample,thisassumptionisreasonablewhenestimatingmovingobjectsthatoccasionallyhaltforsigni cantperiodsoftime.