# Consensus analysis of random sub-graphs for distributed filtering with link
failures

Stefano Battilotti, Filippo Cacace, Massimiliano d’Angelo S. Battilotti is
with the Dipartimento Ingegneria Informatica, Automatica e Gestionale (DIAG)
”A. Ruberti”, Sapienza Università di Roma, Via Ariosto 25, 00185, Rome, Italy
(e-mail: battilotti@diag.uniroma1.it).F. Cacace, is with Università Campus
Bio-Medico di Roma, Rome, Italy (e-mail: f.cacace@ieee.org).M. d’Angelo is
with the Dipartimento Ingegneria Informatica, Automatica e Gestionale (DIAG)
”A. Ruberti”, Sapienza Università di Roma, Via Ariosto 25, 00185, Rome, Italy
(e-mail: mdangelo@diag.uniroma1.it).

###### Abstract

In this paper we carry out a stability analysis of a distributed consensus
algorithm in presence of link failures. The algorithm combines a new broadcast
version of a Push-Sum algorithm, specifically designed for handling link
failures, with a new recursive consensus filter. The analysis is based on the
properties of random Laplacian matrices and random sub-graphs and it may also
be relevant for other distributed estimation problems. We characterize the
convergence speed, the minimum number of consensus steps needed and the impact
of link failures and for both the broadcast Push-Sum and the recursive
consensus algorithms. Numerical simulations validate the theoretical analysis.

Keywords: Filtering, Network analysis, Stochastic systems, random graphs.

##  1 Introduction

Distributed estimation is based on the usage of multiple sensor nodes to
cooperatively perform large-scale sensing tasks that cannot be accomplished by
individual devices. The availability of low-cost sensors and the diffusion of
wireless networks has contributed in recent years to the development of many
applications based on distributed estimation and filtering, and this area has
become one of the most active topics in filtering theory [10, 13, 3].
Distributed filtering algorithms dictate the way in which the information is
exchanged and elaborated by the nodes of the network in order to reach a
shared estimate of the target systems state under the constraint that each
node can communicate only with its neighbors, in a broad range of different
settings related to the kind of systems (continuous-time or discrete-time,
linear or non-linear) and communications pattern (bi-directional or uni-
directional, broadcast or asynchronous, static or dynamic networks). In this
paper we are concerned with stochastic linear time-invariant systems at
discrete-time on bi-directional links, represented by an undirected graph,
when the links are affected by random and symmetric link failures.

Most of the existing approaches to distributed filtering belong to the
consensus-based paradigm and can be broadly categorized into three groups
[13]: state estimate fusion [23, 24, 28, 29, 34], measurement vector fusion
[11, 17, 19, 22, 30, 33], and information vector fusion [5, 16, 27, 31, 32].
Hybrid approaches have also been proposed [6]. Diffusion-based filters [7]
descend from diffusion adaptation strategies [25] but they share a structure
similar to consensus-based filters. In the discrete-time setting most of these
approaches are based on multiple consensus steps among neighbors per unit of
time, in order to preserve stability of the estimation error and overcome the
problem of non-local observability. A numerical comparison among some of these
methods is reported in [2]. An interesting practical conclusion is that none
of the existing methods ensures acceptable estimation accuracy, for arbitrary
networks and systems, when too few consensus steps per time unit are used.

Many recent works consider the distributed estimation problem in presence of
link failures [10]. Two distinct settings can be considered, since failures
can be either known or unknown to the nodes, _i.e._ the node may either be
aware that the message from one of its neighbors got lost or not. The recent
paper [15] proposes distinct filters for the two cases. We focus on the first
case, for the second case see [1, 15] and the references therein. The setting
that we consider is identical to the one in [20]. In that proposal the error
covariance does not converge to the centralized Kalman Filter, the error is
not mean square bounded but only stochastically bounded and the lower bound on
the number of consensus steps is not provided. Analogue limitations affect
[15] for the sub-optimal SDKF as the lower bound on the consensus step cannot
be characterized. An approach based on state estimate fusion with one
consensus step is [9], where sector-bounded nonlinear systems and directed
graphs are considered in the $H_{\infty}$ framework. The setting is more
general and the results correspondingly weaker: the $H_{\infty}$ properties of
the filter are difficult to compute in a distributed way. Analogue issues
arise for the distributed Extended Kalman Filter in [36]. The recent paper
[35] extends the approach in [5] to the case of unknown inputs, random link
failures and time-varying systems. The main problems in this case are the high
communication overhead, the performance with few consensus steps and the
problem of verifying the convergence conditions in a distributed environment.

In this paper we propose and analyze an extension of the DKF algorithm of [2]
in presence of link failures. DKF makes use of two separate consensus
algorithms. The first one aims at reaching consensus on the overall sensing
capability of the network, the second one is a consensus algorithm for the
recursive estimation phase. The use of two separate algorithms allows to
reduce the communication burden without losing the convergence to the
centralized filter as the number of consensus steps grows. A feature of DKF in
[2] is that it is possible to compute at each node the minimum number of
consensus steps that yields mean square boundedness of the estimation error.
We aim at extending these properties in presence of random link failures and
at characterizing the convergence speed, the lower bound on the number of
consensus steps and the impact of link failures. The second contribution is to
propose a modification of the broadcast Push-Sum algorithm to the case of link
failures.

The problem is formally defined in Section 2. The distributed filtering
algorithm is presented in Section 3 and a separate stability analysis for the
two parts of the algorithm is provided in Section 4. The example in Section 5
is used to validate the theoretical results. Additional results for this
analysis are available in the appendices.

#### Notation and preliminaries

$\mathbb{N}$, $\mathbb{R}$ and $\mathbb{C}$ denote respectively natural, real
and complex numbers. $|S|$ is the cardinality of set $S$. For a square matrix
$A$, $\textnormal{tr}(A)$ is the trace, $\sigma(A)$ is the spectrum and
$\rho(A)$ is the spectral radius. $A$ is said to be Schur stable if
$\rho(A)<1$. $\|A\|$ denotes the matrix operator norm. $\mathbb{E}\\{\cdot\\}$
denotes expectation. $\otimes$ is the Kronecker product between vectors or
matrices, and $M^{[n]}=M\otimes M^{[n-1]}$ with $M^{[0]}=I$ the Kronecker
power. The operators $\textnormal{row}_{i}()$, $\textnormal{col}_{i}()$,
$\textnormal{diag}_{i}()$ denote respectively the horizontal, vertical and
diagonal compositions of matrices and vectors indexed by $i$.
$\textnormal{stack}(M)\in\mathbb{R}^{nm\times 1}$ denotes the stack of the
matrix $M\in\mathbb{R}^{n\times m}$. $I_{n}$ is the identity matrix in
$\mathbb{R}^{n}$, $1_{N}\in\mathbb{R}^{N}$ is a vector with all entries $1$
and $U_{N}=1_{N}1_{N}^{\top}$ is the square matrix of size $N$ having $1$ in
each entry. A random sequence $\\{X_{t}(\omega)\\}$ is asymptotically unbiased
if $\lim_{t\to\infty}\mathbb{E}[X_{t}]=0$, while it is mean square bounded if
$\sup_{t\geq 0}\mathbb{E}[\|X_{t}\|^{2}]<+\infty$.

##  2 Problem statement and assumptions

On an undirected network connecting $N$ nodes we study the distributed
recursive estimation problem of the process

$\displaystyle{\bf{x}}_{t+1}=$ $\displaystyle A{\bf{x}}_{t}+{\bf{f}}_{t},$ (1)
$\displaystyle{\bf{y}}^{(i)}_{t}=$ $\displaystyle
C_{i}{\bf{x}}_{t}+{\bf{g}}^{(i)}_{t},\quad i=1,\,\dots,\,N,$ (2)

where ${\bf{x}}_{t}\in\mathbb{R}^{n}$,
${\bf{y}}^{(i)}_{t}\in{\mathbb{R}^{q_{i}}}$, $q_{i}\geq 0$, is the output
available at the node $i\in\\{1,2\dots,N\\}$, ${\bf{f}}_{t}$ and
${\bf{g}}^{(i)}_{t}$, $i=1,\,\dots,\,N$, are zero-mean white noises, mutually
independent with covariance respectively $Q$ and $R_{i}$, $i=1,\ldots,N$. The
matrix $R=\textnormal{diag}_{i}(R_{i})$ is non-singular. ${\bf{x}}_{0}$ is a
random variable with mean
${\widebar{{\bf{x}}}_{0}}:=\mathbb{E}\\{{\bf{x}}_{0}\\}$ and covariance
$\Psi_{0}$. We denote ${\bf{y}}_{t}=\textnormal{col}_{i}({\bf{y}}^{(i)}_{t})$
and $C=\textnormal{col}_{i}(C_{i})$ is the aggregate matrix of the output
maps. When $q_{i}=0$ the node does not have sensing capabilities. In order to
obtain an estimate of ${\bf{x}}_{t}$ at each node it is therefore necessary to
exchange information among neighboring nodes. We consider the problem of
designing a distributed state estimator for (1)–(2) consisting of $N$ local
estimators, one for each node, that exchange local information with the
neighbors in presence of possible communication failures.

The information exchange between the nodes is modeled by the undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ where the vertices
$\mathcal{V}=\\{1,2\dots,N\\}$ represent the $N$ nodes and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges of the
graph. The presence of an edge $(i,j)$ in ${\mathcal{G}}$ implies that nodes
$i$ and $j$ can exchange information between them. The graph is undirected,
that is, the edges $(i,j)$ and $(j,i)\in\mathcal{E}$ are considered to be the
same. Two nodes $i$ and $j$, with $i\neq j$, are neighbors to each other if
$(i,j)\in\mathcal{E}$. The set of neighbors of node $i$ is
$\mathcal{N}^{(i)}:=\\{j\in\mathcal{V}:(j,i)\in\mathcal{E}\\}$,
$\nu^{(i)}=|\mathcal{N}^{(i)}|$ its cardinality,
$\overline{\mathcal{N}}^{(i)}=\\{i\\}\cup\mathcal{N}^{(i)}$ is the set set of
neighbors including $i$ itself with $\bar{\nu}^{(i)}=\nu^{(i)}+1$. A path is a
sequence of connected edges in a graph. A graph is connected if there is a
path between every pair of vertices. The adjacency matrix
$\mathcal{A}\in\mathbb{R}^{N\times N}$ of ${\mathcal{G}}$ has the $(i,j)$-th
entry $1$ if $(i,j)\in\mathcal{E}$ and $0$ otherwise. The degree matrix
$\mathcal{D}=\textnormal{diag}_{i=1}^{N}(\nu^{(i)})$ of $\mathcal{G}$ is a
diagonal matrix whose $i$-th entry is $\nu^{(i)}$. The Laplacian of an
undirected ${\mathcal{G}}$ is the symmetric matrix
$\bar{\mathcal{L}}\in\mathbb{R}^{N\times N}$ defined by
$\bar{\mathcal{L}}=-\mathcal{A}+\mathcal{D}$. When the graph is connected,
$0=\lambda_{1}(\bar{\mathcal{L}})<\lambda_{2}(\bar{\mathcal{L}})\leq\cdots\leq\lambda_{N}(\bar{\mathcal{L}})$,
where $\lambda_{i}(\bar{\mathcal{L}})$ denotes an eigenvalue of
$\bar{\mathcal{L}}$. An eigenvector associated to
$\lambda_{1}(\bar{\mathcal{L}})$ is $\mathbf{1}_{N}$.

###### Assumption 1

The graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is connected.

###### Assumption 2

The couple $(C,A)$ is observable and the couple $(A,Q^{\frac{1}{2}})$ is
controllable.

Assumption 2 ensures that the variance of the estimation error of the
centralized filter is bounded. The presence of failures is modeled by the
Bernoulli stochastic processes $\beta_{t}^{(ij)}(\omega)\in\\{0,\,1\\}$, where
$t$ is the discrete time index. In particular, when
$\beta_{t}^{(ij)}(\omega)=1$ node $i$ and $j$ can communicate at time $t$,
while the contrary happens when $\beta_{t}^{(ij)}(\omega)=0$. We assume that
these variables have uniform probability
$P(\beta_{t}^{(ij)}(\omega)=1)=p_{\beta}$ and that they are temporally
independent and independent from noise ${\bf{f}}_{t}$, ${\bf{g}}^{(i)}_{t}$.
We set $\beta_{t}^{(ii)}(\omega)=1$, since node $i$ has its own measurement,
and we assume that the link failures are symmetric, _i.e._ if at time $t$ node
$i$ does not receive a message from node $j$, the same happens to node $j$
with respect to node $i$. We also define the process
$\beta_{t,h}^{(ij)}(\omega)$, with $h\in\mathbb{N}$ and the same properties as
$\beta_{t}^{(ij)}(\omega)$, to model losses the consensus step iterations. Let
$\nu^{(i)}_{t}(\omega)=\sum_{j\in\mathcal{N}^{(i)}}\beta_{t}^{(ij)}(\omega)$
be the number of neighbors at time $t$ in presence of link failures and
$\bar{\nu}^{(i)}_{t}(\omega)=\nu^{(i)}_{t}(\omega)+1$. Finally, we introduce
the disconnection probability $p_{d}$, which is the probability, constant in
time, that the network is disconnected at time $t$ due to link failures.
$p_{d}$ depends on $p_{\beta}$ but also on the the network topology We
summarize these properties in the following assumption.

###### Assumption 3

The disconnection probability is less than $1$, $p_{d}<1$. For all
$i,j\in\mathcal{V}$, $t\geq 0$, $h\geq 0$, $\beta_{t}^{(ij)}$,
$\beta_{t,h}^{(ij)}$, ${\bf{f}}_{t}$, ${\bf{g}}^{(i)}_{t}$ are mutually
independent. Moreover, for $i\neq j$, the sequences $\beta_{t}^{(ij)}(\omega)$
and $\beta_{t,h}^{(ij)}(\omega)$ are identically distributed Bernoulli
sequences with mean $p_{\beta}<1$, and
$\beta_{t}^{(ij)}(\omega)=\beta_{t}^{(ji)}(\omega)$ and
$\beta_{t,h}^{(ij)}(\omega)=\beta_{t,h}^{(ji)}(\omega)$, while
$\beta_{t}^{(ii)}(\omega)\equiv 1$.

##  3 Distributed Kalman Filter with link failures

The proposed algorithm, shown in Fig. 1, is an extension of the Distributed
Kalman filter in [2] (DKF) where we integrate the distributed algorithm for
the estimation of the gain and the link failures. The initial estimate and
covariance of error at node $i$, $\widehat{\bf{x}}_{0}^{(i)}$ and
$\Psi^{(i)}_{0}$, are chosen as ${\bf{x}}_{0}$ and $\Psi_{0}$ when the values
are available. $\varepsilon$ is an arbitrarily small positive real. The
algorithm has two parameters, the consensus gain $\delta\in\mathbb{R}$ and the
number of consensus iterations $\gamma\in\mathbb{N}$. In detail:

Algorithm DKF with link failures, node $i$

  1. 1:

Set stop=false, $\widehat{\bf{x}}^{(i)}_{0|0}=\widehat{\bf{x}}_{0}^{(i)}$,
$P^{(i)}_{0}=\Psi^{(i)}_{0}$,
$\tilde{C}^{(i)}_{0}=C_{i}^{\top}R_{i}^{-1}C_{i}$, $\tilde{n}^{(i)}_{0}=1$,
$w^{(i)}_{0}=0$ except for $w^{(1)}_{0}=1$ and
$\bar{\nu}^{(i)}=|\overline{\mathcal{N}}^{(i)}|$.

  2. 2:

At time $t\geq 0$, if stop then go to Step 3, otherwise execute:

    1. 2.1:

Send $\frac{\tilde{C}^{(i)}_{t}}{\bar{\nu}^{(i)}}$,
$\frac{\tilde{n}^{(i)}_{t}}{\bar{\nu}^{(i)}}$,
$\frac{w^{(i)}_{t}}{\bar{\nu}^{(i)}}$ to the neighbors.

    2. 2.2:

Compute

$\displaystyle\hskip-28.45274pt\tilde{C}^{(i)}_{t+1}=\frac{\tilde{C}^{(i)}_{t}}{\bar{\nu}^{(i)}}$
$\displaystyle+\sum_{j\in\mathcal{N}^{(i)}}\beta_{t}^{(ij)}\frac{\tilde{C}^{(j)}_{t}}{\bar{\nu}^{(j)}}+(1-{\beta}_{t}^{(ij)})\frac{\tilde{C}^{(i)}_{t}}{\bar{\nu}^{(i)}}$
(3)
$\displaystyle\hskip-28.45274pt\tilde{n}^{(i)}_{t+1}=\frac{\tilde{n}^{(i)}_{t}}{\bar{\nu}^{(i)}}$
$\displaystyle+\sum_{j\in\mathcal{N}^{(i)}}\beta_{t}^{(ij)}\frac{\tilde{n}^{(j)}_{t}}{\bar{\nu}^{(j)}}+(1-{\beta}_{t}^{(ij)})\frac{\tilde{n}^{(i)}_{t}}{\bar{\nu}^{(i)}}$
(4)
$\displaystyle\hskip-28.45274ptw^{(i)}_{t+1}=\frac{w^{(i)}_{t}}{\bar{\nu}^{(i)}}$
$\displaystyle+\beta_{t}^{(ij)}\frac{w^{(j)}_{t}}{\bar{\nu}^{(j)}}+\sum_{j\in\mathcal{N}^{(i)}}(1-{\beta}_{t}^{(ij)})\frac{w^{(i)}_{t}}{\bar{\nu}^{(i)}}$
(5) $\displaystyle\hskip-28.45274pt(G^{(i)}_{t+1},\,N^{(i)}_{t+1})$
$\displaystyle=\begin{cases}\left(\frac{\tilde{C}^{(i)}_{t+1}}{w^{(i)}_{t+1}},\,\frac{\tilde{n}^{(i)}_{t+1}}{w^{(i)}_{t+1}}\right),\
\textnormal{if }w^{(i)}_{t+1}\neq 0,\\\ (C_{i}^{\top}R_{i}^{-1}C_{i},\,1)\
\textnormal{otherwise}.\end{cases}$ (6)

    3. 2.3:

If $\|\tilde{C}^{(i)}_{t+1}\|>0$ and
$\|\tilde{C}^{(i)}_{t+1}-\tilde{C}^{(i)}_{t}\|<\varepsilon$ then set
stop=true.

  3. 3:

Compute

$\displaystyle P^{(i)}_{t+1}=$
$\displaystyle(AP^{(i)}_{t}A^{\top}+Q)(I_{n}+G^{(i)}_{t+1}(AP^{(i)}_{t}A^{\top}+Q))^{-1}$
(7) $\displaystyle K^{(i)}_{t+1}=$
$\displaystyle\begin{cases}N^{(i)}_{t+1}P^{(i)}_{t+1}C_{i}^{\top}R_{i}^{-1}\
\textnormal{if }C_{i}\neq 0,\\\ 0\ \textnormal{otherwise}.\end{cases}$ (8)

  4. 4:

Get ${\bf{y}}^{(i)}_{t+1}$ and compute

${\bf{z}}^{(i)}_{t+1,0}=A\widehat{\bf{x}}^{(i)}_{t|t}+K^{(i)}_{t+1}({\bf{y}}^{(i)}_{t+1}-C_{i}A\widehat{\bf{x}}^{(i)}_{t|t}).$

  5. 5:

For $h=0,\ldots,\gamma-1$ do

    1. 5.1.

Send ${\bf{z}}^{(i)}_{t+1,h}$ to the neighbors

    2. 5.2.

Compute

$\displaystyle{\bf{z}}^{(i)}_{t+1,h+1}={\bf{z}}^{(i)}_{t+1,h}$
$\displaystyle+\frac{1}{\delta}\sum_{j\in\mathcal{N}^{(i)}}\beta^{(ij)}_{t,h}({\bf{z}}^{(j)}_{t+1,h}-{\bf{z}}^{(i)}_{t+1,h})$
(9)

  6. 6.

Set $\widehat{\bf{x}}^{(i)}_{t+1|t+1}={\bf{z}}^{(i)}_{t+1,\gamma}$ and go to
Step 2.

Figure 1: Distributed Kalman Filter (DKF) with link failures.

  * •

Step 2 is a modification of the Push-Sum algorithm [2, 18] in presence of link
failures (see Remark 1). We shall prove that

$\displaystyle\frac{\lim_{t\to\infty}\tilde{C}^{(i)}_{t}}{\lim_{t\to\infty}w^{(i)}_{t}}=$
$\displaystyle G=\sum_{i=1}^{N}C_{i}^{\top}R_{i}^{-1}C_{i}$ (10)
$\displaystyle\frac{\lim_{t\to\infty}\tilde{n}^{(i)}_{t}}{\lim_{t\to\infty}w^{(i)}_{t}}=$
$\displaystyle N$ (11)

and consequently $G^{(i)}_{t}\to\sum_{i=1}^{N}C_{i}R_{i}^{-1}C_{i}$,
$N^{(i)}_{t}\to N$.

  * •

Eqs. (7)–(8) compute the filter gain. Considering the asymptotic values of
$G^{(i)}$, $N^{(i)}$ given above it is easy to check that $K^{(i)}_{t}\to
NP_{\infty}C_{i}^{\top}R_{i}^{-1}$, where $P_{\infty}$ is the solution of the
Riccati equation for the centralized Kalman filter (_i.e._ the Kalman filter
with all $\bf{y}_{t}$ available),

$\displaystyle P_{\infty}$
$\displaystyle=(I_{n}-K_{\infty}C)(AP_{\infty}A^{\top}+Q)(I_{n}-K_{\infty}C)^{\top}$
$\displaystyle\quad+P_{\infty}C^{\top}R^{-1}CP_{\infty},$ (12) $\displaystyle
K_{\infty}$ $\displaystyle=P_{\infty}C^{\top}R^{-1}.$ (13)

  * •

Steps 4 and 5 compute the local state estimate. Steps 4 implements a local
prediction and correction step with the locally available measurements. Step 5
is a dynamic averaging in $\gamma$ steps with gain $\delta$ on the estimates.

###### Remark 1

The original Push-Sum algorithm [18] is a gossip-based protocol to compute
aggregate functions over static networks. Broadcast versions, more suited to
networks of dynamical agents, have been proposed in [2] and [26]. The
Broadcast Push-Sum algorithm computes $\sum_{i=1}^{N}x^{(i)}$ as
$y^{(i)}_{0}=x^{(i)}$, $w_{0}^{(i)}=0$, $w_{0}^{(1)}=1$,

$\displaystyle
y^{(i)}_{t+1}=\frac{y^{(i)}_{t}}{\bar{\nu}^{(i)}}+\sum_{j\in\mathcal{N}^{(i)}}\frac{y^{(j)}_{t}}{\bar{\nu}^{(j)}},\quad
w^{(i)}_{t+1}=\frac{w^{(i)}_{t}}{\bar{\nu}^{(i)}}+\sum_{j\in\mathcal{N}^{(i)}}\frac{w^{(j)}_{t}}{\bar{\nu}^{(j)}}.$
(14)

$w^{(i)}_{t}$ is a positive scalar weight. In [2] it is proved that
$y^{(i)}_{t}/w^{(i)}_{t}$ converges to $\sum_{i=1}^{N}x^{(i)}$. The algorithm
used here is a new version to deal with link failures. In both the gossip and
broadcast versions each node receives from its neighbors the consensus data
divided by the number of its neighbors. This cannot be done in a synchronized
way because, due to failures, the nodes do not know the instantaneous number
of neighbors when transmitting. The new algorithm does not use the variable
number of neighbors $\bar{\nu}^{(i)}_{t}(\omega)$ but the nominal (constant)
value $\bar{\nu}^{(i)}$, replacing missing packets, $\beta^{(ij)}_{t}=0$, with
local values, namely $\tilde{C}^{(i)}_{t}/\bar{\nu}^{(i)}$,
$\tilde{n}^{(i)}_{t}/\bar{\nu}^{(i)}$, $w^{(i)}_{t}/\bar{\nu}^{(i)}$.

###### Remark 2

It is worth noticing that, differently from other popular consensus
algorithms, $\tilde{C}^{(i)}_{t}-\tilde{C}^{(j)}_{t}$ does not converge to
zero, and the asymptotic values of $\tilde{C}^{(i)}_{t}$,
$\tilde{n}^{(i)}_{t}$ and $w^{(i)}_{t}$ depend on the agent. However,
$\tilde{C}^{(i)}_{t}/\bar{\nu}^{(i)}_{t}-\tilde{C}^{(j)}_{t}/\bar{\nu}^{(j)}_{t}\to
0$ for all $(i,j)$. The estimates of the sums of interest,
$N=\sum_{i=1}^{N}\tilde{n}^{(i)}$ and
$G=\sum_{i=1}^{N}C_{i}^{\top}R_{i}^{-1}C_{i}$, are obtained as
$\tilde{n}^{(i)}_{t}/w^{(i)}_{t}$ and $\tilde{C}^{(i)}_{t}/w^{(i)}_{t}$.

###### Remark 3

When it is challenging to orchestrate the initial conditions $w^{(i)}_{0}$ to
be zero for all the nodes apart from one it is possible to resort to the _max-
consensus_ algorithm of [26] in order to effectively decide a leader in the
graph. The analysis of the resulting algorithm in presence of link failures
can be developed in analogy with the one reported here.

###### Remark 4

We assume that in absence of link failures the network graph $\mathcal{G}$ is
static. In this condition, the first part of the algorithm, Step 2, can be
stopped when the asymptotic values of $G^{(i)}$, $N^{(i)}$ and $K^{(i)}$ are
reached. Moreover, under standard hypothesis, the iterative Riccati equation
at Step 3 reaches its steady-state value in a limited number of additional
iterations. Thus, at steady state, the filter reduces at Steps 4, 5 of Fig. 1.

###### Remark 5

Failures are modeled by separate and independent variables. At each time $t>0$
link failures that occur at Step 2.2, (3), (5), are modeled by
$\beta_{t}^{(ij)}(\omega)$, and those in the averaging Step 5.2 are modeled by
$\beta_{t,h}^{(ij)}(\omega)$.

###### Remark 6

The choice of the parameters $\delta$ and $\gamma$ will be considered in the
next section. This choice has no influence on Steps 2, 3.

##  4 Analysis of the DKF with link failures

The estimation algorithm in Fig. 1 can be broadly divided in two parts. Steps
2, 3 aim at estimating the optimal gains $K^{(i)}$ by computing
$G=C^{\top}R^{-1}C=\sum_{i=1}^{N}C_{i}^{\top}R_{i}^{-1}C_{i}$, whereas the
second one uses $K^{(i)}$ for the online estimation algorithm. For this reason
we divide our analysis in two parts. We first show that $K^{(i)}\to
NP_{\infty}C_{i}^{\top}R_{i}^{-1}$. We can then analyze the behavior of the
estimation algorithm when $K^{(i)}$ is replaced by its asymptotic value.

The communication pattern at time $t$ (resp. $(t,h)$ for the dynamic
averaging) is described by the random Laplacian matrix

$(\mathcal{L}_{t}(\omega))_{i,j}=\begin{cases}-\beta_{t}^{(ij)}(\omega),\textnormal{
if }i\neq j\\\
\nu^{(i)}_{t}(\omega)=\sum_{\ell\in\mathcal{N}^{(i)}}\beta_{t}^{(i\ell)}(\omega),\textnormal{
if }i=j.\end{cases}$ (15)

Assumption 3 guarantees that the random Laplacian still enjoys the properties
of the initial Laplacian matrix $\bar{\mathcal{L}}$.

###### Lemma 1

If Assumption 3 holds then: (i)
$\mathbb{E}[\mathcal{L}_{t}(\omega)]=p_{\beta}\bar{\mathcal{L}}$; (ii)
$\mathcal{L}_{t}(\omega)$ is symmetric and positive semi-definite; (iii)
$0\in\sigma(\mathcal{L}_{t}(\omega))$ and the associated left and right
normalized eigenvectors are $v=\frac{1}{\sqrt{N}}\mathbf{1}_{N}$ and
$v^{\top}$; (iv) for all $\omega$,
$\rho(\mathcal{L}_{t}(\omega))\leq\rho(\bar{\mathcal{L}})$.

Proof. The first three properties are a consequence of the fact that
$\mathcal{L}_{t}(\omega)$ is still the Laplacian matrix of an undirected
graph. To prove $\rho(\mathcal{L}_{t}(\omega))\leq\rho(\bar{\mathcal{L}})$ we
recall the following well known property (see [8], Section 1.2),
$x^{\top}\mathcal{L}x=\sum_{(i,j)\in\mathcal{E}}(x_{i}-x_{j})^{2}$, that
implies, $\forall x\in\mathbb{R}^{N}$, $0\leq
x^{\top}\mathcal{L}_{t}(\omega)x\leq x^{\top}\bar{\mathcal{L}}x$, that is,
$\|\mathcal{L}_{t}(\omega)\|\leq\|\bar{\mathcal{L}}\|$. Both matrices are
symmetric and positive semi-definite, and then
$\max(\sigma(\mathcal{L}_{t}(\omega)))\leq\max(\sigma(\bar{\mathcal{L}}))$.
$\Box$

###  4.1 Convergence analysis of the local gains

The goal of this section is to prove that in presence of link failures the
broadcast Push-Sum algorithm at Step 2 in Fig. 1 computes at each node $N$ and
$G=\sum_{i=1}^{N}C_{i}^{\top}R_{i}^{-1}C_{i}$. This provides a distributed
computation of $P_{\infty}$ and $K^{(i)}$ that are essential for the filters
equation at Steps 4, 5 of DKF.

The convergence of the broadcast Push-Sum algorithm has already been studied
[26]. We report for completeness the convergence result for the case without
link failures.

###### Theorem 1

In absence of link failures (_i.e._ $\beta_{t}^{(ij)}=\beta_{t,h}^{(ij)}=1$
$\forall t,h\geq 0$, $i\neq j$), if Assumption 1 holds then the sequences
$\tilde{C}^{(i)}_{t}$, $\tilde{n}^{(i)}_{t}$, $w^{(i)}_{t}$ generated by
(3)–(5) are such that

$\displaystyle\lim_{t\to\infty}\tilde{C}^{(i)}_{t}\to$
$\displaystyle\frac{\bar{\nu}^{(i)}}{\sum_{j=1}^{N}\bar{\nu}^{(j)}}\sum_{j=1}^{N}C_{j}^{\top}R_{j}^{-1}C_{j}$
(16) $\displaystyle\lim_{t\to\infty}\tilde{n}^{(i)}_{t}\to$
$\displaystyle\frac{\bar{\nu}^{(i)}}{\sum_{j=1}^{N}\bar{\nu}^{(j)}}N$ (17)
$\displaystyle\lim_{t\to\infty}w^{(i)}_{t}\to$
$\displaystyle\frac{\bar{\nu}^{(i)}}{\sum_{j=1}^{N}\bar{\nu}^{(j)}}$ (18)

The result is proved in Appendix A.3. The extension to the case of link
failures, which is one of the main results of this paper, requires Assumption
3.

###### Theorem 2

If Assumption 1 and Assumption 3 are satisfied then the limits (16)–(18) hold
in probability.

The proof is reported in Appendix A.4.

###  4.2 Asymptotic analysis of the estimation errors

In this section we analyze the performance of the DKF with link failures,
corresponding to Steps 4, 5 in Fig. 1. In particular, we prove that the
estimate provided by DKF with link failures is asymptotically unbiased and
mean square bounded for a sufficiently large $\delta$ and $\gamma$. This
provides also some guidelines to tune the parameters $\delta$ and $\gamma$. We
assume that the values of $G^{(i)}$ and $N^{(i)}$ have already reached their
respective asymptotic value, $G=C^{\top}R^{-1}C$ and $N$, and
$K^{(i)}=NP_{\infty}C_{i}^{\top}R_{i}^{-1}$ where $P_{\infty}$ solves (12).

Let
$\widehat{\bf{X}}_{t}=\textnormal{col}_{i=1}^{N}(\widehat{\bf{x}}^{(i)}_{t|t})\in\mathbb{R}^{nN}$
be the estimates at the nodes, and
${\bf{X}}_{t}=\mathbf{1}_{N}\otimes{\bf{x}}_{t}\in\mathbb{R}^{nN}$ the vector
corresponding to the system state that evolves as

${\bf{X}}_{t+1}=\mathbf{1}_{N}\otimes(A{\bf{x}}_{t}+{\bf{f}}_{t})=(I_{N}\otimes
A){\bf{X}}_{t}+\mathbf{1}_{N}\otimes{\bf{f}}_{t}.$ (19)

The overall estimation error is thus
${\bf{E}}_{t}={\bf{X}}_{t}-\widehat{\bf{X}}_{t}=\textnormal{col}_{i=1}^{N}({\bf{e}}^{(i)}_{t})$,
with ${\bf{e}}^{(i)}_{t}={\bf{x}}_{t}-\widehat{\bf{x}}^{(i)}_{t|t}$.

Let $\bar{\mathcal{L}}=\bar{\mathcal{L}}^{\top}$ denote the communication
graph in absence of failures. The spectrum of $\bar{\mathcal{L}}$ is
$\sigma(\bar{\mathcal{L}})=\\{\lambda_{1}=0,\lambda_{2},\ldots,\lambda_{N}\\}$,
where $\lambda_{i}\in\mathbb{R}$ for $i=1,\ldots,N$. Let

$\displaystyle M_{t}^{(\gamma)}(\omega)=$
$\displaystyle\prod_{h=0}^{\gamma-1}\left(I_{N}-\frac{1}{\delta}\mathcal{L}_{t,h}(\omega)\right)\in\mathbb{R}^{N\times
N}.$ (20)

The averaging Step 5.2 can be represented through $M_{t}^{(\gamma)}(\omega)$
in (20) and
${\bf{Z}}_{t+1,h}=\textnormal{col}_{i=1}^{N}({\bf{z}}^{(i)}_{t+1,h})$,
$i=1,\ldots,N$, as

${\bf{Z}}_{t+1,h+1}=\left(M_{t}^{(\gamma)}(\omega)\otimes
I_{n}\right){\bf{Z}}_{t+1,h}.$ (21)

Let $A_{i}=(I-K^{(i)}C_{i})A$. From (12), (13) it follows that, for
$A_{C}=A-K_{\infty}CA$.

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}A_{i}=$
$\displaystyle\frac{1}{N}\sum_{i=1}^{N}(I_{n}-K^{(i)}C_{i})A=(I_{n}-K_{\infty}C)A=A_{C}.$
(22)

We therefore have

$\displaystyle{\bf{z}}^{(i)}_{t+1,0}=$ $\displaystyle
A\widehat{\bf{x}}^{(i)}_{t|t}+K^{(i)}\left(C_{i}A\left({\bf{x}}_{t}-\widehat{\bf{x}}^{(i)}_{t|t}\right)+C_{i}{\bf{f}}_{t}+{\bf{g}}^{(i)}_{t+1}\right)$
$\displaystyle=$ $\displaystyle
A{\bf{x}}_{t}-A_{i}{\bf{e}}^{(i)}_{t}+K^{(i)}\left(C_{i}{\bf{f}}_{t}+{\bf{g}}^{(i)}_{t+1}\right)$
(23) $\displaystyle\widehat{\bf{X}}_{t+1}=$
$\displaystyle\left(M_{t}^{(\gamma)}(\omega)\otimes
I_{n}\right)(\mathbf{1}_{N}\otimes A{\bf{x}}_{t})$
$\displaystyle-\left(M_{t}^{(\gamma)}(\omega)\otimes
I_{n}\right)\textnormal{diag}_{i}(A_{i}){\bf{E}}_{t}$
$\displaystyle+\left(M_{t}^{(\gamma)}(\omega)\otimes
I_{n}\right)\textnormal{col}_{i}\left(\
K^{(i)}(C_{i}{\bf{f}}_{t}+{\bf{g}}^{(i)}_{t+1})\right)$ $\displaystyle=$
$\displaystyle(I_{N}\otimes
A){\bf{X}}_{t}-\left(M_{t}^{(\gamma)}(\omega)\otimes
I_{n}\right)\textnormal{diag}_{i}(A_{i}){\bf{E}}_{t}$
$\displaystyle+\left(M_{t}^{(\gamma)}(\omega)\otimes
I_{n}\right)\textnormal{col}_{i}\left(\
K^{(i)}(C_{i}{\bf{f}}_{t}+{\bf{g}}^{(i)}_{t+1})\right),$ (24)

where we have used the property

$\displaystyle\left(M_{t}^{(\gamma)}(\omega)\otimes
I_{n}\right)(\mathbf{1}_{N}\otimes A{\bf{x}}_{t})=(\mathbf{1}_{N}\otimes
A{\bf{x}}_{t})=(I_{N}\otimes A){\bf{X}}_{t}$

that descends from $M_{t}^{(\gamma)}(\omega)\mathbf{1}_{N}=\mathbf{1}_{N}$
(see Lemma 9, point 3, in Appendix A.2). By subtracting (24) from (19)

$\displaystyle{\bf{E}}_{t+1}$
$\displaystyle=A_{\mathcal{G}}^{(\gamma)}(\omega){\bf{E}}_{t}+\left(M_{t}^{(\gamma)}(\omega)\otimes
I_{n}\right)\textnormal{col}_{i=1}^{N}({\bf{h}}^{(i)}_{t}),$ (25)

with

$\displaystyle A_{\mathcal{G}}^{(\gamma)}(\omega)$
$\displaystyle=\left(M_{t}^{(\gamma)}(\omega)\otimes
I_{n}\right)\textnormal{diag}_{i}(A_{i})$ (26)
$\displaystyle{\bf{h}}^{(i)}_{t}$
$\displaystyle=(I_{n}-K^{(i)}C_{i}){\bf{f}}_{t}-K^{(i)}{\bf{g}}^{(i)}_{t+1}.$
(27)

The stability analysis of ${\bf{E}}_{t}$ in (25) is not trivial, because
$A_{\mathcal{G}}^{(\gamma)}(\omega)$ is a random matrix. Our analysis makes
use of Lemma 10 in Appendix B that provides sufficient conditions for mean
square boundedness of linear systems with random matrices. We also use the
following simple bound.

###### Lemma 2

Let $M(\omega)\in\mathbb{R}^{n\times n}$ be a symmetric random matrix such
that $\forall\omega:\ \rho(M(\omega))\leq 1$ and
$\mathbb{P}(\\{\omega:\rho(M)=1\\})<1$. Then $\rho(\mathbb{E}[M(\omega)])<1$.

Proof. Since $M(\omega)$ is symmetric, $\rho(M(\omega))=\|M(\omega)\|$ and
$\rho(\mathbb{E}[M(\omega)])=\|\mathbb{E}[M(\omega)\|$. Clearly,
$1>\mathbb{E}[\rho(M(\omega))]$, and by Jensen’s inequality
$1>\mathbb{E}[\rho(M(\omega))]=\mathbb{E}[\|M(\omega)\|]\geq\quad\|\mathbb{E}[M(\omega)]\|=\rho(\mathbb{E}[M(\omega)])$.
$\Box$

The matrix $M_{t}^{(\gamma)}(\omega)$ in (25) is in general not symmetric but
it enjoys several interesting properties.

###### Lemma 3

The expected value of $M_{t}^{(\gamma)}(\omega)$ is

$\displaystyle\mathbb{E}\left[M_{t}^{(\gamma)}(\omega)\right]=$
$\displaystyle\bar{M}^{(\gamma)}=\left(I_{N}-\frac{p_{\beta}}{\delta}\bar{\mathcal{L}}\right)^{\gamma}.$
(28)

The eigenvalues of $\bar{M}^{(\gamma)}$ are
$\\{(1-\frac{p_{\beta}}{\delta}\lambda_{i})^{\gamma}\\}$, with
$\lambda_{i}\in\sigma(\bar{\mathcal{L}})$. In particular,
$1\in\sigma(\bar{M}^{(\gamma)})$.

The proof is reported in A.1 together with other auxiliary results and
properties. The main result is that the estimate provided by DKF with link
failures is asymptotically unbiased and mean square bounded for a sufficiently
large $\delta$ and $\gamma$ (the proof is reported in Appendix A.5).

###### Theorem 3

When Assumption 1, 2 and 3 hold and $\delta>\rho(\bar{\mathcal{L}})$ there
exists $\gamma_{0}\in\mathbb{N}$ such that $\forall\gamma>\gamma_{0}$ the
estimate of the DKF filter (Steps 4 and 5 in Fig. 1) is asymptotically
unbiased and mean square bounded.

A particular cases arises when the output matrices are identical, _i.e._
$C_{i}=C_{j}$, $i,j=1,\ldots,N$, that implies $A_{i}=A_{C}$ for all
$i=1,\ldots,N$. In this case, any number of consensus steps yields asymptotic
unbiased estimates.

###### Corollary 1

In the hypotheses of Theorem 3, if in addition $C_{i}=C_{j}$ for
$i,j=1,\ldots,N$ then for any $\gamma\geq 1$ the estimate of the DKF filter
(Steps 4 and 5 in Fig. 1) is asymptotically unbiased and mean square bounded.
Moreover, in this case the equation (25) of the estimation error in the
transformed coordinates
$\widetilde{{\bf{E}}}_{t}=\mathcal{T}^{-1}{\bf{E}}_{t}=\mathcal{T}^{\top}{\bf{E}}_{t}$,
where $\mathcal{T}$ is defined in (80) is

$\widetilde{{\bf{E}}}_{t+1}=\begin{pmatrix}A_{C}&0\\\
0&S_{t}^{(\gamma)}(\omega)\otimes
A_{C}\end{pmatrix}\widetilde{{\bf{E}}}_{t}+\tilde{{\bf{h}}}_{t},$ (29)

where $S_{t}^{(\gamma)}(\omega)$ is defined in (63) and $\tilde{{\bf{h}}}_{t}$
in (83).

The proof is reported in Appendix A.6 and the properties of the matrix
$S_{t}^{(\gamma)}(\omega)$ are summarized in Lemma 9. The following lemma
provides the asymptotic value of the covariance of the transformed noise
${\tilde{\bf{h}}}_{t}$ as $\gamma\to\infty$.

###### Lemma 4

Let
$\Psi_{{\tilde{\bf{h}}}}=\mathbb{E}[{\tilde{\bf{h}}}_{t}{\tilde{\bf{h}}}_{t}^{\top}]\in\mathbb{R}^{nN\times
nN}$. If Assumption 1, 2 and 3 hold and $\delta>\rho(\bar{\mathcal{L}})$ then
$\lim_{\gamma\to\infty}\Psi_{{\tilde{\bf{h}}}}$ is equal to

$\begin{pmatrix}N(I_{n}-K_{\infty}C)Q(I_{n}-K_{\infty}C)^{\top}+NP_{\infty}C^{\top}R^{-1}CP_{\infty}&0\\\
0&0\end{pmatrix}.$

The proof of this lemma is reported in Appendix A.7. We are now in the
position of extending to the case of link failures another key property of
DKF.

###### Theorem 4

If Assumption 1, 2 and 3 hold and $\delta>\rho(\bar{\mathcal{L}})$ then the
covariance of the estimation error at each node tends for $t\to\infty$ and
$\gamma\to\infty$ to the covariance $P_{\infty}$ of the centralized Kalman
filter.

The proof is reported in Appendix A.8.

All the results have been obtained under the condition
$\delta>\rho(\bar{\mathcal{L}})$, guaranteeing that
$\mathbb{E}[S_{t}^{(\gamma)}(\omega)^{[2]}]$ and $\bar{S}^{\gamma}$ are Schur.
Since the eigenvalues of $\bar{S}$ are $1-\frac{p_{\beta}}{\delta}\lambda_{i}$
with $\lambda_{i}\in\sigma(\bar{\mathcal{L}})>0$, there is trade-off between
stability and performance. A large $\delta$ is safer but the convergence to
$0$ of the expected value of the estimation error is slow and the variance can
be large. Thus, a value only slightly larger than $\rho(\bar{\mathcal{L}})$ is
in practice the best choice. Clearly, $\delta>\rho(\bar{\mathcal{L}})$ cannot
be verified by using only local information, but one can use
$\delta>\max_{i}\\{\nu^{(i)}\\}>\rho(\bar{\mathcal{L}})$ (see [2]), where
$\max_{i}\\{\nu^{(i)}\\}$ can be computed through a distributed algorithm.

###  4.3 Bounds for the number of consensus steps

A lower bound of $\gamma$ for the mean dynamics $\mathbb{E}[{\bf{E}}_{t}]$ can
be obtained by guaranteeing the error system

$\displaystyle\mathbb{E}[{\bf{E}}_{t+1}]=$
$\displaystyle\mathbb{E}[A_{\mathcal{G}}^{(\gamma)}]\mathbb{E}[{\bf{E}}_{t}]=\left(\bar{M}^{(\gamma)}\otimes
I_{n}\right)\textnormal{diag}_{i}(A_{i})\mathbb{E}[{\bf{E}}_{t}]$ (30)

is asymptotically stable. To this aim, we will reason on the dual global error
system
${\bf{e}}_{t}=\mathbb{E}\left[A_{\mathcal{G}}^{(\gamma)}\right]^{\top}{\bf{e}}_{t}$.
If

$\mathcal{T}^{\top}{\bf{e}}_{t}=(T^{\top}\otimes
I_{n}){\bf{e}}_{t}=:{\widetilde{\bf{e}}}_{t}=\begin{pmatrix}{\widetilde{\bf{e}}}_{t}^{(1)}\cr{\widetilde{\bf{e}}}_{t}^{(2)}\end{pmatrix},$
(31)

where $\mathcal{T}=(v\ W)\otimes I_{n}$ as in (80), we obtain

$\displaystyle\begin{pmatrix}{\widetilde{\bf{e}}}_{t+1}^{(1)}\cr{\widetilde{\bf{e}}}_{t+1}^{(2)}\end{pmatrix}=$
$\displaystyle\mathbb{E}[H_{t}(\omega)]^{\top}\begin{pmatrix}{\widetilde{\bf{e}}}_{t}^{(1)}\cr{\widetilde{\bf{e}}}_{t}^{(2)}\end{pmatrix}=\bar{H}^{\top}\begin{pmatrix}{\widetilde{\bf{e}}}_{t}^{(1)}\cr{\widetilde{\bf{e}}}_{t}^{(2)}\end{pmatrix},$
(32)

with $H_{t}(\omega)$ defined in (82), $\bar{H}=\mathbb{E}[H_{t}]$,

$\displaystyle\bar{H}^{\top}=$
$\displaystyle\begin{pmatrix}A_{C}^{\top}&\mathbb{E}[{H}_{21}^{(\gamma)}]^{\top}\\\
H_{12}^{\top}&\mathbb{E}[{H}_{22}^{(\gamma)}]^{\top}\end{pmatrix}=\mathcal{T}^{\top}{\widebar{A}}_{D}^{\top}\mathcal{T}\begin{pmatrix}I_{n}&0\\\
0&\bar{S}^{\gamma}\otimes I_{n}\end{pmatrix}$ (33)

where $\bar{S}=\mathbb{E}[S_{t,h}(\omega)]$ is defined in (58),
${H_{21}^{(\gamma)}}(\omega)$, ${H_{22}^{(\gamma)}}(\omega)$ defined in (82),
${\widebar{A}}_{D}=\textnormal{diag}_{i=1}^{N}(A_{i})$. The Riccati equation
(12) guarantees that it is always possible to pick $\lambda\in(0,1)$ such that

$A_{C}P_{\infty}A_{C}^{\top}\leq\lambda P_{\infty}.$ (34)

In the proof of the next theorem we use the weighted norms

$\|N\|_{M}:=\sup_{z\in{\mathbb{R}}^{m}}\sqrt{\frac{z^{\top}N^{\top}MNz}{z^{\top}Mz}},$
(35)

$N\in\mathbb{R}^{m\times m}$ , $M\in{\mathcal{P}}_{+}(m)$. (34) implies
$\|A_{C}^{\top}\|_{P_{\infty}}\leq\sqrt{\lambda}$.

###### Theorem 5

If $\delta>\rho(\bar{\mathcal{L}})$ the DKF with link failures is
asymptotically unbiased for all $\gamma$ such that $\rho(A_{R}(\gamma))<1$,

$\displaystyle A_{R}(\gamma):=$
$\displaystyle\begin{pmatrix}\sqrt{\lambda}&\theta_{p_{\beta}}^{\gamma}c_{B}\\\
c_{B}&\theta_{p_{\beta}}^{\gamma}c_{B}\end{pmatrix}\in\mathbb{R}^{2\times 2}$
(36) $\displaystyle c_{B}:=$
$\displaystyle(1+N\|P_{\infty}\|\|G\|_{P_{\infty}})\|A\|_{P_{\infty}},$ (37)

where $\lambda\in(0,1)$ satisfies (34) and
$\theta_{p_{\beta}}:=1-\frac{p_{\beta}}{\delta}(1-\cos(\pi/N))<1$.

Proof. Since $\|\mathcal{T}\|=1$ and
$\|{\widebar{A}}_{D}^{\top}\|=\|\textnormal{diag}_{i}(A_{i})\|=\max_{i}\|A_{i}\|$,

$\displaystyle\|\mathcal{T}^{\top}{\widebar{A}}_{D}^{\top}\mathcal{T}\|_{I_{N}\otimes
P_{\infty}}$ $\displaystyle=\max_{i}\|A_{i}\|_{I_{N}\otimes P_{\infty}}\leq
c_{B}.$ (38)

Moreover, notice that, with $\theta_{p_{\beta}}$ defined in (59),

$\displaystyle\|\bar{S}\otimes I_{n}\|_{I_{N-1}\otimes P_{\infty}}=$
$\displaystyle\|\bar{S}\otimes I_{n}\|\leq\theta_{p_{\beta}},$ (39)
$\displaystyle\|(\bar{S}\otimes I_{n})^{\gamma}\|_{I_{N-1}\otimes
P_{\infty}}=$
$\displaystyle\|\bar{S}\|^{\gamma}\leq\theta_{p_{\beta}}^{\gamma}.$ (40)

By using $\|A_{C}^{\top}\|_{P_{\infty}}\leq\sqrt{\lambda}$, (33) and (38) we
have

$\displaystyle\|{\widetilde{\bf{e}}}_{t+1}^{(1)}\|_{P_{\infty}}\leq$
$\displaystyle\sqrt{\lambda}\|{\widetilde{\bf{e}}}_{t}^{(1)}\|_{P_{\infty}}+\theta_{p_{\beta}}^{\gamma}c_{B}\|{\widetilde{\bf{e}}}_{t}^{(2)}\|_{I_{N-1}\otimes
P_{\infty}}$ (41)
$\displaystyle\|{\widetilde{\bf{e}}}_{t+1}^{(2)}\|_{I_{N-1}\otimes
P_{\infty}}\leq$
$\displaystyle\,c_{B}\|{\widetilde{\bf{e}}}_{t}^{(1)}\|_{P_{\infty}}+\theta_{p_{\beta}}^{\gamma}c_{B}\|{\widetilde{\bf{e}}}_{t}^{(2)}\|_{I_{N-1}\otimes
P_{\infty}}$ (42)

Finally, we conclude

$\displaystyle\begin{pmatrix}\|{\widetilde{\bf{e}}}_{t+1}^{(1)}\|_{P_{\infty}}\\\
\|{\widetilde{\bf{e}}}_{t}^{(2)}\|_{I_{N-1}\otimes
P_{\infty}}\end{pmatrix}\leq$ $\displaystyle
A_{R}(\gamma)\begin{pmatrix}\|{\widetilde{\bf{e}}}_{t}^{(1)}\|_{P_{\infty}}\cr\|{\widetilde{\bf{e}}}_{t}^{(2)}\|_{I_{N-1}\otimes
P_{\infty}}\end{pmatrix}.$ (43)

Thus, for the stability of (30), it is sufficient that the spectral radius of
$A_{R}(\gamma)$ is less than $1$. $\Box$

###### Corollary 2

The condition (36) is always satisfied when

$\left(1-\frac{p_{\beta}(1-\cos{(\pi/N)})}{\delta}\right)^{\gamma}<\left(\frac{1-\sqrt{\lambda}}{c_{B}}\right)^{2}$
(44)

The proof of the bound of the lower bound on $\gamma$ expressed by (44) is
obtained by computing an upper bound of $\rho(A_{R}(\gamma))$ in (36) less
than $1$.

$\displaystyle\mathbb{E}\left[H_{t}(\omega)^{[2]}\right]=\left(\begin{array}[]{@{}c|c
c c@{}}A_{C}^{[2]}&A_{C}\otimes H_{12}&H_{12}\otimes A_{C}&{H_{12}}^{[2]}\\\
\hline\cr
A_{C}\otimes\mathbb{E}[{H}_{21}^{(\gamma)}]&A_{C}\otimes\mathbb{E}[{H}_{22}^{(\gamma)}]&H_{12}\otimes\mathbb{E}[{H}_{21}^{(\gamma)}]&H_{12}\otimes\mathbb{E}[{H}_{22}^{(\gamma)}]\\\
\mathbb{E}[{H}_{21}^{(\gamma)}]\otimes
A_{C}&\mathbb{E}[{H}_{21}^{(\gamma)}]\otimes
H_{12}&\mathbb{E}[{H}_{22}^{(\gamma)}]\otimes
A_{C}&\mathbb{E}[{H}_{22}^{(\gamma)}]\otimes H_{12}\\\
\mathbb{E}[{H_{21}^{(\gamma)}}^{[2]}]&\mathbb{E}[H_{21}^{(\gamma)}\otimes
H_{22}^{(\gamma)}]&\mathbb{E}[H_{22}^{(\gamma)}\otimes
H_{21}^{(\gamma)}]&\mathbb{E}[{H_{22}^{(\gamma)}}^{[2]}]\end{array}\right)$
(49) Figure 2: Structure of the matrix
$\mathbb{E}\left[H_{t}(\omega)^{[2]}\right]$.

###### Remark 7

The parameter $\theta_{p_{\beta}}$ defined in Theorem 5 depends on the
probability of successful communications, that can be estimated from each node
from the statistics of the (known) link failures. Since for all $p_{\beta}<1$
we have $\theta_{p_{\beta}}<1$, there is always $\gamma$ such that
$\rho(A_{R}(\gamma))<1$. The matrices $P$, $G$, $N$ and $A$ are known to each
node, thus the lower bound on $\gamma$ can be locally computed.

###### Theorem 6

If $\delta>\rho(\bar{\mathcal{L}})$ the DKF with link failures is mean square
bounded for all $\gamma$ such that $\rho(A_{S}(\gamma))<1$,

$\displaystyle A_{S}(\gamma):=$
$\displaystyle\begin{pmatrix}\lambda&c_{B}\sqrt{\lambda}&c_{B}\sqrt{\lambda}&c_{B}^{2}\\\
c_{B}\theta_{p_{\beta}}^{\gamma}\sqrt{\lambda}&c_{B}\theta_{p_{\beta}}^{\gamma}\sqrt{\lambda}&c_{B}^{2}\theta_{p_{\beta}}^{\gamma}&c_{B}^{2}\theta_{p_{\beta}}^{\gamma}\\\
c_{B}\theta_{p_{\beta}}^{\gamma}\sqrt{\lambda}&c_{B}^{2}\theta_{p_{\beta}}^{\gamma}&c_{B}\theta_{p_{\beta}}^{\gamma}\sqrt{\lambda}&c_{B}^{2}\theta_{p_{\beta}}^{\gamma}\\\
c_{B}^{2}\theta_{p_{d}}^{\gamma}&c_{B}^{2}\theta_{p_{d}}^{\gamma}&c_{B}^{2}\theta_{p_{d}}^{\gamma}&c_{B}^{2}\theta_{p_{d}}^{\gamma}\end{pmatrix}$
(50)

where $\lambda\in(0,1)$ satisfies (34), $c_{B}$ is defined in (37),
$\theta_{p_{\beta}}<1$ is defined in (59) and $\theta_{p_{d}}<1$ is defined in
Theorem 5.

Proof. After the change of coordinates
$\widetilde{{\bf{E}}}_{t}=\mathcal{T}^{\top}{\bf{E}}_{t}$ that leads to (81)
we derive the conditions for mean square bounded through
$\rho(\mathbb{E}[H_{t}(\omega)^{[2]}])<1$ (see Lemma 10, iii). The matrix
$\mathbb{E}[H_{t}(\omega)^{[2]}]$ is shown in Fig. 2. By using the same
approach as in Theorem 5 we derive an upper bound for the spectral radius with
the spectral radius of the matrix in $\mathbb{R}^{4\times 4}$ obtained by
using upper bounds for the norms of the blocks of
$\mathbb{E}[H_{t}(\omega)^{[2]}]$. The upper bounds for the norms of the
blocks of the first three rows are the same as in Theorem 5. For the fourth
row we need an upper bound for
$\|\mathbb{E}[{S_{t}^{(\gamma)}(\omega)}^{[2]}]\|$, which is provided by Lemma
9, 2), (iii). $\Box$

###### Remark 8

The bound (50) depends not only on the link probability $p_{\beta}$ but also
on the disconnection probability $p_{d}$. This last parameter depends on
$p_{\beta}$ and the network topology. Thus the agents must have some
information on the network configuration in order to estimate $p_{d}$.

##  5 Simulation results

Figure 3: Network topology of the example.

Figure 4: MSE among nodes with respect to $\gamma$ for different values of
probability of receiving information, namely $p_{\beta}$. The plot on the
right is an enlargement of the left plot with a finer discretization of the
probability levels.

We consider the problem of tracking a planar system with a discretization step
$\tau$, where the sensors may estimate only one component of the position,
namely

$\displaystyle A=$ $\displaystyle\begin{pmatrix}I_{2}&\tau I_{2}\\\
0&I_{2}\end{pmatrix},\quad C_{1}=\begin{pmatrix}1&0&0&0\end{pmatrix}\quad
R_{i}=\sigma^{2}_{g}$ $\displaystyle Q=$
$\displaystyle\sigma^{2}\begin{pmatrix}\frac{1}{3}\tau^{3}I_{2}&\frac{1}{2}\tau^{2}I_{2}\\\
\frac{1}{2}\tau^{2}I_{2}&I_{2}\end{pmatrix},\quad
C_{2}=\begin{pmatrix}0&1&0&0\end{pmatrix}.$

We consider the topology of Fig. 3 consisting of a connected graph with $N=10$
nodes and $17$ arcs. Nodes $5$ and $10$ have measurement matrices $C_{1}$ and
$C_{2}$ respectively, the remaining nodes have communication capabilities
only. With $\tau=0.25$, $\sigma=0.05$, $\sigma_{g}=0.1$ we performed
$N_{s}=300$ simulations of $\bar{k}=450$ points for several values of
$\gamma$. The MSE is computed as the norm of the estimation error averaged
over all the nodes and times $k\in[\frac{1}{5}\bar{k},\dots,\bar{k}]$ (to
avoid transient effects). Fig. 4 show the MSE averaged over all the nodes with
respect to the number $\gamma$ of consensus step iterations for different
values of probability of link failure, namely $1-p_{\beta}$. The plot on the
right is an enlargement of the left plot with a finer discretization of the
probability levels and the line corresponding to CKF is the performance of the
centralized Kalman filter without link failures. We can see that the proposed
filter is still stable with $\gamma=1$ with acceptable performance for a
probability of link failure $1-p_{\beta}=0.3$, whilst the MSE of the filter is
unbounded for probability of link failure $1-p_{\beta}=0.4$ with $\gamma=1$
and probability of link failure $1-p_{\beta}=0.5$ with $\gamma\in\\{1,2\\}$.
As expected, when $\gamma$ increases the performance of the filter improves
and tends to the centralized optimal one with no link failure (Fig. 4, right).
Fig. 4 (right) shows that for $p_{\beta}\in[0.7,1]$ and $\gamma\geq 2$ the
performance are essentially the same. Fig. 5 shows for the considered example
the minimum value $p_{\beta}$ of receiving information with respect to the
number $\gamma$ of consensus step iterations in order to keep MSE within a
difference of $10\%$ with respect to the centralized Kalman filter (CKF, no
link failures). The red area denotes the region where the performance
difference degrades over $10\%$ while the pale blue area denotes the region
where the performance difference is below $10\%$. We observe that in this
example it is not possible to keep the performance difference with respect to
the CKF without link failures within $10\%$ if $\gamma\leq 2$.

Figure 5: Minimum admissible value of probability $p_{\beta}$ of receiving
information with respect to the number $\gamma$ of consensus step iterations
in order to keep the performance difference (in terms of MSE) with respect to
the centralized Kalman filter (CKF) without link failures around $10\%$. The
red area denotes the region where performance difference degrades over $10\%$,
while the pale blue area denotes the region where performance difference are
below $10\%$.

##  6 Conclusions

This article studies the stability of a distributed filter with multiple
consensus steps in presence of random link failures when the system is linear
time-invariant, failures are symmetric and not correlated in time. The
extension to directed simmetrizable graphs can be carried out as in [2].
Future developments may aim at extending the framework to time-varying or non-
linear systems, random delays [4], non-symmetric and correlated fault
processes or attacks [12].

##  Appendix A Proofs

###  A.1 Proof of Lemma 3

For the independence of the stochastic Laplacians,

$\displaystyle\mathbb{E}[M_{t}^{(\gamma)}(\omega)]$
$\displaystyle=\prod_{h=0}^{\gamma-1}\left(I_{N}-\frac{1}{\delta}\mathbb{E}[\mathcal{L}_{t,h}(\omega)]\right)=\bar{M}^{(\gamma)}.$
(51)

Let $U$ be the non-singular matrix such that $\bar{\mathcal{L}}=U\Lambda
U^{-1}$, where $\Lambda$ is diagonal and real. Then,

$\displaystyle\bar{M}^{(\gamma)}=\left(I_{N}-\frac{p_{\beta}}{\delta}\bar{\mathcal{L}}\right)^{\gamma}$
$\displaystyle=U\left(I_{N}-\frac{p_{\beta}}{\delta}\Lambda\right)^{\gamma}U^{-1}.$
(52)

Clearly, the eigenvalues of $I_{N}-\frac{p_{\beta}}{\delta}\Lambda$ are
$\\{1-\frac{p_{\beta}}{\delta}\lambda_{i}\\}$, with left and right
eigenvectors $\\{e_{j}\\}$, the versors of the canonical base. It follows from
$(I_{N}-\frac{p_{\beta}}{\delta}\Lambda)e_{j}=(1-\frac{p_{\beta}}{\delta}\lambda_{j})e_{j}$
that
$(I_{N}-\frac{p_{\beta}}{\delta}\Lambda)^{\gamma}e_{j}=(1-\frac{p_{\beta}}{\delta}\lambda_{j})^{\gamma}e_{j}$,
and, due to the similarity relationship,
$(1-\frac{p_{\beta}}{\delta}\lambda_{j})^{\gamma}\in\sigma(\bar{M}^{(\gamma)})$.
Since in particular $\lambda_{1}=0$, $1\in\sigma(\bar{M}^{(\gamma)})$. $\Box$

###  A.2 Auxiliary results

###### Lemma 5

Let $\mathcal{A}$ and $\mathcal{D}$ be, respectively, the adjacency and degree
matrix of an undirected connected graph. Then, matrix
$\Theta=(I+\mathcal{A})(I+\mathcal{D})^{-1}$ has the following properties:

  * a)

$\Theta$ is non-negative, irreducible and column stochastic.

  * b)

$\rho(\Theta)=1=\lambda_{1}\in\sigma(\Theta)$, and $\lambda_{1}=1$ is simple.

  * c)

$\Theta$ is primitive, that is, $\lambda_{1}=1$ is the only eigenvalue on the
unit circle, _i.e._ $|\lambda_{i}|<1$ for $i\neq 1$.

  * d)

The right and left eigenvectors $u_{1}$, $v_{1}^{\top}$ of $\lambda_{1}=1$ are
the only non-negative eigenvectors, where

$\displaystyle u_{1}$
$\displaystyle=\textnormal{col}_{i=1}^{N}(\bar{\nu}^{(i)})=\textnormal{col}_{i=1}^{N}(\nu^{(i)}+1)$
(53) $\displaystyle v_{1}^{\top}$ $\displaystyle=\mathbf{1}_{N}^{\top}.$ (54)

Proof. Point a). By construction, the entries of $\Theta$ are either $0$ or
positive. The irreducibility of $\Theta$ follows from the fact that the matrix
$\mathcal{A}$ is the adjacency matrix of a connected and undirected graph.
From the property

$\displaystyle\Theta=$
$\displaystyle(I_{N}+\mathcal{D}+\mathcal{A}-\mathcal{D})(I_{N}+\mathcal{D})^{-1}=I_{N}-\mathcal{L}(I_{N}+\mathcal{D})^{-1}$

it is easy to check that the entries of the $i$-th column of $\Theta$ are
either $0$ or $1/({\nu}^{(i)}+1)$, _i.e._ the non-zero entries are identical
and there are ${\nu}^{(i)}+1$ of them, so each column sums up to $1$.

Point b). The property $\rho(\Theta)\in\sigma(\Theta)$ follows from the
Perron-Frobenius theorem for non-negative irreducible matrices (see for
example [21], ch. 8). An application of the Gerschgorin Circles to the columns
of $\Theta$ yields $\rho(\Theta)\leq 1$. We show that
$\lambda_{1}=1\in\sigma(\Theta)$ and therefore $\rho(\Theta)=1$. In fact

$\displaystyle\Theta\cdot u_{1}$
$\displaystyle=\Theta\cdot\textnormal{col}_{i=1}^{N}(\bar{\nu}^{(i)})=(I_{N}+\mathcal{A})\cdot\mathbf{1}_{N}=\textnormal{col}_{i=1}^{N}(\bar{\nu}^{(i)}).$

Point c). $\Theta$ is primitive since it is a non-negative irriducible matrix
with non-zero diagonal entries, which is a sufficient condition for
primitivity ([21], ch. 8).

Point d). We have already shown that
$u_{1}=\textnormal{col}_{i=1}^{N}(\bar{\nu}^{(i)})$ is the right eigenvector
of $\lambda_{1}=1$. Moreover, since the columns to $\Theta$ sum up to $1$,
$v_{1}^{\top}\cdot\Theta=\mathbf{1}_{N}^{\top}\cdot\Theta=\mathbf{1}_{N}^{\top}=v_{1}^{\top}$.
Finally, $u_{1}$ and $v_{1}^{\top}$ are the only nonnegative eigenvectors as
stated by the Perron-Frobenius theorem. $\Box$

###### Lemma 6

If $\delta>\rho(\bar{\mathcal{L}})$ then, $\forall\omega$,
$\sigma(M_{t}^{(\gamma=1)}(\omega))\subset[-1,\,1]$, and
$1\in\sigma(M_{t}^{(\gamma=1)}(\omega))$ with right and left normalized
eigenvectors $v=\frac{1}{\sqrt{N}}\mathbf{1}_{N}$ and $v^{\top}$.

Proof. Lemma 1 implies that
$\lambda_{N}(\frac{1}{\delta}\mathcal{L}_{t}(\omega))\leq\lambda_{N}(\frac{1}{\delta}\bar{\mathcal{L}})<1$.
Since $\frac{1}{\delta}\mathcal{L}_{t}(\omega)$ is symmetric and positive
semi-definite, by using the same derivations as in Lemma 3 we obtain that the
eigenvalues of
$M_{t}^{(\gamma=1)}(\omega)=I_{N}-\frac{1}{\delta}\mathcal{L}_{t}(\omega)$ are
$\\{1-\frac{1}{\delta}\lambda_{i}(\mathcal{L}_{t}(\omega))\\}$, with
$\left|1-\frac{1}{\delta}\lambda_{i}(\mathcal{L}_{t}(\omega))\right|\leq 1$.
In particular, since $\lambda_{1}(\mathcal{L}_{t}(\omega))=0$,
$1\in\sigma(M_{t}^{(\gamma=1)}(\omega))$. $\Box$

###### Lemma 7

If $\mathcal{L}_{t}(\omega)$ is the Laplacian matrix of a connected subgraph
of $\mathcal{G}$, $\delta>\rho(\bar{\mathcal{L}})$ and
$W=\textnormal{row}_{i=1}^{N-1}(w_{i})\in\mathbb{R}^{N\times(N-1)}$ is any
(deterministic) matrix whose columns are an orthornormal base of the subspace
$\mathcal{S}^{\bot}_{v}$ orthogonal to
$\mathcal{S}_{v}=\textnormal{span}(\\{v\\})$,
$v=\frac{1}{\sqrt{N}}\mathbf{1}_{N}$, then the matrix

$S_{t}(\omega)=I_{N-1}-\frac{1}{\delta}W^{\top}\mathcal{L}_{t}(\omega)W,$ (55)

is symmetric, semi-definite positive and Schur. Moreover,

$\sigma(S_{t}(\omega))=\sigma(M_{t}^{(\gamma=1)}(\omega))\setminus\\{1\\}.$
(56)

Proof. $S_{t}(\omega)$ is symmetric because $\mathcal{L}_{t}(\omega)$ is
symmetric. $v$ and $\mathcal{S}_{v}$ are independent of $\omega$, hence it
exists a deterministic matrix $W\in\mathbb{R}^{N\times(N-1)}$ such that
$v^{\top}W=W^{\top}v=0$, $W^{\top}W=I_{N-1}$. The matrices
$vv^{\top},\,WW^{\top}\in\mathbb{R}^{N\times N}$ are the projectors on
$\mathcal{S}_{v}$ and $\mathcal{S}^{\bot}_{v}$ respectively, and
$I_{N}=vv^{\top}+WW^{\top}$. Further, for all $\omega$ and
$x\in\mathbb{R}^{N}$, $\mathcal{L}_{t}(\omega)x\in\mathcal{S}_{v}^{\top}$,
since $v^{\top}\mathcal{L}_{t}(\omega)x=0$. Consequently,
$WW^{\top}\mathcal{L}_{t}(\omega)W=\mathcal{L}_{t}(\omega)W$, because the
columns of $\mathcal{L}_{t}(\omega)W$ are in $\mathcal{S}_{v}^{\bot}$ and
$WW^{\top}$ is the projector on $\mathcal{S}^{\bot}_{v}$. Thus,

$\displaystyle M_{t}^{(\gamma=1)}(\omega)$
$\displaystyle=I_{N}-\frac{1}{\delta}\mathcal{L}_{t}(\omega)=vv^{\top}+WS_{t}(\omega)W^{\top}.$
(57)

The two matrices of these decomposition are orthogonal. When
$\mathcal{L}_{t}(\omega)$ is connected, the eigenvalue
$1\in\sigma(M_{t}^{(\gamma=1)}(\omega))$ has multiplicity one and it is the
only non-null eigenvalue of $vv^{\top}$ since $vv^{\top}v=v$. The remaining
$N-1$ eigenvalues of $M_{t}^{(\gamma=1)}(\omega)$, that according to Lemma 6
belong to the interval $(-1,\,1)$, are the eigenvalues of the second term,
that is, the eigenvalues of $S_{t}(\omega)$ and $0$. $\Box$

###### Lemma 8

If $\bar{\mathcal{L}}$ is the Laplacian matrix of a connected graph of
$\mathcal{G}$, $\delta>\rho(\bar{\mathcal{L}})$, $W$ as in Lemma 7, then the
matrix

$\bar{S}=I_{N-1}-\frac{p_{\beta}}{\delta}W^{\top}\bar{\mathcal{L}}W,$ (58)

is symmetric, semi-definite positive and Schur. Moreover,

$\displaystyle\|\bar{S}\|$
$\displaystyle=\rho(\bar{S})=1-\frac{p_{\beta}}{\delta}\lambda_{2}(\bar{\mathcal{L}})$
$\displaystyle\leq\theta_{p_{\beta}}:=1-\frac{p_{\beta}}{\delta}(1-\cos(\pi/N))$
(59) $\displaystyle\bar{M}^{(\gamma)}$
$\displaystyle=vv^{\top}+W\bar{S}^{\gamma}W^{\top}$ (60)
$\displaystyle\bar{S}^{\gamma}$ $\displaystyle=W^{\top}\bar{M}^{(\gamma)}W.$
(61)

Proof. The properties of $\bar{S}$ defined in (58) are easily proved by the
same steps as in Lemma 7, since
$\delta/p_{\beta}\geq\delta>\rho(\bar{\mathcal{L}})$. (59) follows from (58)
by using the lower bound $\lambda_{2}(\bar{\mathcal{L}})\geq 2(1-\cos(\pi/N))$
(see [14]). From (57) it is easy to see that the identity (60) holds for
$\gamma=1$. Proceeding inductively,

$\displaystyle\bar{M}^{(\gamma)}$
$\displaystyle=\bar{M}^{(\gamma-1)}\bar{M}^{(1)}=vv^{\top}+W\bar{S}^{\gamma}W^{\top}.$
(62)

To obtain (61) it is sufficient to pre- and post-multiply the terms in (60) by
$W^{\top}$ and $W$ respectively and recall that $W^{\top}W=I_{N-1}$. $\Box$

###### Lemma 9

If Assumption 3 holds and

$S_{t}^{(\gamma)}(\omega):=\prod_{h=0}^{\gamma-1}S_{t,h}(\omega).$ (63)

then, for all $t$:

  1. 1.

$\mathbb{E}[S_{t}^{(\gamma)}(\omega)]=\bar{S}^{\gamma}$.

  2. 2.

If in addition $\delta>\rho(\bar{\mathcal{L}})$ then:

    1. (i)

$\mathbb{E}[\|S_{t}^{(\gamma)}(\omega){S_{t}^{(\gamma)}}(\omega)^{\top}\|]<1$.

    2. (ii)

$\mathbb{E}[S_{t}^{(\gamma)}(\omega){S_{t}^{(\gamma)}}(\omega)^{\top}]$ is
Schur.

    3. (iii)

$\|\mathbb{E}[{S_{t}^{(\gamma)}(\omega)}^{[2]}]\|\leq\theta_{p_{d}}^{\gamma}$,

$\displaystyle\theta_{p_{d}}:=(1-p_{d})\theta_{p_{\beta}}^{2}+p_{d}$
$\displaystyle<1$ (64)

    4. (iv)

$\lim_{\gamma\to\infty}\|\mathbb{E}[{S_{t}^{(\gamma)}(\omega)}^{[2]}]\|=0$.

  3. 3.

$1\in\sigma(M_{t}^{(\gamma)}(\omega))$ for all $\omega$, and the associated
left and right normalized eigenvectors are
$v=\frac{1}{\sqrt{N}}\mathbf{1}_{N}$ and $v^{\top}$.

  4. 4.

if $\delta>\rho(\bar{\mathcal{L}})$ and $p_{d}<1$ then

$\displaystyle\lim_{\gamma\to\infty}\bar{M}^{(\gamma)}=\lim_{\gamma\to\infty}\mathbb{E}\left[M_{t}^{(\gamma)}(\omega)\right]=vv^{\top}$
$\displaystyle=\frac{1}{N}U_{N}$
$\displaystyle\lim_{\gamma\to\infty}\mathbb{E}\left[{M_{t}^{(\gamma)}(\omega)}^{\top}M_{t}^{(\gamma)}(\omega)\right]=vv^{\top}$
$\displaystyle=\frac{1}{N}U_{N}$

Proof. Point 1. By using the decomposition (57), we have

$\displaystyle M^{(\gamma)}_{t}(\omega)$
$\displaystyle=vv^{\top}+W\left(\prod_{h=0}^{\gamma-1}S_{t,h}(\omega)\right)W^{\top}.$
(65)

By taking expectations with
$\mathbb{E}[M_{t}^{(\gamma)}(\omega)]=\bar{M}^{(\gamma)}$ and by comparing
with (60) we conclude that
$\mathbb{E}[S_{t}^{(\gamma)}(\omega)]=\bar{S}^{\gamma}$.

Point 2. $S_{t,h}(\omega)$ is symmetric and, if
$\delta>\rho(\bar{\mathcal{L}})$, $\rho(S_{t,h}(\omega))\leq 1$ (Lemma 7),
thus $\|S_{t,h}(\omega)\|\leq 1$, $\forall\omega$.

$\displaystyle\|S_{t}^{(\gamma)}(\omega){S_{t}}^{(\gamma)}$
$\displaystyle(\omega)^{\top}\|=\|S_{t,0}(\omega)\cdot\ldots\cdot{S_{t,\gamma-1}}(\omega)^{2}\cdot\ldots\cdot
S_{t,0}(\omega)\|$ $\displaystyle\leq$
$\displaystyle\|S_{t,0}(\omega)\|^{2}\cdot\ldots\cdot\|S_{t,\gamma-1}(\omega)\|^{2}\leq
1.$ (66)

The equality holds only when $\omega$ is such that $\mathcal{L}_{t,h}(\omega)$
is not connected, $h=0,\ldots,\gamma-1$, that is, with probability $p_{d}<1$,
thus
$\mathbb{E}[\|S_{t}^{(\gamma)}(\omega){S_{t}}^{(\gamma)}(\omega)^{\top}\|]<1$.
By using (66) and Lemma 2 it follows that
$\mathbb{E}[S_{t}^{(\gamma)}(\omega){S_{t}}^{(\gamma)}(\omega)^{\top}]$ is
Schur. (iii):

$\displaystyle\|\mathbb{E}[{{S_{t}}^{(\gamma)}}^{[2]}]\|=$
$\displaystyle\|\mathbb{E}[(\Pi_{h=0}^{\gamma-1}S_{t,h})^{[2]}]\|=\|\mathbb{E}[\Pi_{h=0}^{\gamma-1}S_{t,h}^{[2]}]\|$
$\displaystyle=$
$\displaystyle\|\Pi_{h=0}^{\gamma-1}\mathbb{E}[S_{t,h}^{[2]}]\|\leq\prod_{h=0}^{\gamma-1}\|\mathbb{E}[{S_{t,h}}^{[2]}]\|$
$\displaystyle\leq$
$\displaystyle\prod_{h=0}^{\gamma-1}\mathbb{E}[\|S_{t,h}^{[2]}\|]=\mathbb{E}[\rho(S_{t,h}^{[2]})]^{\gamma}=\mathbb{E}[\rho(S_{t,h})^{2}]^{\gamma}$

At each $(t,h)$ the graph is either connected, with probability $1-p_{d}$, and
$\rho(S_{t,h})\leq\theta_{p_{\beta}}$, or disconnected with probability
$p_{d}$ and $\rho(S_{t,h})=1$. It follows
$\mathbb{E}[\rho(S_{t,h})^{2}]\leq\theta_{p_{d}}<1$ and iv).

Point 3.

$\displaystyle M_{t}^{(\gamma)}(\omega)v$
$\displaystyle=M_{t}^{(\gamma-1)}(\omega)\left(I_{N}\cdot
v-\frac{1}{\delta}\mathcal{L}_{t,h}(\omega)v\right)$
$\displaystyle=M_{t}^{(\gamma-1)}(\omega)v=\ldots=v.$ (67)

Point 4. If $\delta>\rho(\bar{\mathcal{L}})$,
$\sigma(\mathbb{E}[M_{t}^{(\gamma)}(\omega)])=\sigma(\bar{M}^{(\gamma)})=\\{(1-\frac{p_{\beta}}{\delta}\lambda_{i})^{\gamma}\\}\subset[-1,\,1]$,
where we have used Lemma 3. Recalling that $1\in\sigma(\bar{M}^{(\gamma)})$,
we obtain that
$\lim_{\gamma\to\infty}\sigma(\mathbb{E}[M_{t}^{(\gamma)}(\omega)])=\\{0,1\\}$.
Thus, $\mathbb{E}[M_{t}^{(\gamma)}(\omega)]$ tends to the projector on the
auto-space of $1$, that is, $vv^{\top}$. Moreover, from (65) and the property

$\mathbb{E}[A(\omega)B(\omega)B^{\top}(\omega)A^{\top}(\omega)]=\mathbb{E}[A(\omega)\mathbb{E}[B(\omega)B^{\top}(\omega)]A^{\top}(\omega)]$

that holds for any couple of independent stochastic matrices $A(\omega)$,
$B(\omega)$ with compatible dimensions, we obtain

$\displaystyle\lim_{\gamma\to\infty}\mathbb{E}\left[{M_{t}^{(\gamma)}}^{\top}M_{t}^{(\gamma)}\right]=vv^{\top}+\lim_{\gamma\to\infty}W\cdot$
$\displaystyle\cdot\mathbb{E}\Big{[}S_{t,0}\mathbb{E}\big{[}S_{t,1}\ldots\mathbb{E}\big{[}S_{t,\gamma-1}^{2}\big{]}\ldots
S_{t,1}\big{]}S_{t,0}\Big{]}W^{\top}=vv^{\top}.$

In fact, for any $h=0,\ldots,\gamma-1$, the absolute value of all the
eigenvalues of $S_{t,h}(\omega)^{2}$ are less than $1$ with probability $>0$.
Thus, $\mathbb{E}[S_{t,h}(\omega)^{2}]$ is Schur (Lemma 2) and the second term
of the decomposition goes to $0$ as $\gamma\to\infty$. $\Box$

###  A.3 Proof of Theorem 1

When $\beta^{(ij)}_{t}\equiv 1$, the recursive equations in (16), (17) and
(18) are of the kind

$\displaystyle
z_{i}(t+1)=\frac{z_{i}(t)}{\bar{\nu}^{(i)}}+\sum_{j_{\in}\mathcal{N}^{(i)}}\frac{z_{j}(t)}{\bar{\nu}^{(j)}}.$
(68)

To prove Theorem 1 we show that for any initial assignment $z_{i}(0)=x_{i}$ at
each node the sequence (68) is such that

$\lim_{t\to\infty}z_{i}(t)=\frac{\bar{\nu}^{(i)}}{\sum_{j=1}^{N}\bar{\nu}^{(j)}}\sum_{j=1}^{N}x_{j},$
(69)

since the thesis follows by taking into account the initial assignments for
$\tilde{C}^{(i)}$, $\tilde{n}^{(i)}$ and $w_{i}$. Let us consider the vector
case $x_{i}\in\mathbb{R}^{n}$, the matrix case being a trivial extension.
Denoting $Z=\textnormal{col}_{i=1}^{N}(z_{i})\in\mathbb{R}^{nN}$ (68) becomes

$\displaystyle Z(t+1)$
$\displaystyle=\left((I_{N}+\mathcal{A})(I_{N}+\mathcal{D})^{-1}\otimes
I_{n}\right)Z(t)$ $\displaystyle=(\Theta\otimes I_{n})Z(t)$ (70)

with $Z(0)=\textnormal{col}_{j=1}^{N}x_{j}$. Since $(\Theta\otimes
I_{n})^{t}=\Theta^{t}\otimes I_{n}$, $\sigma(\Theta^{t}\otimes
I_{n})=\sigma(\Theta^{t})=\\{\lambda_{i}^{t}:\
\lambda_{i}\in\sigma(\Theta)\\}$. As proved in Lemma 5 the matrix $\Theta$ is
non-negative, irreducible and primitive with spectral radius $\rho(\Theta)=1$,
and $\lambda_{1}=1$ is the only eigenvalue on the unit circle, and then

$\displaystyle\lim_{t\to\infty}(\Theta\otimes
I_{n})^{t}Z(0)=\left(\frac{u_{1}v_{1}^{\top}}{v_{1}^{\top}u_{1}}\otimes
I_{n}\right)\textnormal{col}_{j=1}^{N}(x_{j})$
$\displaystyle=\textnormal{col}_{i=1}^{N}\left(\frac{\bar{\nu}^{(i)}}{\sum_{j=1}^{N}\bar{\nu}^{(j)}}\sum_{j=1}^{N}x_{j}\right),$
(71)

because $u_{1}=\textnormal{col}_{i=1}^{N}(\bar{\nu}^{(i)})$ and
$v_{1}^{\top}=\mathbf{1}_{N}$, thus $(v_{1}^{\top}\otimes
I_{n})\textnormal{col}_{j=1}^{N}(x_{j})=\sum_{j=1}^{N}x_{j}$ . $\Box$

###  A.4 Proof of Theorem 2

Our aim is to show that with the property (69) still holds in probability. In
compact form the recursive equations in (16), (17) and (18) are of the kind

$\displaystyle Z(t+1)$
$\displaystyle=\left(((I_{N}+\mathcal{A}(t,\omega)+\mathcal{D}-\mathcal{D}(t,\omega))\right.$
$\displaystyle\cdot\left.(I_{N}+\mathcal{D})^{-1})\otimes I_{n}\right)Z(t)$
$\displaystyle=\left((I_{N}-\mathcal{L}(t,\omega)(I+\mathcal{D})^{-1})\otimes
I_{n}\right)Z(t)$ $\displaystyle=(\Theta(t,\omega)\otimes I_{n})Z(t),$ (72)

In (72), the matrices $\mathcal{A}(t,\omega)$ and
$\mathcal{D}(t,\omega)=\textnormal{diag}_{i}(\nu^{(i)}_{t})$ are, respectively
the (random) adjacency matrix and degree matrix of the random subgraph
$\mathcal{G}(t,\omega)$ of $\mathcal{G}$ that models the symmetric link
failures. The random matrix $\Theta(t,\omega)\in\mathbb{R}^{N\times N}$ still
enjoys all the properties of $\Theta$ in Lemma 5, except being irreducible and
primitive. The algebraic multiplicity of the eigenvalue $\lambda_{1}=1$ can be
more than one when the graph is disconnected due to link failures, but
$\Theta(t,\omega)\geq 0$, $\Theta(t,\omega)$ is column stochastic,
$\rho(\Theta(t,\omega))=1$, $\|\Theta(t,\omega)\|_{1}=1$. This last property
ensures that the solution of (72) is simply stable. Moreover, when
$p_{\beta}>0$, the matrix

$\mathbb{E}_{\Theta}=\mathbb{E}\left[\Theta(t,\omega)\right]=I_{N}-p_{\beta}\bar{\mathcal{L}}(I_{N}+D)^{-1}$
(73)

is non-negative, irreducible, primitive and column stochastic with right and
left eigenvectors $u_{1}$, $v_{1}^{\top}$ defined in (53)–(54). Consequently,

$\lim_{t\to\infty}\mathbb{E}_{\Theta}^{t}=\frac{u_{1}v_{1}^{\top}}{v_{1}^{\top}u_{1}}=\mathcal{P}_{1},$
(74)

where we denote $\mathcal{P}_{1}$ the projector on the autospace of
$\lambda_{1}=1$. The expected value of $Z(t)$ has limit

$\displaystyle\lim_{t\to\infty}Z(t)=$
$\displaystyle\lim_{t\to\infty}\left(\mathbb{E}_{\Theta}^{t}\otimes
I_{n}\right)Z(0)=\left(\mathcal{P}_{1}\otimes I_{n}\right)Z(0),$ (75)

identical to the deterministic case (71). The proof is concluded by showing
that the covariance of $Z(t)$ is asymptotically vanishing. Suppose, for
conciseness, that $n=1$. Then,

$\displaystyle Z(t)=$
$\displaystyle\prod_{\tau=0}^{t-1}\Theta(\tau,\omega)Z(0)$ (76)
$\displaystyle\Psi_{Z}(t)=$
$\displaystyle\mathbb{E}\left[\left(\prod_{\tau=0}^{t-1}\Theta(\tau,\omega)-\mathbb{E}_{\theta}^{t}\right)Z(0)\right.$
$\displaystyle\left.\cdot
Z^{\top}(0)\left(\prod_{\tau=0}^{t-1}\Theta^{\top}(t-1-\tau,\omega)-{\mathbb{E}_{\theta}^{\top}}^{t}\right)\right].$
(77)

By using the property
$\textnormal{stack}(AXA^{\top})=A^{[2]}\textnormal{stack}(X)$ and the temporal
independence of $\Theta(\tau,\omega)$, denoting
$\Psi_{0}=\textnormal{stack}(Z(0)Z^{\top}(0)$ we arrive at

$\displaystyle\textnormal{stack}(\Psi_{Z}(t))=$
$\displaystyle\left(\left(\mathbb{E}\left[\Theta^{[2]}(t,\omega)\right]\right)^{t}-\left(\mathbb{E}_{\Theta}^{[2]}\right)^{t}\right)\Psi_{0}.$
(78)

Since the spectrum of the Kronecker square is composed by the product of
eigenvalues,
$\sigma\left(\mathbb{E}\left[\Theta^{[2]}(t,\omega)\right]\right)\subset[0,1]$
and when $p_{\beta}>0$ the only eigenvalue on the unit circle is
$\lambda_{1}^{2}=1$, thus

$\lim_{t\to\infty}\left(\mathbb{E}\left[\Theta^{[2]}(t,\omega)\right]\right)^{t}=\lim_{t\to\infty}\left(\mathbb{E}_{\Theta}^{[2]}\right)^{t}=\mathcal{P}_{1}^{[2]},$
(79)

and, consequently, $\textnormal{stack}(\Psi_{Z}(t))\to 0$. When $n>1$ it is
sufficient to replace $\Theta(\tau,\omega)$ with $\Theta(\tau,\omega)\otimes
I_{n}$ and $\mathbb{E}_{\Theta}$ with $\mathbb{E}_{\Theta}\otimes I_{n}$ and
the proof is identical.

###  A.5 Proof of Theorem 3

Let $T=(v\ W)$, $T_{v}=v\otimes I_{n}$, $T_{w}=W\otimes I_{n}$ and

$\displaystyle\mathcal{T}$
$\displaystyle=\begin{pmatrix}T_{v}&T_{w}\end{pmatrix},\quad\mathcal{T}^{-1}=\mathcal{T}^{\top}=\begin{pmatrix}T_{v}^{\top}\\\
T_{W}^{\top},\end{pmatrix}$ (80)

where $v=\frac{1}{\sqrt{N}}\mathbf{1}_{N}\in\mathbb{R}^{N\times 1}$ and
$W\in\mathbb{R}^{N\times(N-1)}$ are as in Lemma 7. Consider the change of
coordinates
$\widetilde{{\bf{E}}}_{t}=\mathcal{T}^{-1}{\bf{E}}_{t}=\mathcal{T}^{\top}{\bf{E}}_{t}$.
In the new coordinates the error dynamics is

$\displaystyle\widetilde{{\bf{E}}}_{t+1}=$ $\displaystyle
H_{t}(\omega)\widetilde{{\bf{E}}}_{t}+\tilde{{\bf{h}}}_{t}$ (81)
$\displaystyle H_{t}(\omega)=$
$\displaystyle\begin{pmatrix}T_{v}^{\top}A_{\mathcal{G}}^{(\gamma)}(\omega)T_{v}&T_{v}^{\top}A_{\mathcal{G}}^{(\gamma)}(\omega)T_{W}\\\
T_{W}^{\top}A_{\mathcal{G}}^{(\gamma)}(\omega)T_{v}&T_{W}^{\top}A_{\mathcal{G}}^{(\gamma)}(\omega)T_{W}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}A_{C}&T_{v}^{\top}\textnormal{col}_{i=1}^{N}(W_{i}\otimes
A_{i})\\\ (S_{t}^{(\gamma)}(\omega)\otimes
I_{n})\mathcal{W}_{A}^{\top}T_{v}&(S_{t}^{(\gamma)}(\omega)\otimes
I_{n})\mathcal{W}_{A}^{\top}T_{W}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}A_{C}&H_{12}\\\
H_{21}^{(\gamma)}(\omega)&H_{22}^{(\gamma)}(\omega)\end{pmatrix}$ (82)

with $\mathcal{W}_{A}^{\top}=\textnormal{row}_{i=1}^{N}(W_{i}^{\top}\otimes
A_{i})\ \in\mathbb{R}^{nN\times n(N-1)}$, and

$\displaystyle\tilde{{\bf{h}}}_{t}$
$\displaystyle=\begin{pmatrix}(v^{\top}\otimes
I_{n})(M_{t}^{(\gamma)}(\omega)\otimes I_{n})\\\ (W^{\top}\otimes
I_{n})(M_{t}^{(\gamma)}(\omega)\otimes
I_{n})\end{pmatrix}\textnormal{col}_{i=1}^{N}({\bf{h}}_{t}^{(i)})$
$\displaystyle=\begin{pmatrix}T_{v}^{\top}{\bf{h}}_{t}\\\
(W^{\top}M^{(\gamma)}_{t}(\omega)\otimes I_{n}){\bf{h}}_{t}\end{pmatrix}$ (83)

where $W_{i}\in\mathbb{R}^{1\times(N-1)}$ denotes the rows of
$W=\textnormal{col}_{i=1}^{N}(W_{i})$,
${\bf{h}}_{t}=\textnormal{col}_{i=1}^{N}({\bf{h}}_{t}^{(i)})$,
$S_{t}^{(\gamma)}(\omega)$ is defined by (63) and we used Lemma 9 to derive
that

$\displaystyle T_{v}^{\top}A_{\mathcal{G}}^{(\gamma)}(\omega)T_{v}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}A_{i}=A_{C},$ (84) $\displaystyle
T_{v}^{\top}A_{\mathcal{G}}^{(\gamma)}(\omega)T_{W}$
$\displaystyle=T_{v}^{\top}\textnormal{col}_{i=1}^{N}(W_{i}\otimes A_{i}),$
(85) $\displaystyle T_{W}^{\top}A_{\mathcal{G}}^{(\gamma)}(\omega)T_{v}$
$\displaystyle=(W^{\top}M_{t}^{(\gamma)}(\omega)\otimes
I_{n})\textnormal{diag}_{i=1}^{N}(A_{i})T_{v}$
$\displaystyle=(S_{t}^{(\gamma)}(\omega)\otimes
I_{n})\textnormal{row}_{i=1}^{N}(W_{i}^{\top}\otimes A_{i})T_{v}.$ (86)

Since $H_{21}^{(\gamma)}(\omega)$, $H_{22}^{(\gamma)}(\omega)$ are independent
from the state and the noise and $\mathbb{E}[\tilde{{\bf{h}}}_{t}]=0$, by
taking expectations in (81),

$\displaystyle\mathbb{E}[\widetilde{{\bf{E}}}_{t+1}]=\begin{pmatrix}A_{C}&T_{v}^{\top}\textnormal{col}_{i=1}^{N}(W_{i}\otimes
A_{i})\\\ (\bar{S}^{\gamma}\otimes
I_{n})\mathcal{W}_{A}^{\top}T_{v}&(\bar{S}^{\gamma}\otimes
I_{n})\mathcal{W}_{A}^{\top}T_{W}\end{pmatrix}\mathbb{E}[\widetilde{{\bf{E}}}_{t}],$
(87)

where we have used Lemma 9, point 1, (61) in Lemma 8 and the property
$W^{\top}\bar{M}^{(\gamma)}=\bar{S}^{\gamma}W^{\top}$ that descends from (60)
pre-multiplying by $W^{\top}$. We observe that $A_{C}=(I-K_{\infty}C)A$ is the
dynamical matrix of the centralized Kalman filter, which is Schur for
Assumption 2, and $\bar{S}$ is symmetric and Schur (see Lemma 8). Thus,
$\lim_{\gamma\to\infty}\|\bar{S}^{\gamma}\|=0$ and there exists a sufficiently
large $\gamma_{0}$ such that for all $\gamma>\gamma_{0}$ the dynamical matrix
in (87) is Schur.

As for mean square boundedness, by invoking Lemma 10, iii), we just have to
prove that for a sufficiently large $\gamma$ the matrix
$\mathbb{E}\left[H_{t}(\omega)^{[2]}\right]$, shown in Fig. 2, is time-
invariant and Schur. Time invariance of
$\mathbb{E}\left[H_{t}(\omega)^{[2]}\right]$ is a consequence of the temporal
independence of the blocks $H_{21}^{(\gamma)}(\omega)$,
$H_{22}^{(\gamma)}(\omega)$. From the structure of $H_{21}^{(\gamma)}$,
$H_{22}^{(\gamma)}$ and
$\lim_{\gamma\to\infty}\|\mathbb{E}[{S_{t}^{(\gamma)}(\omega)}^{[2]}]\|=0$
(Lemma 9, point 2-iv) it follows that

$\displaystyle\lim_{\gamma\to\infty}\mathbb{E}\left[H_{t}(\omega)^{[2]}\right]=\begin{pmatrix}A_{C}^{[2]}&*\\\
0&0\end{pmatrix}$

and since $A_{C}^{[2]}$ is Schur, the desired property holds for
$\gamma\to\infty$ and therefore for a sufficiently large $\gamma$.

###  A.6 Proof of Corollary 1

We only need to prove (29). In fact, from (29) it follows that

$\mathbb{E}[\widetilde{{\bf{E}}}_{t+1}]=\begin{pmatrix}A_{C}&0\\\
0&\bar{S}^{\gamma}\otimes
A_{C}\end{pmatrix}\mathbb{E}[\widetilde{{\bf{E}}}_{t}]$ (88)

and, since in the hypotheses both $A_{C}$ and $\bar{S}^{\gamma}$ are Schur, it
follows that the dynamical matrix is Schur. From (29), Lemma 9, 2) and Lemma
10, iii) it follows also that $\widetilde{{\bf{E}}}_{t}$ is mean square
bounded. To prove (29) we observe that when $\forall i,j$ $A_{i}=A_{j}$, then
$A_{i}=A_{C}$ and

$\displaystyle H_{12}=$ $\displaystyle
T_{v}^{\top}\textnormal{col}_{i=1}^{N}(W_{i}\otimes
A_{C})=T_{v}^{\top}(W\otimes A_{C})=0,$

and analogously $H_{21}^{(\gamma)}(\omega)=0$ too. Moreover, since
$\sum_{i=1}^{N}W_{i}^{\top}W_{i}=I_{N-1}$,

$\displaystyle H_{22}^{(\gamma)}(\omega)$
$\displaystyle=(S_{t}^{(\gamma)}(\omega)\otimes
I_{n})\mathcal{W}_{A}^{\top}(W\otimes I_{n})=S_{t}^{(\gamma)}(\omega)\otimes
A_{C}.$

###  A.7 Proof of Lemma 4

Let
$\widetilde{R}=\mathbb{E}[\textnormal{row}_{i}\textnormal{col}_{j}(h_{t}^{(i)}{h_{t}^{(j)}}^{\top})]$
and $S_{t}^{(\gamma)}(\omega)=\Pi_{h=0}^{\gamma-1}S_{t,h}(\omega)$. Since
$\delta>\rho(\bar{\mathcal{L}})$,
$\lim_{\gamma\to\infty}S_{t}^{(\gamma)}(\omega){S_{t}^{(\gamma)}(\omega)}^{\top}$
exists. We can apply Lebesgue’s dominated convergence theorem to obtain

$\displaystyle\lim_{\gamma\to\infty}\Psi_{{\tilde{\bf{h}}}}=$
$\displaystyle\lim_{\gamma\to\infty}\mathbb{E}\left[\mathcal{T}^{\top}(M_{t}^{(\gamma)}(\omega)\otimes
I_{n})\widetilde{R}(M_{t}^{(\gamma)}(\omega)\otimes
I_{n})^{\top}\mathcal{T}\right]$ $\displaystyle=$
$\displaystyle\lim_{\gamma\to\infty}\mathbb{E}\Big{[}\mathcal{T}^{\top}((vv^{\top}+WS_{t}^{(\gamma)}(\omega)W^{\top})\otimes
I_{n})\widetilde{R}\cdot$
$\displaystyle\cdot(((vv^{\top}+WS_{t}^{(\gamma)}(\omega)^{\top}W^{\top})\otimes
I_{n})\mathcal{T}\Big{]}$ $\displaystyle=$
$\displaystyle\mathcal{T}^{\top}((vv^{\top}\otimes
I_{n})\widetilde{R}(vv^{\top}\otimes
I_{n})\mathcal{T}=\begin{pmatrix}T_{v}^{\top}\widetilde{R}T_{v}&0\\\
0&0\end{pmatrix}.$

The thesis follows by observing that

$\displaystyle
T_{v}^{\top}\widetilde{R}T_{v}=\frac{1}{N}\sum_{i,j}\mathbb{E}\left[h_{t}^{(i)}{h_{t}^{(j)}}^{\top}\right]$
$\displaystyle=N\left((I_{n}-K_{\infty}C)Q(I_{n}-K_{\infty}C)^{\top}+P_{\infty}C^{\top}R^{-1}CP_{\infty}\right).$
(89)

###  A.8 Proof of Theorem 4

The proof is obtained by showing that the covariance of the error in the
transformed coordinates
$\widetilde{{P}}_{t}=\mathbb{E}[\widetilde{{\bf{E}}}_{t}\widetilde{{\bf{E}}}_{t}^{\top}]$
satisfies

$\lim_{t\to\infty}\lim_{\gamma\to\infty}\widetilde{{P}}_{t}=\begin{pmatrix}NP_{\infty}&0\\\
0&0\end{pmatrix}$ (90)

that is equivalent to stating that the asymptotic (in time) limit (in
$\gamma$) of the covariance of the estimation error is identical across the
$N$ agents and sums up to $NP_{\infty}$. Let
$\widetilde{{P}}_{0}=T^{\top}\mathbb{E}[{\bf{E}}_{0}{\bf{E}}_{0}^{\top}]T$ be
the initial value of the covariance of the estimation error in the transformed
coordinates. By proceeding inductively,
$\lim_{\gamma\to\infty}\widetilde{{P}}_{1}$ is equal to

$\displaystyle\lim_{\gamma\to\infty}\mathbb{E}\left[\begin{pmatrix}A_{C}&H_{12}\\\
H_{21}^{(\gamma)}(\omega)&H_{22}^{(\gamma)}(\omega)\end{pmatrix}\widetilde{{P}}_{0}\begin{pmatrix}A_{C}^{\top}&{H^{21}}^{\top}_{\gamma}(\omega)\\\
{H_{12}}^{\top}&H_{22}^{(\gamma)}(\omega)\end{pmatrix}\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\lim_{\gamma\to\infty}\Psi_{{\tilde{\bf{h}}}}$
$\displaystyle=\begin{pmatrix}A_{C}&H_{12}\\\
0&0\end{pmatrix}\widetilde{{P}}_{0}\begin{pmatrix}A_{C}^{\top}&0\\\
{H_{12}}^{\top}&0\end{pmatrix}+\lim_{\gamma\to\infty}\Psi_{{\tilde{\bf{h}}}}$
$\displaystyle=\begin{pmatrix}A_{C}(\widetilde{{P}}_{0})_{1,1}A_{C}^{\top}+H_{12}(\widetilde{{P}}_{0})_{1,2}+(\widetilde{{P}}_{0})_{1,2}^{\top}{H_{12}}^{\top}+(\Psi_{{\tilde{\bf{h}}}})_{1,1}&0\\\
0&0\end{pmatrix},$

where $(\Psi_{{\tilde{\bf{h}}}})_{1,1}$ is given by (89), namely

$(\Psi_{{\tilde{\bf{h}}}})_{1,1}=N(I_{n}-K_{\infty}C)Q(I_{n}-K_{\infty}C)^{\top}+NP_{\infty}C^{\top}R^{-1}CP_{\infty}.$

Therefore, only the first $n\times n$ block of
$\lim_{\gamma\to\infty}\widetilde{{P}}_{1}$ is not zero, and this property
continues to hold for all the matrices
$\lim_{\gamma\to\infty}\widetilde{{P}}_{t}$. The block
$\frac{1}{N}\widetilde{{P}}^{1,1}_{t}$ evolves as

$\displaystyle\frac{1}{N}\widetilde{{P}}^{1,1}_{t+1}$
$\displaystyle=(I_{n}-KC)(A\frac{1}{N}\widetilde{{P}}^{1,1}_{t}A^{\top}+Q)(I_{n}-KC)^{\top}$
$\displaystyle\quad+P_{\infty}C^{\top}R^{-1}CP_{\infty}.$ (91)

Since $P_{\infty}$ satisfies the algebraic Riccati equation (12) the
difference $\Delta_{t}=P_{\infty}-\frac{1}{N}\widetilde{{P}}^{1,1}_{t}$
evolves as $\Delta_{t+1}=A_{C}\Delta_{t}A_{C}^{\top}$, which is an
asymptotically stable matrix function because $A_{C}$ is Schur. Consequently,
$\lim_{t\to\infty}\frac{1}{N}\widetilde{{P}}^{1,1}_{t}=P_{\infty}$. $\Box$

##  Appendix B A result on the stability of random matrices

In a probability space $(\Omega,\mathcal{F},P)$ the linear space of
$\mathcal{F}$-measurable vectors $x:\Omega\to\mathbb{R}^{n}$ with finite
second moment, endowed with the inner product
$[x_{1},x_{2}]_{\mathcal{L}_{2}}=\mathbb{E}[x_{1}^{\top}x_{2}]$ is a Hilbert
space denoted
$\mathcal{L}_{2}^{n}=L_{2}((\Omega,\mathcal{F},P);\mathbb{R}^{n})$. If
$x\in\mathcal{L}_{2}^{n}$ then $\mathbb{E}[\|x\|^{2}]<\infty$. In particular,
when $\mathbb{E}[x]=0$ then $\|x\|^{2}_{\mathcal{L}_{2}^{n}}$ is the variance
of the random vector $x$. A random square matrix $A(\omega):\
\Omega\to\mathbb{R}^{n\times n}$ is a $\mathcal{F}$-measurable function from
$\Omega$ to the set of square matrices of size $n$.

###### Lemma 10

Let $\\{A(t,\omega)\\}$, $t=0,1,\ldots$, be a sequence of independent,
$\mathcal{F}$-measurable and identically distributed matrix functions
$A(t,\omega):\ \Omega\to\mathbb{R}^{n\times n}$. Given the system

$x(t+1)=A(t,\omega)x(t)+f(t,\omega),$ (92)

where $x(0)\in\mathcal{L}^{n}_{2}$, $f(t,\omega)$ is a sequence of mutually
independent vectors in $\mathcal{L}^{n}_{2}$, with $\mathbb{E}[f(t,\omega)]=0$
and $f(t,\omega)$ independent from $x_{0}$ for all $t$, $A(t,\omega)$
independent from $x(0)$ and $f(t,\omega)$, then

  1. i)

if $\rho(\mathbb{E}[A])<1$ then $\mathbb{E}[x(t)]\to 0$ exponentially.

  2. ii)

if $\mathbb{E}[\|A\|^{2}]<1$ then $\|x(t)\|_{\mathcal{L}_{2}}$ is uniformly
bounded for all $t$.

  3. iii)

if $\rho(\mathbb{E}[A^{[2]}])<1$ then $\|x(t)\|_{\mathcal{L}_{2}}$ is
uniformly bounded for all $t$.

Proof. i): At each $t$ $A(t,\omega)$ and $x(t)$ are independent,

$\mathbb{E}[x(t+1)]=\mathbb{E}[Ax(t)]=\mathbb{E}[A]\mathbb{E}[x(t)]$ (93)

and since $\mathbb{E}[A]$ is Schur, $\mathbb{E}[x(t)]\to 0$.

ii):

$\displaystyle\|x(t+1)\|_{\mathcal{L}_{2}}$
$\displaystyle=\|A(t,\omega)x(t)+f(t,\omega)\|_{\mathcal{L}_{2}}$
$\displaystyle\quad\leq\mathbb{E}[\|A\|^{2}]^{\frac{1}{2}}\|x(t)\|_{\mathcal{L}_{2}}+\|f(t,\omega)\|_{\mathcal{L}_{2}}.$
(94)

iii): for any conformable matrices $A$, $B$, $C$ it holds that
$\textnormal{stack}(ABC)=(C^{\top}\otimes A)\cdot\textnormal{stack}(B)$. Let
$P(t)=\mathbb{E}[x(t)x(t)^{\top}]$. (92) implies that

$\displaystyle P(t+1)$
$\displaystyle=\mathbb{E}\left[A(t,\omega)P(t)A(t,\omega)^{\top}\right]+\mathbb{E}[f(t,\omega)f(t,\omega)^{\top}]$
(95) $\displaystyle\textnormal{stack}(P(t+1))$
$\displaystyle=\mathbb{E}\left[A(t,\omega)^{[2]}\right]\textnormal{stack}(P(t))$
$\displaystyle\quad\qquad\qquad+\textnormal{stack}(\mathbb{E}[f(t,\omega)f(t,\omega)^{\top}]).$
(96)

It follows that if $\mathbb{E}[A(t,\omega)^{[2]}]$ is Schur then
$\textnormal{stack}(P(t))$ is uniformly bounded in time and the same holds for
$P(t)$. Since $\|x(t)\|^{2}_{\mathcal{L}_{2}}=\textnormal{tr}(P(t))$ the
thesis follows.

$\Box$

## References

  * [1] S. Battilotti, F. Cacace, M. d’Angelo, and A. Germani.  Distributed Kalman filtering over sensor networks with unknown random link failures.  IEEE Control Systems Letters, 2(4):587–592, 2018.
  * [2] S. Battilotti, F. Cacace, and M. d’Angelo.  A stability with optimality analysis of consensus-based distributed filters for discrete-time linear systems.  Automatica, 129:109589, 2021.
  * [3] S. Battilotti, F. Cacace, M. d’Angelo, and A. Germani.  Asymptotically optimal consensus-based distributed filtering of continuous-time linear systems.  Automatica, 122:109189, 2020.
  * [4] S. Battilotti and M. d’Angelo.  Stochastic output delay identification of discrete-time gaussian systems.  Automatica, 109:108499, 2019.
  * [5] G. Battistelli and L. Chisci.  Kullback–Leibler average, consensus on probability densities, and distributed state estimation with guaranteed stability.  Automatica, 50(3):707–718, 2014.
  * [6] G. Battistelli, L. Chisci, G. Mugnai, A. Farina, and A. Graziano.  Consensus-based linear and nonlinear filtering.  IEEE Trans. on Automatic Control, 60(5):1410–1415, 2015.
  * [7] F.S. Cattivelli and A.H. Sayed.  Diffusion strategies for distributed Kalman filtering and smoothing.  IEEE Trans. on Automatic control, 55(9):2069–2084, 2010.
  * [8] F.R.K. Chung.  Spectral graph theory, volume 92.  American Mathematical Soc., 1997.
  * [9] M. Gao, Y. Niu, and L. Sheng.  Distributed fault-tolerant state estimation for a class of nonlinear systems over sensor networks with sensor faults and random link failures.  IEEE Systems Journal, 2022.
  * [10] A. Ge, Q.-L. Han, X.-M. Zhang, L. Ding, and F. Yang.  Distributed event-triggered estimation over sensor networks: A survey.  IEEE Trans. on Cybernetics, 50(3):1306–1320, 2020.
  * [11] X. Ge, Q.-L. Han, and Z. Wang.  A dynamic event-triggered transmission scheme for distributed set-membership estimation over wireless sensor networks.  IEEE Trans. on Cybernetics, 49(1):171–183, 2017.
  * [12] Y. Guan and X. Ge.  Distributed attack detection and secure estimation of networked cyber-physical systems against false data injection attacks and jamming attacks.  IEEE Trans. on Signal and Information Processing over Networks, 4(1):48–59, 2017.
  * [13] S. He, H.-S. Shin, S. Xu, and A. Tsourdos.  Distributed estimation over a low-cost sensor network: A review of state-of-the-art.  Information Fusion, 54:21–43, 2020.
  * [14] R.A. Horn and C.R. Johnson.  Matrix analysis.  Cambridge university press, 2012.
  * [15] H. Jin and S. Sun.  Distributed filtering for multi-sensor systems with missing data.  Information Fusion, 86:116–135, 2022.
  * [16] A.T. Kamal, J.A. Farrell, and A.K. Roy-Chowdhury.  Information weighted consensus filters and their application in distributed camera networks.  IEEE Trans. on Automatic Control, 58(12):3112–3125, 2013.
  * [17] M. Kamgarpour and C. Tomlin.  Convergence properties of a decentralized Kalman filter.  In Proc. of the 47th IEEE Conf. on Decision and Control, pages 3205–3210. IEEE, 2008.
  * [18] D. Kempe, A. Dobra, and J. Gehrke.  Gossip-based computation of aggregate information.  In Proc. of the 44th IEEE Symposium on Foundations of Computer Science, 2003., pages 482–491. IEEE, 2003.
  * [19] W. Li, G. Wei, D.W.C. Ho, and D. Ding.  A weightedly uniform detectability for sensor networks.  IEEE Trans. on Neural Networks and Learning Systems, 29(11):5790–5796, 2018.
  * [20] Q. Liu, Z. Wang, X. He, and D.H. Zhou.  On Kalman-consensus filtering with random link failures over sensor networks.  IEEE Trans. on Automatic Control, 63(8):2701–2708, 2018.
  * [21] C.D. Meyer.  Matrix analysis and applied linear algebra, volume 71.  SIAM, 2000.
  * [22] R. Olfati-Saber.  Distributed Kalman filter with embedded consensus filters.  In Proc. of the 44th IEEE Conf. on Decision and Control, pages 8179–8184. IEEE, 2005.
  * [23] R. Olfati-Saber.  Distributed Kalman filtering for sensor networks.  In Proc. of the 46th IEEE Conf. on Decision and Control, pages 5492–5498. IEEE, 2007.
  * [24] R. Olfati-Saber.  Kalman-consensus filter: Optimality, stability, and performance.  In Proc. of the 48h IEEE Conf. on Decision and Control, pages 7036–7042. IEEE, 2009.
  * [25] A.H. Sayed.  Diffusion adaptation over networks.  In Academic Press Library in Signal Processing, volume 3, pages 323–453. Elsevier, 2014.
  * [26] I. Shames, T. Charalambous, C.N. Hadjicostis, and M. Johansson.  Distributed network size estimation and average degree estimation and control in networks isomorphic to directed graphs.  In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1885–1892. IEEE, 2012.
  * [27] S.P. Talebi and S. Werner.  Distributed Kalman filtering and control through embedded average consensus information fusion.  IEEE Trans. on Automatic Control, 64(10):4396–4403, 2019.
  * [28] S.P. Talebi, S. Werner, V. Gupta, and Y.-F. Huang.  On stability and convergence of distributed filters.  IEEE Signal Processing Letters, 28:494–498, 2021.
  * [29] V. Ugrinovskii.  Distributed robust filtering with H∞ consensus of estimates.  Automatica, 47(1):1–13, 2011.
  * [30] C. Wan, Y. Gao, X.R. Li, and E. Song.  Distributed filtering over networks using greedy gossip.  In 2018 21st International Conference on Information Fusion, pages 1968–1975. IEEE, 2018.
  * [31] S. Wang and W. Ren.  On the convergence conditions of distributed dynamic state estimation using sensor networks: A unified framework.  IEEE Trans. on Control Systems Technology, 26(4):1300–1316, 2017\.
  * [32] G. Wei, W. Li, D. Ding, and Y. Liu.  Stability analysis of covariance intersection-based Kalman consensus filtering for time-varying systems.  IEEE Trans. on Systems, Man, and Cybernetics: Systems, 50(11):4611–4622, 2018.
  * [33] Z. Wu, M. Fu, Y. Xu, and R. Lu.  A distributed Kalman filtering algorithm with fast finite-time convergence for sensor networks.  Automatica, 95:63–72, 2018.
  * [34] W. Yang, Y. Zhang, G. Chen, C. Yang, and L. Shi.  Distributed filtering under false data injection attacks.  Automatica, 102:34–44, 2019.
  * [35] D. Yu, Y. Xia, L. Li, and C. Zhu.  Distributed consensus-based estimation with unknown inputs and random link failures.  Automatica, 122:109259, 2020.
  * [36] P. Zhu, G. Wei, and J. Li.  On hybrid consensus-based extended Kalman filtering with random link failures over sensor networks.  Kybernetika, 56(1):189–212, 2020.