Robustness in Consensus Networks

arXiv:1802.07321v2 [cs.SY] 25 Feb 2018

T. Sarkar, M. Roozbehani, M. A. Dahleh

Abstract— We consider the problem of robustness in large
consensus networks that occur in many areas such as distributed optimization. Robustness, in this context, is the scaling of performance measures, e.g.: H2 –norm, as a function
of network dimension. We provide a formal framework to
quantify the relation between such performance scaling and
the convergence speed of the network. Specifically, we provide
upper and lower bounds for the convergence speed in terms of
robustness and discuss how these bounds scale with the network
topology. The main contribution of this work is that we obtain
tight bounds, that hold regardless of network topology. The
work here also encompasses some results in convergence time
analysis in previous literature.

I. I NTRODUCTION
The goal of this paper to develop a general framework to
assess robustness in large consensus networks. Robustness
quantifies how some performance measure scales with the
network dimension. Large networks have become ubiquitous
in many socioeconomic and engineering areas, e.g.: finance,
economics, transportation etc. Therefore, to guarantee graceful performance scaling as a function of network dimension
and its interconnections, there is a need to develop a general
framework for robustness analysis. We use the ideas introduced in [1] and extend them to consensus networks. It is
well known that convergence speeds of consensus networks
are limited by the proximity of the second largest eigenvalue
to unity. However, the precise relation between robustness
and convergence speed is still unclear. It should, however,
be clear intuitively that graceful performance scaling implies
“fast” convergence. In this work our goal is to study this
notion more precisely.
Many performance measures to capture dimension dependent scaling have been studied in [2], [3], [4]. Specifically,
in [2], H2 –norm based performance measures are studied.
H∞ based performance scaling, known as harmonic instability, is studied in [3] for the case of one-dimensional
transportation networks. A generalized framework for robustness of stable networks is provided in [1]. The focus
there has been limited to stable networks. The case of
robustness in consensus networks is studied in [5], [6], [7],
[8]. The work in [6], [7], [8] is limited to the case of
undirected networks. A class of performance measures called
schur convex systemic (SCS) are introduced there. These
performance measures have the property that they are schur
convex in the eigenvalues of the network. H2 –norm is used
as a performance measure for analyzing directed networks
in [5]; however they do not show any relation between
convergence speed and network robustness. Additionally, the
analysis there is based on a non-unique reduction of the
network, which is different from the framework we develop
here.
The convergence speeds for stochastic matrices has been
widely studied (See [9], [10], [11], [12] and references
T. Sarkar, M. Roozbehani, M. A. Dahleh are with the EECS Department,
Massachusetts Institute of Technology, Cambridge, MA 02139 USA (e-mail:
tsarkar, mardavij,dahleh@mit.edu).

therein). Specifically, [11] studies with convergence speeds in
consensus networks that are characterized by nodal degrees.
The work in [11], [12], [13] also deal with the case when
the network topology is time varying. A primary motivation
of previous literature has been to analyze, for e.g., if a
distributed consensus dynamics converges geometrically. Let
us denote by dt as the distance to consensus, where dt <
1/16 implies convergence. Further assume that dt ≤ αt ,
then it is clear that if α < 1 the convergence is geometric.
When α is a function of the network dimension then so
does the convergence time, i.e., t∗ at which dt∗ < 1/16. We
are specifically interested in the case when α varies with
network dimension. The network architectures for which
such dependence is known are limited, and the method of
analyses do not extend to general structures.
In this work we seek to obtain a relation between the
aforementioned convergence time and dimension dependent
performance scaling in networks. In previous literature such
scaling has been attributed to network interconnections and
studies there have resulted in more “robust” network design.
We believe that an understanding of robustness in the context
of consensus networks will help in areas such as identification of links that slow convergence. Deriving from results
in [1], we demonstrate that there exists a network projection
which is equivalent to the consensus network. We will then
show that the robustness of this projected network is closely
related to the convergence time of its consensus counterpart.
Such an alternate formulation is needed because a consensus
network is marginally stable, and most performance measures require network stability. The main contribution of this
work is that we provide a general set of tools that help us
connect the convergence time of a consensus time to the
“convergence” time (to origin) of a stable network, which can
then be measured by a concrete algebraic quantity – which
we refer to as robustness. Further, the framework studied
here is not limited by network architecture as in previous
cases, and can be extended to general time varying or random
networks.
The paper is organized as follows – in section II we
introduce some mathematical notation. Section III develops
the model and reviews some results in consensus networks
and network robustness. In Section IV we state and prove our
main result. Specifically, we show how convergence time can
be interpreted as a measure of robustness. We present some
examples in Section V that demonstrate the tightness of our
bounds. Finally we conclude in Section VI.
II. M ATHEMATICAL N OTATION
Matrix Theory: A vector v ∈ Rn×1 is of the form
[v1 , . . . , vn ]T , where vi denotes the ith element, unless specified otherwise. The vector 1 is the all 1s vector of appropriate
dimension; to specify the dimension we sometimes refer to
it as 1n , where it is a n × 1 vector. Similarly, we will refer
to a n × n matrix A as An when we want to specify its
dimension. For a matrix, A, we denote by ρ(A) its spectral

radius, and by σi (A) the ith largest singular value of A. I is
the identity matrix of appropriate dimension. The Lp norm
of a matrix, A, is given by ||A||p = supv ||Av||p /||v||p and
more generally,
||A||p→q = sup ||Av||q
||v||p ≤1

Finally, Qn = In − 1n 1Tn /n is the projection matrix. A
network is Schur stable (or simply stable) if ρ(A) < 1.
Order Notation: For functions, f (·), g(·), we have
f (n) = O(g(n)), when there exist constants C, n0 such that
f (n) ≤ Cg(n) for all n ∈ N > n0 . Further, if f (n) =
O(g(n)), then g(n) = Ω(f (n)). For functions g(·), h(·), we
have g(n) = Θ(h(n)) when there exist constants C1 , C2 , n1
such that C1 h(n) ≤ g(n) ≤ C2 h(n) for all n ∈ N > n1 .
Finally, for functions h1 (·), h2 (·), we have h1 (n) = o(h2 (n))
when limn→∞ |h1 (n)/h2 (n)| = 0.
Graph Theory: A graph is the tuple G = (VG , EG , wG ),
where VG = {v1 , v2 , . . . , vn } represents the set of nodes and
EG ⊆ VG × VG represents the set of edges or communication
links. An edge or link from node i to node j is denoted
by e[i, j] = (vi , vj ) ∈ EG , and wG : EG → R. Denote by
AG the incidence matrix of G. A graph, G, is symmetric or
undirected if wG (vi , vj ) = wG (vi , vj ) for all 1 ≤ i, j ≤ |VG |.
G is induced by a matrix, An×n if VG = {1, . . . , n}, and
(i, j) ∈ EG if [A]ij 6= 0, and wG (i, j) = [A]ij .
Miscellaneous: Denote by P is the family of polynomials.
III. P RELIMINARIES
We follow a similar model framework to [1]. Consider the
following discrete time LTI dynamics:
x(k + 1) = A x(k) + ω δ(0, k), k ∈ {0, 1, 2, . . .}
T

(1)

Here x(k) = [x1 (k), . . . , xn (k)] is the vector of state
variables. A is the n × n state transition matrix. δ(0, k)
is the Kronecker delta function, with δ(0, 0) = 1 and
δ(0, k) = 0 ∀ k 6= 0 and ω = [ω1 , . . . , ωn ]T is exogenous to
the system. We further assume that x(0) = 0.
We impose the following assumptions on A and ω (if random) throughout the paper unless explicitly stated otherwise.
Assumption 1: A is a primitive (aperiodic and irreducible) row stochastic matrix.
Assumption 2: ω is an n × 1 random vector with
E[ωω T ] = In×n and E[ω] = 0.
Definition 1: A signal, w(k), is a shock if w(k) = 0 for
all k > 0 but w(0) 6= 0.
Then w(k) = ωδ(0, k) in Eq. (1) is a shock.
Definition 2: A consensus network, N (A; G), is a graph
G = (VG , EG , wG ), where VG = {1, 2, . . . , n}, and for each
node, i ∈ VG , there is an associated dynamical behavior,
i → xi (·), given by Eq. (1). Further, wG (i, j) = [A]ij for all
1 ≤ i, j ≤ n. The graph G is sometimes referred to as the
network topology.
Remark 1: The focus of this paper will be on “large”
consensus networks. Following the discussion in [1], we
will denote a large network A by a sequence of networks
{An }∞
n=1 that have a “fixed” topology but growing network
dimension.
Remark 2: Based on Definition 2 it is obvious that a
network matrix A uniquely defines the consensus network
N (A; G). So for shorthand, we will refer to the network
N (A; G) by its network matrix A.

Throughout this paper, we use some commonly encountered network topologies. For these topologies, the network
matrices are of the form An = Dn−1 An , where Dn =
Diag(d1 , d2 , . . . , dn ), An is the incidence matrix and di is
the degree of node i. Further, i → j denotes a directed edge
from i to j, i.e., [An ]ij = 1 but [An ]ji = 0. The network
topologies considered in this work are shown in Fig. 1.

Fig. 1: Different Network Topologies
Now, under Assumption 1, we have the following result
on the steady state dynamics of a consensus network.
Proposition 1 (Perron-Frobenius Theorem): For
a
stochastic matrix A we have that limk→∞ Ak = 1π T , where
π T A = π T , i.e., π is the invariant distribution. Additionally,
πi > 0 for all i ∈ {1, 2, . . . , n}.
It is important to note that Assumption 1 is a stronger
condition than ergodicity of A, i.e., there exists π such
that π T A = π. For example, consider the directed cycle
network DCn in Fig. 1. Then it is easy to see that πDCn =
(1/n)1. Further, DCnk 6= DCnk+1 for all k > 0, and in fact
DCnm×n = I for all m ∈ N. Thus limk→∞ DCnk does not
exist.
Remark 3: Throughout the paper we assume that Proposition 1 holds for all stochastic matrices considered unless
otherwise stated.
For the class of consensus networks we consider, to quantify
how “fast” they approach the invariant distribution we define
the notion of convergence time.
Definition 3: We define –convergence time, tA (), for
consensus network A, as
tA () = inf{k| ||Ak − 1π T ||∞ < }
where π is the invariant distribution of A. We say that
consensus has been reached for all k > t().
Further for the consensus network in Eq. (1) with an input
shock we have that
x(k) = Ak ω
lim x(k) = 1(π T ω)

k→∞

This means that as t → ∞, xi (k) → xj (k) for all i, j ∈
{1, 2, . . . , n}. Now, consider xQ (·)
xQ (k) = Qn Ak ω
where xQ (·) is the projection of x(·) onto the subspace
orthogonal to 1n , i.e., Q. Then it follows that
lim ||xQ (k)||∞ = 0

k→∞

It follows from Proposition 3 in [1] that this convergence is
exponential, i.e.,
lim ||(xQ (k))||1/k
∞ =α <1

k→∞

The goal of this work is to show that there exists a stable
large network whose robustness is equivalent to the 1/2–
convergence time of the consensus network. For completeness we define robustness for a large network (See [1]),
Definition 4: A large network, An , is (asymptotically)
robust if we have:
• Network matrix, An , is stable for each n
• trace(P (An )) = O(p(n))
Here p(·) ∈ P and An P (An )ATn + I = P (An ).
Definition 5: The pair (|| · ||, P (An )) is a robustness
measure for the network matrix An if || · || ∈ C where
C = {|| · || | (p(n))−1 trace(P (An )) ≤ ||A||,
||A|| ≤ (p(n))trace(P (An ))}
and p(·) ∈ P.
Examples of norms that can be considered as part of robustness measures include Lp –induced matrix norms, Schatten
norms etc. Consequently, we call a large network, An , fragile
if it lacks robustness in the sense of super-polynomial or
exponential scaling of trace(P (An )).
Remark 4: Definition 4 uses the “controllability” gramian
(assuming B = I), P (An ), i.e.,
An P (An )ATn + I = P (An )
In [1], [14], robustness measure was instead based on the
“observability” gramian (assuming C = I), i.e.,
ATn P O (An )An + I = P O (An )
From the perspective of asymptotic robustness, the type
of gramian used is not important as trace(P (An )) =
trace(P O (An )). With some more effort similar bounds (as
shown in this paper) can be obtained for P O (An ).
IV. C ONVERGENCE T IME AS ROBUSTNESS
In this section we will describe the relationship between
the convergence time of a consensus network and the robustness of its stable, projected counterpart. We first characterize
this stable network, then we formalize the relationship that
we seek between robustness and convergence time, and
finally we show how the two are connected. Such an analysis
is similar to the one introduced in [1] for consensus networks.
However, here we provide a formal justification of why such
a projection is appropriate.
A. Projected Network Dynamics
Consider the consensus network dynamics in Eq. (1), we
define the projected network dynamics (for the consensus
network) as follows
Definition 6: The projected network dynamical behavior,
ProjΠ (A), for the network matrix A is given by,
xΠ (k) = ΠAxΠ (k − 1) + w(k)
where Π is the projection operator and ΠA is the projected
network matrix.
In this work we are interested specifically in ProjQ (A) where
Q = I − 11T /n. We show next the stability of the network
dynamics ProjQ (A).

Proposition 2: The projected network matrix QA is stable.
Proof: We first show that (QA)k = QAk . For k = 1
this is trivially true. Now, assume that this holds for some
k = k0 , then we have for (QA)k0 +1 that
(QA)k0 +1 = (QA)k0 QA
= QAk0 QA
Now, since Ak0 is also row stochastic we have that Ak0 Q =
Ak0 − 11T /n (since Ak0 1 = 1). Then, QAk0 Q = QAk0
since Q is orthogonal to 11T /n by definition. Thus we have
(QA)k0 +1 = QAk0 +1 and our assertion is true.
From Theorem 4.9 in [10] we have that
||Ak − 1π T ||∞ ≤ 2Cαk =⇒ Ak = 1π T + W
where ||W ||∞ ≤ 2Cαk and α ∈ (0, 1), then it follows that
lim ||QAk ||1/k
∞ =α <1

k→∞

Since QAk = (QA)k we have ρ(QA) < 1 and QA is stable.
The proof of Proposition 2 shows that QAk = (QA)k .
Then under the same input shock, xQ (k) (generated by
ProjQ (A)) is identical to xQ (k), that is the projection of x(k)
onto Q generated in Eq. 1, i.e., the projection of network
output is equivalent to output of the network projection. This
commutativity between the projection and network operators
is what helps us connect the notions of robustness and
convergence time.
Since the projected network dynamical behavior,
ProjQ (A), is stable, its gramian exists and is unique. This
is given by the solution to the matrix equation
(QA)X(QA)T + I = X
The solution will be denoted as X = P (QA). In this
discussion we showed how for every consensus network that
we consider, there exists a stable projected network. In the
following sections we will show that there exists a strong
relationship between the –convergence time of a consensus
network and the robustness of its projected network.
B. Convergence Time in Consensus Networks
We defined the –convergence time of a consensus network to measure the speed of convergence to the invariant
distribution. However, it seems that this speed depends on .
Here we show that the choice of  is not important as long
as it is less than a certain threshold.
Proposition 3: For a consensus network, An ,
tAn (1/2) = Θ(p(n))
then
tAn () = Θ(p(n))
for all  < 1 (uniformly).
Proof: We first consider the case of  < 1/2. If
tA (1/2) = Θ(p(n)) this means that there exists k = Θ(p(n))
such that
||Ak − 1π T ||∞ ≤ (1/2)
Now it follows from Aτ 1π T = 1π T and submultiplicativity
that
||Ak+τ − 1π T ||∞ ≤ ||Ak − 1π T ||∞

Let a = inf{t | t ∈ N and t ≥ log (1/2)}, then we have that
||A

ka

T

a

− 1π ||∞ ≤ (1/2)
≤

Thus tA () = O(p(n)) but tA (1/2) = Θ(p(n)) and since
 ≤ 1/2 =⇒ tA () = Θ(p(n)) (tA (·) is non-increasing
because ||QAk ||∞ is non-increasing in k).
Next assume that tAn (1/2) = Θ(p(n)) but tAn () =
log (2)
o(p(n)) for some 1/2 <  < 1. Then pick any a > log
(1/) ,
then tAn (a ) = o(ap(n)) =⇒ tAn (1/2) = o(p(n)) because
tA (·) is non-increasing. But this is a contradiction.
Proposition 3 states that as long as  does not depend on
the network dimension the convergence times are equal in
an order sense. For example if  = 3/4, then it is the same
as  = 1/2 (in an order sense). However, in the definition of
–convergence time, it is possible that tA () > 0 for  > 1
and therefore it is important to consider an “appropriate”
class of  where the equivalence of Proposition 3 holds. For
example, consider the following stochastic network, Bn , and
α = 1 − 1/(n − 1)
Bn = αn I + (1 − αn )11T /n
The invariant distribution of Bn = 1/n, and further since
it is a positive matrix, therefore Perron Frobenius theorem
holds. Then it follows that,
Proposition 4: For the network, Bn , we have
tBn (2 − 4/n) = 1
but

−1

if and only if for some k = Θ(p(n)) we have
||QAk ||∞ ≤ 1/2
Proof: If tA (1/2) = Θ(p(n)), then from Proposition 3
it follows that tA (1/4) = Θ(p(n)), i.e., there exists k =
Θ(p(n)) such that
||Ak − 1π T ||∞ ≤ 1/4
Then QAk = Q(Ak − 1π T ) (since Q1π T = 0) and we have
||Q(Ak − 1π T )||∞ ≤ ||Q||∞ ||(Ak − 1π T )||∞
≤ 1/2
The last inequality follows from the fact ||Q||∞ = 2.
Next assume that QAτ ≤ 1/2 for some τ = Θ(p(n)), and
since QA2τ = (QAτ )2 from Proposition 2, it follows that
QAk ≤ 1/4 for k = Θ(p(n)). Then we have that for some
Wk , in the space orthogonal to 11T and ||Wk ||∞ ≤ 1/4, that
Ak = 1δkT + Wk
=⇒ Ak+α = Aα 1δkT + Aα Wk
Now, we will show that δk and π do not vary too much in
norm.
lim Ak+α = 1δkT + 1π T Wk

α→∞

1π T = 1δkT + 1π T Wk
||1π T − 1δkT ||∞ ≤ (1/4)||1π T ||∞
= (1/4)
Then we have ||Ak −1π T ||∞ ≤ ||1δk −1π T ||∞ +||Wk ||∞ ≤
(1/2). This means that tA (1/2) = O(p(n)).

tBn (e ) = Θ(n)
Proof: We first show that Bnk = αnk I + (1 − αnk )11T /n.
For the base case k = 1, it is trivial. We assume that this
holds for k = k0 , then

We will show that the convergence time of the consensus
network depends on robustness of the projected network and
some variational properties of the consensus network, i.e.,

Bnk0 +1 = (αk0 I + (1 − αk0 )11T /n)(αI + (1 − α)11T /n)

VAR1 (A)||P (QA)||(1) ≤ tA (1/2) ≤ VAR2 (A)||P (QA)||(2)

= (αk0 +1 I + (1 − αk0 +1 )11T /n)
Thus our inductive hypothesis is true for k0 + 1, and hence
for all k ∈ N.
Now, observe that
||B k − 11T /n||∞ = αk ||I − 11T /n||∞
= 2αk (1 − 1/n)
Then for k = 1, we get that ||B − 11T /n||∞ = 2(1 −
2/n). It is easy to verify that for k = 2(n − 1) we see that
||B k − 11T /n||∞ < e−1 but for k = n − 1 we have that
||B k − 11T /n||∞ > e−1 . Thus, tBn (e−1 ) = Θ(n).
We have shown that tA () are essentially equal (in an order
sense) for every  in a certain class; further notice that the
class of { < 1 (uniformly)} is not very restrictive given that
||Q||∞ = 2, ||Ak ||∞ = 1 for all k. Following this whenever
we say convergence time of A, we will mean tA (1/2).
Next, we relate convergence time to the dynamics of the
projected network. This will be the first step towards making
connections between the robustness of the projected network
and convergence time of the original consensus network.
Theorem 1: For a consensus network, A, we have that
tA (1/2) = Θ(p(n))

Here (|| · ||(i) , P (QA)) is some appropriately chosen robustness measure and VARi (A) is a measure of the “variance” in
A. It will turn out that in some non-trivial cases robustness
meets convergence time with equality (in an order sense).
We describe these quantities more precisely in the following
discussion.
C. Convergence Time as a Robustness Measure
In the preceding discussion, we related the convergence
time to the norm properties of the projected network dynamics (specifically ||QAk ||∞ ). It can be shown that similar
bounds can also be obtained for the projection Qπ = I−1π T .
In fact, there is some hope that these are stronger results
compared to those given by Q. However for the sake of
completeness we limit ourselves to results for Q.
Assumption 3:
sup |aij − (1/n)
ij

n
X

aij | > 0

i=1

i.e., all rows are not identical and consensus has not been
reached.
This assumption is not restrictive as a consensus network
with identical rows would imply that tA () = 1 for all 
which is not a very interesting case. For the purpose of our
main theorem we define a variance parameter.

Definition 7:
Var0 (QA) = sup |ai,j − (1/n)
i,j

n
X

aij |

i=1

Theorem 2: Let tA (1/2) = t∗ = Θ(p(n)), then we have
that
(1/n)trace(P (QA)) ≤ 1 + Var0 (A)Θ(p(n))
π

max
Θ(p(n))
1 + (1/n)Θ(p(n)) ≤||P (QA)||2 ≤ 1 +
πmin
where (πmax , πmin ) = (maxi πi , mini πi ).
The proof of this can be found in Section VII-B.
Var0 (A) parameter measures the furthest any element in
the stochastic matrix is away from its column average. If all
elements are very close to the columnar average, then this
implies consensus from preceding results. In such a case
the average is the stationary value. Another point to note is
that the bounds are not tight. However, they show that the
gramian measures the convergence time reasonably well.
In previous literature, there exist bounds on convergence
times of the form
−1

tA (1/2) ≤ C(1 − |λ2 |)

Where C can be a function of network size. General lower
bounds are obtained in terms of bottleneck ratio, which is a
discrete optimization problem (See Chapter 7 [10]). Further
to obtain tighter and/or lower bounds on convergence times,
special structure was required. In this work we find explicitly
characterize the effect of network dimension in terms of
robustness and “variance”. Moreover, our bounds do not
require any special structural constraints. Our result can be
summarized as follows
trace(P (QA))
= O(tA (1/2))
nVar0 (A)
n||P (QA)||2 = Ω(tA (1/2))
V. E XAMPLES
We will present a few examples remarking on the tightness
of our bounds. First we define a class of derived networks
that will be useful in our discussion.
Definition 8: For any network A, its lazy version is given
by
AL
n = (1/2)(An + I)
The lazy version is useful because first, AL
n is aperiodic and
irreducible even if An is not and second, it preserves the
topological and spectral properties of An .
Cycle

Star

Fig. 2: Lazy versions of Network Topologies
A. Tightness of bounds
Consider the star network, Sn , and the cycle network, Cn ,
in Fig. 1. We consider the lazy versions of these networks
denoted by SnL , CnL respectively. Then,

Proposition 5: For the lazy random walk networks, we
have trace(CnL ) = Θ(n3 ), ||P (CnL )||2 = Θ(n2 ), and
trace(SnL ) = Θ(n), ||P (SnL )||2 = Θ(1).
Quite surprisingly it turns out that the star network exhibits
no scaling with network dimension. The centrality in
star topology lends fast “mixing” property. The cycle
network has poor “mixing” properties and as a result
the robustness measure scales quadratically with network
dimension. Further these robustness measures are identical
to convergence times for these networks (See [10]).
Proof:
Star Network

0.5
0.5

SnL =  .
 ..
0.5

1
2(n−1)

0.5
..
.
0

Now, the projection of SnL on Q

0
0
1
0 12 − 2(n−1)

L
QSn =  ..
..
.
.
1
0
− 2(n−1)

...
...
..
.
...

1
2(n−1)



0
..
.
0.5






is
...
...
..
.
...

0



1

− 2(n−1)


..

.
1
1
2 − 2(n−1)

Now,
||P (QSnL )||2 ≤ 1 + ||QSnL ||22 ||P (QSnL )||2
This follows from
AP (A)AT +I = P (A) =⇒ ||AT P (A)A||2 +1 ≥ ||P (A)||2
From the structure of QSnL it follows that ||QSnL ||2 = 0.5
and then it follows that ||PΠ (SnL )||2 ≤ 1/(1 − ||QSnL ||22 ).
Further, ||P (QSnL )||2 ≥ ||Π||2 = 1 and our claim follows.
Cycle Network
0.5 0.25 . . .
0.25 0.5 . . .
 .
..
..
CnL = 
.
.
 ..
 0
0
...
0.25
0
...


0
0
..
.
0.5
0


0.25
0 
.. 

. 
0.25
0.5

T
AL
n = 1/2In×n + (1/4)(DLn + DLn )

Here DLn is the matrix with 1s on the off-diagonal. This is
a circulant matrix (and symmetric). From [15], we have that
2
ρ2 (AL
n ) = cos (π/n)

Additionally, the eigenvalue corresponding to ρ2 (AL
n ) is
positive =⇒ ||PΠ (An )||2 = Θ((1 − cos2 (π/n))−1 ) =
Θ((sin2 (π/n))−1 ) = Θ(n2 ). The argument for trace follows
from symmetry.
The proof of the preceding propositions show that
tSnL (1/2) = Θ(1) and tCnL (1/2) = Θ(n2 ) (this follows
from Section 5.3 in [10]). To show that some of the bounds
in Theorem 2 are tightly achieved we provide a plot of
||P (QA)||2
tA (1/2) with the number of nodes in the network (Fig. 3).
We observe that this ratio remains a constant for the two
topologies. This is a general trend we observe for common
examples. However, we have been unable to tighten our

bounds for general consensus topologies.

Fig. 3:

σ1 (P (QA))
tA (1/2)

vs Number of Nodes

Next, we provide upper bounds on convergence times for
a class of networks discussed in [12].
Definition 9: A consensus network, An , is an undirected
flocking network if
An =

Dn−1 An

where Dn is the matrix with degree of each node on the
diagonal and An is the incidence matrix. Further, [An ]ij =
[An ]ji .
We will now provide a bound for the convergence time
of a connected undirected flocking network. This result also
readily follows from the Theorem 1 in [12].
Proposition 6: Any undirected flocking consensus network, An , is robust. Further ||P (QAn )|| = O(n2 ).
Proof: An undirected flocking matrix, as in [12], has
a symmetric adjacency matrix. Then, we know that An =
Dn−1 An can be symmetrized to
Sn = Dn−1/2 An Dn−1/2 = Dn1/2 An Dn−1/2
0

0

Next note that P (QAn ) = (QAn )T P (QAn )(QAn )+I can
0
be alternately written P = ATn P An +Q, i.e., P = P (QAn ).
Note that this is different from out traditional definition
of gramian but in terms of the trace they are identical, as
discussed before. Then we have,
P = ATn P An + Q
P = ATn Dn1/2 Dn−1/2 P Dn−1/2 Dn1/2 An + Q
Dn−1/2 P Dn−1/2 = SnT Dn−1/2 P Dn−1/2 Sn + Dn−1/2 QDn−1/2
PD = SnT PD Sn + QD
1/2

Here QD is orthogonal to Dn [1, 1, . . . , 1]T , which is the
eigenvector of Sn corresponding to the eigenvalue 1. Since
Sn is symmetric, the second greatest eigenvalue (in magnitude) will be in an orthogonal subspace, i.e., in QD .
Since Sn is symmetric the singular values of Sn are the
eigenvalues of Sn (albeit some permutation). From [16], we
know that for a flocking matrix, λ2 (Sn ) ≤ 1 − 1/n, where
λ2 (A) is the second largest eigenvalue (in magnitude) of A.
1/2
1/2
Then, we get that σ1 (PD ) = O(n), further Dn PD Dn =
2
P (QAn ) =⇒ σ1 (P (QAn )) = O(n ).
Note from Theorem 1 in [12], we have that the convergence
time is O(n3 ). Further, since it follows from Proposition 6
that n||P (QAn )||2 = O(n3 ), our bound in Theorem 2 is
tight from below.

VI. C ONCLUSIONS
In this work we showed that convergence time for consensus networks can be represented as robustness in its
projected counterpart. This gave us a general framework,
one that is not limited by the type of consensus network,
to estimate convergence times. The bounds obtained here
do not assume knowledge of the invariant distribution. We
believe that such a relation will help in analyzing cases when
the network is time varying or random. For example, in [12]
it was shown that there exist time varying networks where
convergence is exponential. Such a result may follow from
our framework in the following way – since it is clear that
exponential convergence time implies lack of robustness,
then all we have to do is study the scaling of H2 –norm
with network size. Another future direction may be to study
network projection when the invariant distribution is known,
i.e., when Q is replaced by Qπ = I − 1π T where π is the
invariant distribution. For such projections, we believe that
the bounds in Theorem 2 can be made tighter.
R EFERENCES
[1] T. Sarkar, M. Roozbehani, and M. A. Dahleh, “Robustness scaling in
large networks,” in 2016 American Control Conference (ACC), July
2016, pp. 197–202.
[2] Q. Huang, Y. Yuan, J. Gonalves, and M. A. Dahleh, “H2 norm based
network volatility measures,” in 2014 American Control Conference,
June 2014, pp. 3310–3315.
[3] I. Herman, D. Martinec, Z. Hurak, and M. Sebek, “Nonzero bound
on fiedler eigenvalue causes exponential growth of h-infinity norm
of vehicular platoon,” CoRR, vol. abs/1409.4605, 2014. [Online].
Available: http://arxiv.org/abs/1409.4605
[4] D. Acemoglu, V. Carvalho, A. Ozdaglar, and A. Tahbaz-Salehi, “The
network origins of aggregate fluctuations,” Econometrica, vol. 80,
no. 5, pp. 1977–2016, 2012.
[5] G. F. Young, L. Scardovi, and N. E. Leonard, “Robustness of noisy
consensus dynamics with directed communication,” in American Control Conference (ACC), 2010. IEEE, 2010, pp. 6312–6317.
[6] M. Siami and N. Motee, “Systemic measures for performance and
robustness of large-scale interconnected dynamical networks,” in Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on.
IEEE, 2014, pp. 5119–5124.
[7] ——, “Fundamental limits and tradeoffs on disturbance propagation in
linear dynamical networks,” IEEE Transactions on Automatic Control,
vol. 61, no. 12, pp. 4055–4062, 2016.
[8] ——, “Growing linear consensus networks endowed by spectral systemic performance measures,” arXiv preprint arXiv:1706.07832, 2017.
[9] I. C. Ipsen and T. M. Selee, “Ergodicity coefficients defined by vector
norms,” SIAM Journal on Matrix Analysis and Applications, vol. 32,
no. 1, pp. 153–200, 2011.
[10] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov chains and mixing
times. American Mathematical Soc., 2009.
[11] A. Olshevsky and J. N. Tsitsiklis, “Convergence speed in distributed
consensus and control,” arXiv preprint math/0612682, 2006.
[12] ——, “Degree fluctuations and the convergence time of consensus
algorithms,” Automatic Control, IEEE Transactions on, vol. 58, no. 10,
pp. 2626–2631, 2013.
[13] ——, “On the nonexistence of quadratic lyapunov functions for consensus algorithms,” IEEE Transactions on Automatic Control, vol. 53,
no. 11, pp. 2642–2645, 2008.
[14] T. Sarkar, M. Roozbehani, and M. A. Dahleh, “Asymptotic network
robustness,” arXiv preprint arXiv:1712.05273, 2017.
[15] R. M. Gray, “Toeplitz and circulant matrices: A review,” Foundations
and Trends in Communications and Information Theory, vol. 2,
no. 3, pp. 155–239, 2006. [Online]. Available: http://dx.doi.org/10.
1561/0100000006
[16] M. Cao, D. A. Spielman, and A. S. Morse, “A lower bound on convergence of a distributed network consensus algorithm,” in Decision and
Control, 2005 and 2005 European Control Conference. CDC-ECC’05.
44th IEEE Conference on. IEEE, 2005, pp. 2356–2361.
[17] F. D. M. Perı́a, P. G. Massey, and L. E. Silvestre, “Weak matrix
majorization,” Linear algebra and its applications, vol. 403, pp. 343–
368, 2005.
[18] E. Marchi, “What is the reciprocal of a function concave or convex?”
2014.

VII. A PPENDIX
A. Results
For strong bounds on convergence times in terms of the
gramian, we need projection operator Qπ = I − 1π T . We
briefly show that all the properties of the projection QA can
be summarized for Qπ A
k
k
• Qπ A = (Qπ A) . This follows because
Qπ A = AQπ
•

P (QA) 

Qπ A is Schur stable. This follows from Theorem 4.9
in [10].
lim ||Qπ Ak ||1/k < 1

k→∞
•
•

Theorem 1 holds by definition.
Qπ Am+n = Qπ Am Qπ An . This follows because of the
projection property
Q2π = Qπ

P (QA) = I +
trace(P (QA)) = n +

k

k T

T

Q(A )(A ) Q

k=1
∞
X

n
X

(k)

X

k=1 i,j=1
n
∞ X
X

i=1

|aij − (1/n)

≤ n(1 + sup
i

(k)

k=1 j=1

aij |2 )

i=1

≤ n(1 + 2||QA||max ×
∞ X
n
n
X
X
(k)
(k)
|ai∗ j − (1/n)
alj |)
sup
i

k=1 j=1
∗

rmt∗ ,i =

i

(k)

|aij − (1/n)

k=mt∗ j=1

X

aij |

i=1

rmt∗ = sup rmt∗ ,i ≤ (1/2)m t∗

(k)

|aij − (1/n)

m=0

Then it follows that
(1/n)trace(P (Qπ A)) = 1 + ||QA||max O(p(n))
Consider the two scenarios – when ||QA||max = o(1/n) and
||QA||max = Ω(1/n). In the first case, when ||QA||max =
o(1/n), notice that ||QA||∞ = o(1) and we are done by
definition, i.e., consensus has been reached. The interesting
case is when ||QA||max = Ω(1/n), we start “away” from
consensus. Indeed, a similar bound could have been obtained
by taking Qπ instead of Q. It turns out that
trace(P (Qπ A)) ≥ trace(P (QA))

aij |2

i=1

Here t∗ + 1 is the first time when ||QA||∞ ≤ 1/4. Then
the l2 –norm of the row with l1 –norm > 1/4 will be at least
(1/4)n−1 (By Jensen’s Inequality).
For an upper bound on ||P (QA)||2 , we see that

||P (QA)||2 ≤
||P (QA)||2 ≤
||P (QA)||2 ≤

∞
X
k=0
∞
X
k=0
∞
X
k=0
∞
X

QAk (Ak )T Q
||QAk (Ak )T Q||2
||QAk (Ak )T Q||∞
||QAk ||∞ ||(Ak )T Q||∞

k=0
∞
X

||P (QA)||2 ≤ 2

||QAk ||∞ ||(Ak )T ||∞

k=0

Now ||(Ak )T ||∞ ≤ (πmax /πmin ), this follows from the fact
that
||π T Ak ||∞ ≤ πmax

≤ n(1 + Θ(1)||QA||max t∗ )

X

|amj −

≥ 1 + Θ(p(n))n−1

Since we have,
rmt∗ )

(t)

j=1

(1/4)n−1

π T Ak = π T
∞
X

Pn

k=1

i

trace(P (QA)) ≤ n(1 + 2||QA||max

∞ X
n
X
k=1 j=1

t∗
X

l=1

Let t∗ be when ||QAt ||∞ ≤ 1/2. By definition t∗ =
Θ(p(n)), then it follows from the monotonicity of ||QAk ||∞
in k and the fact that ||QAm+n ||∞ ≤ ||QAn ||∞ ||QAm ||∞ ,
(m+1)t∗ n
X X

σ1 (P (QA)) ≥ 1 + sup

P (QA) =
X

QAi (AT )i Q

Now, the diagonal term of [QAt (AT )t Q]mm =
P
(1/n) i=1 aij |2 is

aij |2

|aij − (1/n)

k
X
i=0

≥1+

B. Proof of Theorem 2
First, we show a lower bound on the convergence time.
∞
X

Thus the lower bound is tighter for Qπ .
For the other direction, we design a P
construction.
n
First observe that, we need a lower bound
j=1 |aij −
Pn
(1/n) i=1 aij |2 . Although we have a lower bound for the
l1 by design (> 1/4), it is not that trivial to obtain such a
bound for the l2 case. Consider again the gramian, for any
k we have

||πmin ||||(Ak )T ||∞ ≤ πmax
Then our claim follows.

