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

Determined by distributed calculationof yLS

Local KF outputs

Fig.3.Thesteady-statebehaviorofthedistributed lterisequivalenttoaglobalKalman lterwithapre lteredinput.Theperformanceanalysisofthisisbasedonquantifyinghowclosethepre lteristounity.

Now,wewanttoconsiderthetheerrorsignal

e= x yTLSyTLS...yT

T

LS,

andthetransferfunctionfrom y

toe(z)H e y(z)=H(z) PLSTPLST...PLS

T T

.Notethatthistransferfunctioniszeroatz=1bycon-struction.Furthermore,weknowthatthissystemhasthe

structureofmdecoupledsubsystems(oneforeachcompo-nentofxi).Uptoaconstantmatrixscalingdeterminedbythecovariancematrices,eachsuchsubsystemhastransferfunctionofthefollowingform

G(z)=

1N

11T (1 z 1)(I γL)n I z 1(I γL)n 1

.

Thisfollowsfromtheinner-loopLaplacianupdateopera-tion(1),andthe rst-orderdifferencingoperationinthe

outerloop.WewillfurtherdecomposethesesubsystemsbyexploitingthefactthattheLaplacianisasymmetricmatrix,andadmitsaspectraldecomposition

L=0·11T

+ λiPi

i>1

wherethePitermsareorthogonalprojectionsontomutually

orthogonalsubspacesandtheλitermsarestrictlypositiveeigenvalues(orderedfromsmallesttolargest).Recallthatthe rstterm,correspondingtothenullspaceofL,isknown

aprioribecauseofthestructureoftheLaplacianmatrix.ApplyingthisformulaforLintheaboveequation,weob-tain

(1 γλi)nG(z)=(z 1)

nPi.i>1z (1 γλi)Notethatallofthesetermsarezeroatz=1,inaccordance

withourpreviousstatementregardingHe y(z).

Wehavenowdecomposedtheerrortransferfunction(uptoablock-diagonalmatrixscaling)intoNmindepen-dentsubsystems,eachwithtrivialpole-zerostructure.Specif-ically,theyallshareacommonzeroatz=1,andeachhaveasinglepoleoftheformz=(1 γλi)n.Ourassumptionregardingγimpliesthatthelargestsuchtermis(1 γλ2)n.Thisallowsustoboundtheerrortransferfunctionasfol-lows: H(z) ≤ C(1 γλ)n(z 1)

2 e y z (1 γλ (2)2)n whereCisaconstantdeterminedbythecovariancematri-ces.

5.THEIMPACTOFTHENETWORK:TOPOLOGY,

DENSITY,ANDBANDWIDTHTheboundwehavederivedintheprevioussectionallowsustoquantifytheperformanceofthedistributedestimationschemeasafunctionofthenetworkparametersλ2,γ,andn.Asasimpleveri cationofourclaimthatthedistributedschemereducestoperfectestimationundercompleteinter-connection,wewillmakeuseofthefactthatforacompletegraph

λi=dmax+1foralli>biningthisfact,ourchoiceofγfrombefore,andtheboundfromtheprevioussection,weobtain

He y=0

foralln>1,whichimpliesthattheglobalKalman lter

performanceisachievedwithasinglemessageexchangeoneachlinkperunittime.

Ingeneral,wecanunderstandtheperformanceofthissystembythefollowingquantity:

n λ 1 2 1+d .max Asthisquantitytendstozero,theperformanceofthedis-tributedestimatorapproachesthatofacentralizedKalman

lter.Speci callywecanstudythisquantityasafunctionofthethreefactorsthatarelikelytovaryacrossreal-worldsensornetworks:topology,connectiondensity,andband-width.The rstaspectiscapturedintheeigenvaluesoftheLaplacianmatrix,andinparticularthealgebraicconnec-tivityλ2.Acomprehensiveexplanationofthisquantityis