1

Abstraction of Linear Consensus Networks with Guaranteed
Systemic Performance Measures

arXiv:1709.01150v1 [] 4 Sep 2017

Milad Siami† and Nader Motee⋆

Abstract—A proper abstraction of a large-scale linear consensus network with a dense coupling graph is one whose number of coupling
links is proportional to its number of subsystems and its performance is
comparable to the original network. Optimal design problems for an abstracted network are more amenable to efficient optimization algorithms.
From the implementation point of view, maintaining such networks
are usually more favorable and cost effective due to their reduced
communication requirements across a network. Therefore, approximating
a given dense linear consensus network by a suitable abstract network is
an important analysis and synthesis problem. In this paper, we develop
a framework to compute an abstraction of a given large-scale linear
consensus network with guaranteed performance bounds using a nearlylinear time algorithm. First, the existence of abstractions of a given
network is proven. Then, we present an efficient and fast algorithm
for computing a proper abstraction of a given network. Finally, we
illustrate the effectiveness of our theoretical findings via several numerical
simulations.

I.

I NTRODUCTION

Reducing design complexity in interconnected networks of dynamical systems by means of abstraction are central in several real-world
applications [1]–[6]. Various notions of abstractions for dynamical
systems have been widely used by researchers in the context of
control systems in past decades, see [7]–[10] and references in there,
where the notion of reduction mainly implies projecting dynamics of
a system to lower dimensional state spaces. In this paper, we employ
a relevant notion of abstraction in the context of interconnected
dynamical network: for a given dynamical network that is defined
over a coupling graph, find another dynamical system whose coupling
graph is significantly sparser and its performance quality remains
close to that of the original network. In this definition, abstraction can
be regarded as a notion of network reduction. There are several valid
reasons why reduction in this sense is useful in design, maintenance,
and implementation of dynamical networks. Real-time generation
of state estimation in large-scale dynamical networks can be done
much more efficiently and faster if proper abstractions are utilized.
Optimal control problems that involve controller design, feedback
gain adjustments, rewiring existing feedback loops, and etc. are more
amenable to efficient computational tools that are specifically tailored
for optimization problems with sparse structures. In security- or
privacy-sensitive applications such as formation control of group of
autonomous drones, it is usually required to minimize communication
requirements across the network to reduce risk of external intrusions. In power network applications, network authorities periodically
provide access to their network data and parameters for academic
(or public) studies and evaluations. In order to reduce possibility of
planned malicious attacks, network authorities can perform abstractions in order to hide actual values of parameters in their networks
by preserving all other important characteristics of the network that
interest researchers.
† M. Siami is with the Institute for Data, Systems, and Society,
Massachusetts Institute of Technology, Cambridge, MA 02319. Email:
siami@mit.edu.
⋆ N. Motee is with the Department of Mechanical Engineering and
Mechanics, Packard Laboratory, Lehigh University, Bethlehem, PA 18015.
Email: motee@lehigh.edu.

The goal of this paper is to address the abstraction problem
for the class of linear consensus networks. In [1], we introduce
a class of operators, so called systemic performance measure, for
linear consensus networks that provides a unified framework for
network-wide performance assessment. Several existing and popular
performance measures in the literature, such as H2 and H∞ norms
of a consensus network from a disturbance input to its output, are
examples of systemic performance measures. This class of operators
is obtained through our close examination of functional properties of
several existing gold standard measures of performance in the context
of network engineering and science. An important contribution of
this reference paper is that it enables us to optimize performance
of a consensus network solely based on its intrinsic features. The
authors formulate several optimal design problems, such as weight
adjustment as well as rewiring of coupling links, with respect to
this general class of systemic performance measures and propose
efficient algorithms to solve them. In [11], [12], we quantify several
fundamental tradeoffs between a H2 -based performance measure and
sparsity measures of a linear consensus network. The problem of
sparse consensus network design has been considered before in [5],
[13]–[15], where they formulate an ℓ0 -regularized H2 optimal control
problem. The main common shortcoming of existing works in this
area is that they are heavily relied on computational tools with no
analytical performance guarantees for the resulting solution. More
importantly, the proposed methods in these papers mainly suffer from
high computational complexity as network size grows.
For a given linear consensus network with an undirected connected
graph, the network abstraction problem seeks to construct a new
network with a reasonably sparser graph compared to the original
network such that the dynamical behavior of the two networks
remains similar in an appropriately defined sense. We develop a
methodology that computes abstractions of a given consensus network
using a nearly-linear time Õ(m)1 algorithm with guaranteed systemic
performance bounds, where m is the number of links. Unlike other
existing work on this topic in the literature, our proposed framework:
(i) works for a broad class of systemic performance measures including H2 -based performance measures, (ii) does not involve any sort of
relaxations such as ℓ0 to ℓ1 ,2 (iii) provides guarantees for the existence
of a sparse solution, (iv) can partially sparsify predetermined portions
of a given network; and most importantly, (v) gives guaranteed levels
of performance. While our approach is relied on several existing
works in algebraic graph theory [16], [17], our control theoretic
contributions are threefold. First, we show that there exist proper
abstractions for every given linear consensus network. Second, we
develop a framework to compute a proper abstraction of a network
using a fast randomized algorithm. One of the main features of our
method is that while the coupling graph of the abstracted network
is a subset of the coupling graph of the original network, the link
weights (the strength of each coupling) in the sparsified network
1 We use Õ(.) to hide poly log log terms from the asymptotic bounds.
Thus, f (n) ∈ Õ (g(n)) means that there exists c > 0 such that f (n) ∈
O (g(n) logc g(n)).
2 We discuss some of the shortcomings of the ℓ /ℓ -regularization based
0 1
sparsification methods in Section VIII.

2

are adjusted accordingly to reach predetermined levels of systemic
performance. Third, we prove that our method can also be applied
for partial abstraction of large-scale networks, which means that we
can abstract a prespecified subgraph of the original network. This is
practically plausible as our algorithm can obtain an abstraction using
only spatially localized information. Moreover, this allows parallel
implementation of the abstraction algorithm in order to achieve
comparably lower time complexity.
II.

N OTATION AND P RELIMINARIES

The set of real, positive real, and strictly positive real numbers are
represented by R, R+ and R++ , respectively. A matrix is generally
represented by an upper case letter, say X = [xij ], where xij is the
(i, j) element of matrix X and X T indicates its transposition. We
assume that 1n and In denote the n × 1 vector of all ones and the
n × n identity matrix, respectively. The centering matrix is defined
by Mn = In − n1 Jn in which Jn is the n × n matrix of all ones.
Notation X  Y is equivalent to matrix X − Y being positive semidefinite. A graph is represented by G = (V, E , w), where V is the
set of nodes, E ⊂ V × V is the set of links, and w : V × V → R+
is the weight function. The value of the weight function is zero for
e ∈ V × V \ E and positive for e ∈ E . The weighted degree of node
i ∈ V is defined by
X
w(e).
(1)
di :=
e={i,j}∈E

The neighborhood of node i is denoted by set N (i) that consists
of all adjacent nodes to i and its cardinality |N (i)| is equal to the
number of neighbors of node i. In unweight graphs, |N (i)| is equal
to the degree of node i. The adjacency matrix A = [aij ] of graph
G is defined by setting aij = w(e) if e = {i, j} ∈ E , and aij = 0
otherwise. The Laplacian matrix of graph G with n nodes is defined
by
L := diag[d1 , . . . , dn ] − A.
A n-by-m oriented incidence matrix E = [eij ] for 1 ≤ i ≤ n and
1 ≤ j ≤ m can be formed by assigning an arbitrary direction for
every link of G, labeling every link by a number 1 ≤ j ≤ m, and
letting eij = 1 whenever node i is the head of (directed) link j,
eij = −1 if node i is the tail of (directed) link j, and eij = 0 when
link j is not attached to node i for all possible orientations of links.
The weight matrix W = [wkk ] is the m-by-m diagonal matrix with
diagonal elements wkk = w(ek ) for 1 ≤ k ≤ m. It follows that
L = EW E T .
Assumption 1: All graphs in this paper are assumed to be finite,
simple, undirected, and connected.
According to this assumption, every considered Laplacian matrix
in this paper has exactly n − 1 positive eigenvalues and one zero
eigenvalue, which allow us to index them in ascending order 0 =
λ1 ≤ λ2 ≤ · · · ≤ λn . The set of Laplacian matrices of all connected
weighted graphs over n nodes is represented by Ln . The Moore†
Penrose pseudo-inverse of L is denoted by L† = [lji
] which is a
square, symmetric, doubly-centered and positive semi-definite matrix.
The corresponding resistance matrix R = [rij ] to Laplacian matrix
L is defined by setting
†
†
†
rij = lii
+ ljj
− 2lij

in which rij is called the effective resistance between nodes i and j.
Moreover, we denote the effective resistance of link e = {i, j} by
r(e) = rij = rji . The ℓ0 sparsity measure of matrix A = [aij ] ∈

Rn×n is defined by

kAkℓ0 := card (i, j)

aij 6= 0 .

1≤i≤n

1≤j≤n

(2)

The S0,1 sparsity measure of matrix A is defined by
n
o
kAkS0,1 := max max kA(i, .)k0 , max kA(., j)k0 ,

(3)

where A(i, .) represents the i’th row and A(., j) the j’th column of
matrix A. The value of the S0,1 -measure of a matrix is the maximum
number of nonzero elements among all rows and columns of that
matrix [18].
III.

P ROBLEM S TATEMENT

A. Network model
We consider a class of consensus networks that consist of a group
of subsystems whose state variables xi , control inputs ui , and output
variables yi are scalar and their dynamics evolve with time according
to
ẋi (t)

=

ui (t) + ξi (t)

(4)

yi (t)

=

xi (t) − x̄(t)

(5)

for all i = 1, . . . , n, where xi (0) =

xi0

is the initial condition and

1
x̄(t) =
x1 (t) + . . . + xn (t)
n
is the average of all states at time instant t. The impact of the uncertain
environment on each agent’s dynamics is modeled by the exogenous
noise/disturbance input ξi . By applying the following linear feedback
control law to the agents of this network
ui (t) =

n
X
j=1


kij xj (t) − xi (t) ,

(6)

where kij is the feedback gain between subsystems i and j, the
closed-loop dynamics of network (4)-(6) can be written in the
following compact form
(
ẋ(t) = − Lx(t) + ξ(t)
N(L) :
(7)
y(t) = Mn x(t)
with initial condition x(0) = x0 , where x, ξ and y denote the state
vector of the entire network, the exogenous disturbance input and
the output vector of the network, respectively. The Laplacian matrix
L = [lij ] is defined by

−kij
if i 6= j

lij :=
.
(8)

ki1 + . . . + kin if i = j

The coupling graph of the consensus network (7) is a graph G =
(V, E , w) with node set V = {1, . . . , n}, link set
n
o
E = {i, j} ∀ i, j ∈ V : kij 6= 0 ,
(9)
and weight function

w(e) =


 kij


0

if

e = {i, j} ∈ E

if

e∈
/E

.

(10)

One may verify that the Laplacian matrix of graph G is equal to L.
Assumption 2: All feedback gains (weights) satisfy the following
properties for all i, j ∈ V:
(i) non-negativity: kij ≥ 0,
(ii) symmetry: kij = kji ,
(iii) simpleness: kii = 0.

3

Ω
Ωh

PSfrag replacements
Ωs

Fig. 1: A Venn diagram that shows the relationship among sets Ω, Ωs , and
Ωh . The set of general systemic measures Ω is a superset of both the set
of homogeneous systemic measures Ωh and the set of spectral systemic
measures Ωs . While the intersection of sets Ωs and Ωh is nonempty, there

are some systemic measures that belong only to one of these sets.

Property (ii) implies that feedback gains are symmetric and (iii)
means that there is no self-feedback loop in the network.
Assumption 3: The coupling graph G of the consensus network (7)
is time-invariant.
Based on Assumption 3, the corresponding eigenvector to the
only marginally stable mode of the network is 1n . This mode is
unobservable from the performance output as the output matrix of
the network satisfies Mn 1n = 0.
B. Homogeneous Systemic Performance Measures
A systemic measure in this paper refers to a real-valued operator
over the set of all consensus networks governed by (7) with the
purpose of quantifying performance of this class of networks in
presence exogenous uncertainties. Since every network with dynamics
(7) is uniquely determined by its Laplacian matrix, it is reasonable
to define a systemic performance measure as an operator on set Ln .
Definition 1: An operator ρ : Ln → R+ is called a homogeneous
systemic measure of order −α, where α > 0, if it satisfies the
following properties for all matrices in Ln :
1. Homogeneity: For all κ > 1,
ρ(κL) = κ−α ρ(L);
2. Monotonicity: If L2  L1 , then
ρ(L1 ) ≤ ρ(L2 );
3. Convexity: For all 0 ≤ c ≤ 1,
ρ(cL1 + (1 − c)L2 ) ≤ cρ(L1 ) + (1 − c)ρ(L2 );
The set of all homogeneous systemic performance measures is
denoted by Ωh . We adopt an axiomatic approach to introduce and
categorize a general class of performance measures that captures
the quintessence of a meaningful measure of performance in largescale dynamical networks [19]. Property 1 implies that intensifying
the coupling weights by ratio κ > 1 results in κα times better
performance. Property 2 guarantees that strengthening couplings in
a consensus network never worsens the network performance with
respect to a given systemic measure. The monotonicity property
induces a partial ordering on all linear consensus networks with
dynamics (7). Adding new coupling links or strengthening the existing
couplings will result in better performance. Property 3 is imposed
for the pure purpose of having favorable (convex) network design
optimization problems.

The class of systemic performance measures can be classified based
on their functional properties according to Definition 1. Let us denote
the set of spectral systemic performance measures by Ωs . This class
consists of all measures that satisfy properties 2, 3 and orthogonal
invariance3 . We refer to [20] for a comprehensive study of this class
of performance measures. It is proven that all measures in Ωs depend
only on Laplacian eigenvalues. Let us represent the set of all general
systemic performance measures that only satisfy properties 2 and 3
by Ω. Fig. 1 shows the relationship between the sets of spectral,
homogeneous, and general systemic performance measures.
Definition 2: For a given linear consensus network N(L) endowed
with a homogeneous systemic measure ρ : Ln → R+ of order −α,
its corresponding normalized performance index is defined by
p
Πρ (L) := α ρ(L).
(11)
C. Network Abstraction Problem
Our goal is to develop a framework to compute an abstraction
of a given linear consensus network with predetermined levels of
performance and sparsity (i.e., link reduction).
Definition 3: Let us consider network N(L) that is governed by
(7). For a properly chosen pair of design parameters d ∈ R++ and
ǫ ∈ (0, 1), another N(Ls ) is said to be an (ǫ, d)-abstraction of N(L)
if and only if
(i) N(Ls ) has at most dn/2 feedback links;
(ii) N(Ls ) is an ǫ-approximation of N(L) in the following sense
Πρ (L) − Πρ (Ls )
≤ǫ
Πρ (Ls )

(12)

for every homogeneous systemic performance measure ρ : Ln → R+ .
Property (i) implies that the average number of neighbors for every
node in N(Ls ) is less than d, i.e.,
n
|Es |
1X
≤ d,
|N (i)| = 2
d¯ =
n i=1
n

where N (i) and Es denote the set of all adjacent nodes to i and the set
of all links in the abstraction, respectively. Therefore, one can think of
design parameter d as an upper bound on the desired average number
of neighbors of nodes in the abstracted network which is independent
of the network size. For Property (ii), inequality (12) indicates that
the resulting abstracted network N(Ls ) has guaranteed performance
bounds with respect to N(L). The design constant ǫ is referred to as
permissible performance loss parameter.
IV.

E XAMPLES OF R ELEVANT H OMOGENEOUS S YSTEMIC
P ERFORMANCE M EASURES

We now present some existing and widely-used systemic performance measures for linear consensus networks; a list of these
measures are summarized in Table I.
A. Sum of Homogeneous Spectral Functions
This class of performance measures is generated by forming
summation of a given function of Laplacian eigenvalues. For a given
matrix L ∈ Ln , suppose that ϕ : R+ → R+ is a decreasing
homogeneous convex function. Then, the following spectral function
ρ(L) =

n
X

ϕ(λi )

(13)

i=2

3 A systemic measure is orthogonally invariant if ρ(L) = ρ(U LU T ) for
every orthogonal matrix U for which U U T = U T U = I.

4

Homogeneous Systemic Performance Measure

Symbol

Spectral Riemann zeta function

ζq (L)

Representation
n
X
1/q
λ−q
i
i=2
n 
X

2

Iγ (L)

γ

System Hankel norm

η(L)

i=2
1 −1
λ2

Hardy-Schatten or Hp system norm

θp (L)

Local Deviation Error for First Order Consensus Networks
Local Deviation Error for Second Order Consensus
Networks with β > 0

∆(L)

1
2

Υ(L)

1
2β

H2 -norm of Second Order Consensus Networks with
β>0

Θ2 (L)

Gamma entropy

2
(



λi − λ2i − γ −2

1 
2

)1/p
Z ∞ X
n

p−1  p1
1
= α0 Tr L†
σk (G(jω))p dω
2π −∞
k=1
Pn
−1
i=1 di
Pn

1
2β

i=1

Pn

di −2

i=1

λi −2

1/2

TABLE I: Some important examples of homogeneous systemic performance measures.

is a homogeneous systemic measure [20]. Moreover, if ϕ is a homogeneous function of order −α where α > 1, then its corresponding
normalized index
!1
n
α
X
Πρ (L) =
(14)
ϕ(λi )

of Laplacian spectrum as follows
X
n


fγ (λi )
γ ≥ λ−1

2

i=2
,
(16)
Iγ (L) =




∞
otherwise

1 
where fγ (λi ) = γ 2 λi − λ2i − γ −2 2 . Furthermore, the γentropy Iγ (L) is a homogeneous systemic performance measure.

1) Spectral Riemann Zeta Measures: For a given network (7), its
corresponding spectral Riemann zeta function of order q ≥ 1 is
defined by
1/q
X
n
ζq (L) :=
λ−q
,
(15)
i

B. Uncertainty volume

i=2

is also a homogeneous systemic performance measure [20]. Some
notable examples of this class of measures are discussed in the
following parts.

i=2

where λ2 , . . . , λn are eigenvalues of L [21]. According to Assumption 3, all Laplacian eigenvalues are strictly positive and, as a result,
function (15) is well-defined. According to the result presented in
Subsection IV-A, since ϕ(λ) = λ−q for q ≥ 1 is a decreasing
homogeneous convex function, the spectral function (15) is a homogeneous systemic performance measure. The homogeneous systemic
performance measure 12 ζ1 (L) is equal to the H2 -norm squared of a
first-order consensus network (7) and √12 ζ (L) equal to the H2 -norm
2
of a second-order consensus model of a network of multiple agents
(c.f. [11]).
2) Gamma Entropy: The notion of gamma entropy arises in various
applications such as the design of minimum entropy controllers and
interior point polynomial-time methods in convex programming with
matrix norm constraints [22]. As it is shown in [23], the notion of
gamma entropy can be interpreted as a performance measure for linear
time-invariant systems with random feedback controllers by relating
the gamma entropy to the mean-square value of the closed-loop gain
of the system. The γ-entropy of network (7) is defined as
 −γ 2 R ∞

log det I − γ −2 G(jω)G∗ (jω) dω

2π
−∞



for γ ≥ kGkH∞
Iγ (L) :=




∞
otherwise

where G(jω) is the transfer matrix of network (7) from ξ to y [23].
In [20], it is shown that the value of the γ-entropy for a given
linear consensus network (7) can be explicitly computed in terms

The uncertainty volume of the steady-state output covariance matrix
of network (7) is defined by

1 
(17)
|Σ| := det Y∞ + Jn
n
in which


Y∞ = lim E y(t)y T (t) .
t→∞

This quantity is widely used as an indicator of the network performance [2] and [24]. Since y(t) is the error vector that shows distance
from consensus, the quantity (17) can be interpreted as volume of the
steady-state error ellipsoid. It is straightforward to show this measure
satisfies all properties of Definition 1.
C. Hankel Norm
The Hankel norm of network (7) and transfer matrix G(jω) from
ξ to y is defined as the L2 -gain from past inputs to the future outputs,
i.e.,
R∞ T
y (t)y(t)dt
kGk2H :=
sup
.
R 00
ξ∈L2 (−∞,0]
ξ T (t)ξ(t)dt
−∞

The value of the Hankel norm of network (7) can be equivalently
computed using the Hankel norm of its disagreement form [3] that is
given by
ẋd (t)

=

y(t)

=

−Ld xd (t) + Mn ξ(t),

Mn xd (t),

(18)
(19)

where the disagreement vector is defined by
1
Jn x(t).
(20)
n
The disagreement network (18)-(19) is stable as the real part of every
eigenvalue of the state matrix −Ld = −(L+ n1 Jn ) is strictly negative.
xd (t) := Mn x(t) = x(t) −

5

One can verify that the transfer matrices from ξ(t) to y(t) in both
realizations are identical. Therefore, the Hankel norm of the system
from ξ(t) to y(t) in both representations are well-defined and equal,
and is given by [25]
p
η(L) := kGkH = λmax (P Q),
(21)

where the controllability Gramian P is the unique solution of


1 
1 
L + Jn P + P L + Jn − Mn = 0
n
n
and the observability Gramian Q is the unique solution of

1 
1  
Q L + Jn + L + Jn Q − Mn = 0.
n
n
It is shown in [20] that the value of the Hankel norm of network (7)
is equal to
1
η(L) = λ−1
.
2 2
One can verify that this measure is a homogeneous systemic performance measure.
Remark 1: One may also consider the sum of the k largest
eigenvalues of L† as a performance measure. This is equivalent to
evaluate the k slowest modes of the network, which are the most
energetic modes. This measure satisfies properties of Definition 1 as
it is convex and symmetric with respect to Laplacian eigenvalues (c.f.
[26, Ch. 5.2] and [27]).
D. Hardy-Schatten or Hp System Norms

The Hp -norm of networks (7) for 2 ≤ p ≤ ∞ is defined by
!1
Z ∞ X
n
p
1
p
kGkHp :=
σk (G(jω)) dω
,
(22)
2π −∞ k=1

where G is the transfer matrix from ξ(t) to y(t) and σk (jω)
for k = 1, . . . , n are singular values of G(jω). To ensure welldefinedness of performance measure (22), the marginally stable mode
of the network must be unobservable through the output. Thus, this
performance measure remains well-defined as long as the coupling
graph of the network stays connected. This class of system norms
captures several important performance and robustness features of
linear control systems. For instance, a direct calculation reveals that
the H2 -norm of network (7) is
!1
n
2
1 X −1
kGkH2 =
.
(23)
λi
2 i=2

E. Local deviation error:
In network (7), the local deviation of subsystem i is equal to the
deviation of the state of subsystem i from the weighted average of
states of its immediate neighbors, which can be formally defined by
X
1
w(e) xj (t).
(26)
εi (t) := xi (t) −
di
e={i,j}∈E

The expected cumulative local deviation is then defined by
" n
#
X
2
∆(L) = lim E
εi (t)
t→∞

with respect to input ξ being a white noise process with identity
covariance. The notion of local deviation can be extended and defined
for velocity variables in the second-order consensus network (96)-(97)
(c.f., [11]) as follows
X
1
ςi (t) := vi (t) −
w(e) vj (t)
(28)
di
e={i,j}∈E

that is equal to the deviation of the velocity of subsystem i from
the weighted average of velocities of its neighbors. The expected
cumulative local deviation is then given by
" n
#
X
ςi (t)2 ,
Υ(L) = lim E
(29)
t→∞

kGkH∞ =

Theorem 1: The operators ∆, Υ : Ln → R+ defined by (27) and
(29) are homogeneous systemic performance measures. Moreover,
they can also be characterized as
∆(L) =
and
Υ(L) =

4 β(x, y)

=

R1
0

tx−1 (1 − t)y−1 dt for Re{x}, Re{y} > 0.

n
1 X −1
di
2 i=1

(30)

n
1 X −2
di
2β i=1

(31)

in which di is the degree of node i ∈ V.

Proof: Let us define the total local deviation at time t by
X
εtotal (t) :=
εi (t)2 .
(32)
i∈V

We reformulate (26) as
εi (t)

=
=

(24)

where λ2 is known as the algebraic connectivity of the network [3].
The value of H∞ -norm of network (7) can be interpreted as the worst
attainable performance for all square integrable disturbance inputs.
In [20], the authors prove that the Hp -norm of a given network
N(L) is given by

1− 1
p
θp (L) := kGkHp = α0 ζp−1 (L)
(25)
q
p
−β( 2p , − 12 ) and β : R×R → R is the well-known
in which α−1
0 =
4
Beta function . Moreover, this measure is a homogeneous systemic
performance measure for all 2 ≤ p ≤ ∞.

i=1

where it is assumed that input ξ in network model (96)-(97) is a white
noise process with identity covariance.

This system norm quantifies the quality of noise propagation throughout the network [12]. The H∞ -norm of a network is an input-output
system norm and its value for network (7) is
λ−1
2 ,

(27)

i=1



di xi (t) −
d−1
i

d−1
i

X

e={i,j}∈E

X

e={i,j}∈E



w(e) xj (t)

w(e) (xi (t) − xj (t)) .

(33)

Therefore, we get


−1
ε(t) = diag d−1
L x(t).
1 , · · · , dn

where ε(t) is concatenation of elements εi (t) for i = 1, . . . , n. Also,
we can rewrite (32) as follows
εtotal (t) = εT (t)ε(t) = xT (t)Qx(t)
with


−2
Q = L diag d−2
L.
1 , · · · , dn

Thus, according to [12, Thm. 5] the steady-state of εtotal is given by

1
∆(L) = lim E [εtotal (t)] = Tr L† Q
t→∞
2

6

1 X −1
di .
2 i∈V

=

(34)

Now we show this measure is a homogeneous systemic performance
measure. We first show that (34) has property 1, which means
1X
∆(κL) =
(κdi )−1 = κ−1 ∆(L).
2 i∈V

(a)

(b)

Fig. 2: Two isospectral graphs with six nodes [29].

Furthermore, it is monotone, because if L1  L2 then we have
T
eT
i L1 ei ≤ ei L2 ei ,

where ei for i = 1, . . . , n are the standard basis for the n-dimensional
Euclidean space. Therefore, we have L1 (i, i) ≤ L2 (i, i) that guarantees the monotonicity of ∆. Moreover, its convexity follows from
convexity of function 1/x for all x ∈ R+ . Because consider two
(1)
(2)
Laplacian matrices L1 and L2 with node degrees di and di ,
respectively, for i = 1, . . . , n. Then, we get
X
1
∆(cL1 + (1 − c)L2 ) =
(1)
(2)
+ (1 − c) di
i∈V c di
!
X
c
1−c
≤
+ (2)
(1)
d
di
i∈V
i
X 1−c
X c
+
=
(1)
(2)
i∈V di
i∈V di
= c∆(L1 ) + (1 − c)∆(L2 )
for all 0 ≤ c ≤ 1. This completes the proof of the first part. For the
second part, let us define the total local deviation error at time t by
X
ςtotal (t) :=
ςi (t)2 .
(35)
i∈V

We similarly reformulate (28) as

ςi (t)

=

=

d−1
i

d−1
i

di vi (t) −
X

e={i,j}∈E

X

e={i,j}∈E



w(e) (vi (t) − vj (t)) .



−1
ς(t) = diag d−1
L v(t),
1 , · · · , dn

where ς(t) is concatenation of elements ςi (t) for all 1 ≤ i ≤ n.
Moreover, we can rewrite (35) as follows
=

ς T (t)ς(t)

=

v T (t)Qv(t),


d−2
1 ,···

, d−2
n

where Q is given by Q = L diag
steady-state of ςtotal can be characterized as
Υ(L)

=
=

V.

In this section, we develop a fast abstraction algorithm for the class
of linear consensus networks (7) with guaranteed bounds with respect
to the class of homogeneous systemic performance measures.

The abstraction goals are to reduce the number of feedback links
while preserving a desired level of performance. From notation (3),
one can easily verify that the value of S0,1 -measure is equal to the
maximum of |N (i)| for all nodes i = 1, . . . , n, which makes it a
suitable surrogate for design parameter d. The next result reveals an
inherent interplay between sparsity and performance.
Theorem 2: For a given network (7) that is endowed with a
homogenous systemic performance measure ρ : Ln → R+ of order
−α, suppose that w∗ = maxe∈E w(e). Then, there are fundamental
tradeoffs between normalized performance and graph sparsity measures in the following sense

(36)


L. Therefore, the


1
Tr (L† )2 Q
lim E [ςtotal (t)] =
t→∞
2β
1 X −2
di .
2β i∈V

A BSTRACTION WITH G UARANTEED B OUNDS

A. Intrinsic Tradeoffs on the Best Achievable Abstractions

w(e) vj (t)

Therefore, we have

ςtotal (t)

monotonicity of Υ. Finally, its convexity can be concluded from
convexity of function 1/x2 for all x ∈ R+ .
Remark 2: For first-order consensus network (7) that are defined
over d-regular coupling graphs, the corresponding microscopic measure (30) scales linearly with network size. For regular lattices that
are d-regular graphs, our result assumes the reported result of [28] as
its special case.
Remark 3: Fig. 2 shows example of two isospectral5 graphs that
are not isometric6 . While the value of a spectral systemic performance
measure is equal for both graphs, the value of an expected cumulative
local deviation measure is different for each of these graphs and
depend on their specific interconnection topology. This simple observation implies that systemic performance measures (30) and (31)
are suitable tools to differentiate among networks with isospectral
coupling graphs.

(37)

This measure is a homogeneous systemic performance measure. It is
straightforward to show that (37) satisfies property 1 by verifying that
1 X
Υ(κL) =
(κdi )−2 = κ−2 Υ(L).
2β i∈V
It is monotone, as if L1  L2 , then we have
T
eT
i L1 ei ≤ ei L2 ei .

As a result, it follows that L1 (i, i) ≤ L2 (i, i) that guarantees the

Πρ (L) kAkℓ0 ≥ 2̺∗ (n − 1),

(38)

Πρ (L) kAkS0,1 ≥ 2̺∗

(39)

and
when n > 2, in which A is the adjacency matrix of the coupling
graph and ̺∗ = w∗−1 Πρ (LKn ), where LKn is Laplacian matrix of
the unweighted complete graph.
Proof: Since it is assumed that the coupling graph of the network
is connected, the sparsity measure kAkℓ0 is always bounded from
below by 2(n − 1); with equality sign if the coupling graph is a
tree. Thus, the following inequality holds on the cone of positive
semidefinite matrices
kAkℓ0
w∗ kAkℓ0
L 
L 
LKn .
2(n − 1)
2(n − 1)
5 Two graphs are called isospectral if and only if their Laplacian matrices
have the same multi-sets of eigenvalues
6 This means that their adjacency matrices are not permutation-similar.

7

From monotonicity property, it follows that
ρ(L) kAkα
ℓ0

α

≥ 2 (n − 1)

α

w∗−α

ρ(LKn ).

By taking α’th root from both sides, one can conclude the desired
inequality (38). When n > 2, the localized sparsity measure kAkS0,1
is always greater of equal to 2. Therefore, the following relation holds
1
1
kAkS0,1 L 
w∗ kAkS0,1 LKn .
2
2
By utilizing the monotonicity property, we get
L 

α −α
ρ(L) kAkα
S0,1 ≥ 2 w∗ ρ(LKn ).

The desired inequality (39) follows from taking α’th root from both
sides of the inequality.
The monotonicity property of a systemic performance measure
implies that link removal will lead to performance deterioration.
Theorem 2 quantifies this inherent interplay by saying that sparsity
and performance cannot be improved indefinitely both at the same
time. As we will see in the following subsection, this is exactly why
we need to perform reweighing after link elimination procedure in
order to achieve an approximation that meets (12).
B. Existence and Algorithms
The next theorem enables us to harness the monotonicity property
of homogeneous systemic measures in our network approximations.
Theorem 3: Suppose that two linear consensus networks N(L)
and N(Ls ) are endowed with a homogeneous systemic performance
measure ρ : Ln → R+ of order −α. For a given constant ǫ ∈ (0, 1),
the two networks are ǫ-approximation of each other, i.e., property
(12) holds, if and only if their state matrices satisfy
(1 − ǫ)L  Ls  (1 + ǫ)L.

(40)

Proof: According to the monotonicity and homogeneity properties of system measures, it follows that if (40) holds then we have
(1 + ǫ)−α ρ(L) ≤ ρ(Ls ) ≤ (1 − ǫ)−α ρ(L).

(41)

Therefore, according to (41) and (12), N(Ls ) is an ǫ-approximation
of N(L). Let us consider the following measures
ρv (L) = v T L† v

(42)

n

for all v ∈ R . This operator is a homogeneous systemic performance
measure of order −1. For all v ∈
/ Span{1}, inequality (12) yields
ρv (L) − ρv (Ls )
≤ ǫ.
−ǫ ≤
ρv (Ls )

v T L†s v
≤ (1 − ǫ)−1 .
v T L† v

(43)

Since v T L† v > 0, inequalities (43) can be rewritten as
(1 + ǫ)−1 v T L† v ≤ v T L†s v ≤ (1 − ǫ)−1 v T L† v.

in which hv, ui i := v T ui . Moreover, we know that the eigenvalues of
A + vv T interlace those of A. Reference [17] suggests a framework
which provides intuition as to where these new eigenvalues are
located. If we start with an empty graph on n nodes, then after
M = ⌈d(n − 1)/2⌉ iterations of choosing links from the original
graph and adjusting its weight, it is shown that the eigenvalues of
the resulted graph are controlled by maintaining two barrier potential
functions. According to [17, Th. 1.1], coupling graph G = (V, E , w)
has a weighted subgraph Ĝ = (V, Ê, ŵ) with |Ê | = ⌈d(n − 1)/2⌉
that satisfies
!2
p
1 + d/2
p
L
(45)
L  LĜ 
1 − d/2

where LĜ is the Laplacian matrix of graph Ĝ. We define Gs =
(V, Ê, ws ) by its Laplacian matrix, which is given by
p
(1 − d/2)2
Ls :=
LĜ .
(46)
1 + d/2
Therefore, according to (45) and (46), it follows that
!
!
√
√
2d
2d
1−
L  Ls 
1+
L.
d/2 + 1
d/2 + 1

(47)
√

Thus, it follows that
(1 + ǫ)−1 ≤

N(L2 ), inequality ρ(L2 ) ≤ ρ(L1 ) can be realized through several
possible scenarios; for example, network N(L2 ) can be constructed
by (i) adding new weighted edges to the coupling graph of network
N(L1 ), (ii) increasing weights of some of the existing links in
network N(L1 ), (iii) rewiring topology of network N(L1 ) while
ensuring L1  L2 .
The next result proves existence of an abstraction for every given
linear consensus network.
Theorem 4: Suppose that a network N(L) with coupling graph
G = (V, E , w) endowed with a homogeneous systemic performance
measure ρ : Ln → R+ of order −α and a design parameter d > 2
are given. Then, it is possible to construct another network N(Ls )
with coupling graph
Gs = (V, Es , ws ) such that
√
8d
(i) N(Ls ) is a ( d+2
, d)-abstraction of network N(L);
(ii) Es ⊂ E .
Proof: It is well known that the characteristic polynomial of
A + vv T can be computed based on the characteristic polynomial7
of A, its eigenvalues µi , and eigenvectors ui as follows
!
X hv, ui i2
PA+vvT (x) = PA (x) 1 −
x − µi
i

(44)

We know that L and Ls are Laplacian matrices and (44) holds for
all v ∈
/ Span{1}; therefore, we get
(1 + ǫ)−1 L†  L†s  (1 − ǫ)−1 L† .

This inequality can be rewritten to obtain the desired result
(1 − ǫ)L  Ls  (1 + ǫ)L.

2d
, d)Using (47) and Theorem 3, it yields that N(Ls ) is a ( d/2+1
abstraction of N(L). Since Es = Ê and the fact that Ê is obtained
by taking samples from E , one concludes that Es ⊂ E .
In our next result, we show that every consensus network has a
sparsification such that: (i) it yields a better systemic performance
than the original network, and (ii) the total weight sum of the coupling
graph of the spars network is controlled, i.e., it is less than a constant
multiple, which is independent of the network size, of the total weight
sum of the original network.
Proposition 1: For a given consensus network N(L) with coupling
graph G = (V, E , w) and every d > 2, there exists a consensus
network N(Ls ) with coupling graph Gs = (V, Es , ws ) that has at
most dn/2 links and Es ⊂ E . Moreover, we have
(i) the total weight of coupling graph of N(Ls ) is controlled, i.e.,
7

The result of the above theorem is crucial as it enables us to
take advantage of monotonicity property of systemic performance
measures in our approximations. For two given networks N(L1 ) and

The characteristic polynomial of matrix A ∈ Rn×n is defined by
pA (t) = det (tIn − A) .

8

X

e∈Es

ws (e) ≤

!2
√
X
2d + 2
√
w(e);
2d − 2
e∈E

Algorithm 1: Network Abstraction Algorithm

(48)

Input : G = (V, E , w) and r(e) for all e ∈ E
Output: Gs = (V, Es , ws )

(ii) N(Ls ) has a superior performance with respect to N(L), i.e.,
ρ (Ls ) ≤ ρ (L) ,

1

for every homogeneous systemic performance measure ρ : Ln → R+ .
Proof: According to
abstraction, N(Lŝ ), with Eŝ
!α
√
2d
1−
≤
d/2 + 1

√

8d
( d+2
, d)-

Theorem 4, N(L) has a
⊂ E , which means that we have
!α
√
ρ (L)
2d
≤
1+
ρ (Lŝ )
d/2 + 1

(49)

ρ (Ls ) ≤ ρ (L) .

−1
P
It is straightforward to verify that operator Ξ(L) =
e∈E w(e)
is a homogeneous systemic performance measure with α = 1. From
the left-hand side inequality of (49), we get the desired bound (48).
Remark 4: Proposition 1 demonstrates a tradeoff between the
largest possible number of links in an abstraction, i.e., upper bound
of |Es |, and
ratio of the total weights, i.e., upper
Pthe best achievable
P
bound of e∈Es ws (e)/ e∈E w(e). We have that

P
ws (e)
Pe∈Es
≤
e∈E w(e)

!2
√
2d + 2
√
.
2d − 2

4

6
7

Finally, by substituting ρ(Lŝ ) from (50) in the left-hand side inequality of (49), we obtain

and

3

5

for every homogeneous systemic performance
measure ρ : Ln → R+
√
8d
of order −α. Let us define Ls = d+2−
Lŝ . Then, it follows that
d+2
α

d+2
√
ρ(Ls ).
(50)
ρ(Lŝ ) =
d + 2 − 8d

1
|Es | ≤ dn
2

2

(51)

(52)

Let us fix n. By increasing the value of parameter d, the upper bound
in (51) increases, but the upper bound in (52) decreases and gets closer
to 1. On the other hand, if d → 2, then the upper bound in (52) tends
to infinity.
We next employ a randomized algorithm to compute an (ǫ, d)abstraction of a given network. A randomized algorithm utilizes a
degree of randomness as part of its logic. Randomization allows us to
design provably accurate algorithms for problems that are massive and
computationally expensive or NP-hard. For this aim based on [16],
we sample low-connectivity coupling links with high probability and
high-connectivity coupling links with low probability. For a given
consensus network N(L) with n nodes, we sample links of the
coupling graph of this network M := ⌈dn/2⌉ times in order to
produce an (ǫ, d)-abstraction. Let us denote probability of selecting a
link e ∈ E by π(e)8 that is proportional to w(e)r(e), where w(e) and
r(e) are the weight and the effective resistance of link e, respectively.
In each step of sampling9 , we add the selected link e to the abstraction
with weight w(e)/(M π(e)). All details of our proposed algorithm
are explained below. The following result, which is obtained based on
a theorem in [16, Thm. 1], provides us with a certificate that the above
P
8
e∈E w(e)r(e) = n − 1; therefore, we have
P It is well-know that
e∈E π(e) = 1.
9 A sampling is a discrete probability distribution on a support E of all
possible samples. The probability of selecting
P link e is denoted by positive
number π(e) for all e ∈ E. We also have
e∈E π(e) = 1, because π is a
probability distribution on E.

8

set Gs to be the empty graph on V (i.e., Es := {} and
ws (.) := 0)
for all e ∈ E
set π(e) = w(e)r(e)
n−1
for j = 1 to M := ⌈dn/2⌉ do
sample a link from E with probability distribution π → {e}
Es = Es ∪ {e}
ws (e) = ws (e) + Mw(e)
π(e)
end
return Gs

randomized algorithm is capable of generating a proper abstraction
of a given linear consensus network.
Theorem 5: Suppose that a linear consensus network N(L) endowed with a homogeneous systemic performance measure ρ :
Ln → R+ of order −α is given and a permissible performance loss
√
parameter ǫ ∈ (1/ n, 1] is fixed. Let us pick a real number d that
is at the order of ǫ−2 log n. Then, Algorithm 1 produces an (ǫ, d)abstraction of network N(L), whose coupling graph is a subgraph of
N(L), with probability at least 0.5.
Proof: Let us consider the following projection matrix
P = W 1/2 EL† E T W 1/2 ,

(53)

where E is m-by-n incidence matrix and W is a diagonal matrix
with link weights on its diagonal such that L = E T W E. The mby-m matrix P has eigenvalue at 0 with multiplicity m − n + 1 and
eigenvalue at 1 with multiplicity n−1 [16, Lemma 3]. Now, we show
that the sampling of links in Algorithm 1 corresponds to selecting
M = O(n log n/ǫ2 ) columns at random from matrix P . Then by
a concentration lemma of Rudelson [30, Thm. 3.1] and Markov’s
inequality, with probability at least 0.5, we get
kP − P ΓP k2 ≤ ǫ,

(54)

where Γ is a nonnegative diagonal matrix. Then, it is straightforward
to show that for every homogeneous systemic performance measure
ρ : Ln → R+ , we have
Πρ (L) − Πρ (Ls )
≤ǫ
Πρ (Ls )

in which Ls = EW 1/2 ΓW 1/2 E T . One can show that the inequality
(54) is equivalent to
sup

x∈Rm
x6=0

|xT (P − P ΓP )x|
≤ ǫ.
xT x

Since Im{W 1/2 E} ⊂ Rm , it follows that
sup
x∈Im{W 1/2 E}
x6=0

|xT (P − P ΓP )x|
xT x

≤
≤

Let us define x = W

1/2

sup

x∈Rm
x6=0

(55)

|xT (P − P ΓP )x|
xT x

ǫ.

′

Ex . Then, we can rewrite (55) as follows

sup
x′ ∈Rn
1/2 E}
x′ ∈ker{W
/

|x′T (L − Ls )x′ |
≤ ǫ.
x′T Lx′

(56)

For all x′ ∈ ker{W 1/2 E}, one gets x′T Lx′ = x′T Ls x′ = 0. As a

9

result, it follows that
|x′T (L − Ls )x′ |
sup
≤ ǫ,
x′T Lx′
x′ ∈Rn

(57)

x′ 6=0

matrices of the augmented network

Mn
AX + XA =
−Mn
where

which implies that
(1 − ǫ)L  Ls = EW 1/2 ΓW 1/2 E T  (1 + ǫ)L.

A = −

(58)

Finally, using this and Theorem 3, we conclude the desired result.
Algorithm 1 produces a network abstraction with O(n log n/ǫ2 )
feedback links in expectation and runs in approximately linear time
Õ(m), where m is the number of links (c.f. [31]). This favorable
almost-linear-time complexity is achieved by having access to good
approximations of all effective resistances. In [16], the authors show
that O(log n) calls to a solver for a linear system of equations with
symmetric diagonally dominant (SDD) matrix can provide sufficiently
good approximations to all effective resistances. Moreover, it is shown
in [17] that a spectral sparsification with O(n/ǫ2 ) links can be
computed in O(n3 m/ǫ2 ) time by employing a slower deterministic
algorithm for link selection. The best known classical algorithm for
calculating effective resistances relies on solving a Laplacian linear
system and takes Õ(m) time [17], [32].
Remark 5: By putting together results of Theorems 4 and 5, we
observe an intrinsic tradeoff between the number of feedback links
M and the permissible performance loss parameter ǫ. These two
design factors move in opposite directions, i.e., if we decrease M , ǫ
increases, and vice versa. According to Theorems 4 and 5, one can
deduce that the number of feedback links M decreases inversely with
the square of ǫ.

"
L+

1
J
n n

0n×n

and
X =




−Mn
,
Mn
0n×n

Ls +

X1
X2T

1
J
n n

(62)

#


X2
.
X3

The matrix equation (62) can be decomposed into three Sylvester
equations as follow. The first equation is




1
1
L + Jn X1 + X1 L + Jn
= Mn
n
n
and its solution is given by
X1 =

1 †
L .
2

(63)

The second equation is




1
1
= Mn
Ls + Jn X3 + X3 Ls + Jn
n
n
and its unique solution is given by
X3 =

1 †
L .
2 s

(64)

Finally, the third one is




1
1
L + Jn X2 + X2 Ls + Jn
= − Mn
n
n

(65)

with unique solution
C. Guaranteed Performance Bounds
In the following, we show that our proposed abstraction algorithm
approximately preserves frequency characteristics of the original
(dense) network (see Fig. 3). Our abstraction method shares some
common roots with the classical model reduction techniques, where
the objective is to find a reduced model that yields small H2 -norm
error (c.f., [8]). Our first result gives a tight upper bound on the
H2 -norm error of two linear consensus networks in terms of their
Laplacian matrices.
Lemma 1: Suppose that N(L) and N(L̂) are two given consensus
networks governed by dynamics (7). Then, we have

Tr L̂† + L† − 4(L + L̂)†
kG − Ĝk2H2
≤
,
(59)
kGk2H2
Tr (L† )
where G(s) and Ĝ(s) are transfer matrices of N(L) and N(L̂) from
input ξ to output y , respectively.
Proof: In the first step, we define an augmented dynamical
network N∗ using the two given networks
"
#
#
"

1
0

Mn
ż(t) = − L + n Jn

ξ(t)
z(t) +


Mn
0
Ls + n1 Jn
(60)


i
h


y(t) =
Mn −Mn z(t)

in which z ∈ R2n , ξ ∈ Rn , y ∈ Rn . If we denote the transfer matrix
of network (60) from ξ to y by G∗ , then one can show that
kG∗ kH2 = kG − Gs kH2 .

(61)

It is known that calculating the H2 -norm of a linear time-invariant
system reduces to solving an Algebraic Lyapunov Equation (ALE)
[33]. Let us form the corresponding ALE to (61) using the state

X2 = −

Z

∞

1

1

e−(L+ n Jn )t Mn e−(Ls + n Jn )t dt,

0

where the integrand can be reformulated as
1

1

1

1

e−(L+ n Jn )t Mn e−(Ls + n Jn )t = e−(L+ n Jn )t e−(Ls + n Jn )t
1
1 −(L+ n1 Jn )t
e
Jn e−(Ls + n Jn )t
+
n
1
1
e−2t
= e−(L+ n Jn )t e−(Ls + n Jn )t +
Jn .
n
By utilizing the Golden-Thompson inequality for Hermitian matrices,
it follows that


1
1
Tr e−(L+ n Jn )t Mn e−(Ls + n Jn )t


1 J )t −(L + 1 J )t
e−2t
−(L+ n
n
s n n
e
+
Jn
= Tr e
n


−2t
2
e
≥ Tr e−(L+Ls + n Jn )t +
(66)
Jn
n
Therefore, the trace of X2 can be bounded by
Z ∞

1
1
Tr(X2 ) = − Tr
e−(L+ n Jn )t Mn e−(Ls + n Jn )t dt
Z ∞ 0

1
1
= −
Tr e−(L+ n Jn )t Mn e−(Ls + n Jn )t dt
Z0 ∞ 

2
≤ −
Tr Mn e−(Ls +L+ n Jn )t dt
0


= − Tr (L + Ls )† .
(67)

Putting all these pieces together, the H2 -norm of the augmented
network can be written as




 X1 X2 Mn

kG∗ k2H2 = Tr Mn Mn
X2 X3 Mn

10

2.5

y(t)

ξ(t)

+

y(t) − ys (t)

-

replacements

N(Ls ):

PSfrag replacements

p

ǫ(4 − ǫ)/(1 − ǫ)(2 + ǫ)

N(L):

2

1.5

1

0.5

0
0

ys (t)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

ǫ

Fig. 4: This plot presents the upper bound given by Theorem 6 on the
H2 -norm error of a consensus network and its ǫ-approximation network.

Fig. 3: The block diagram of the augmented network (60).

=

Tr



X1
X2

X2
X3



Mn
Mn

Mn
Mn



.

(68)

From (63), (64) and (68), it follows that
1
Tr(L† + L†s ) − Tr((X2 + X2T )Mn )
kG∗ k2H2 =
2


1
≤
Tr(L† + L†s ) − 2 Tr (L + Ls )† ,
2
where (67) is used in the last inequality. Finally, from this and (61),
we conclude the desired result


1
kG − Gs k2H2 ≤ Tr L̂† + L† − 4(L + L̂)† .
2
The right-hand side of inequality (59) is always non-negative, i.e.,


0 ≤ Tr L̂† + L† − 4(L + L̂)† .

This is because of the fact that Tr(L† ) is convex on Ln and the
following inequality holds


 1

1
Tr L† + Tr L̂† .
Tr (L + L̂)† ≤
4
4

The inequality (40) implies proximity of state matrices of the
original and its abstraction on the cone of positive semidefinite
matrices. In the following result, it is proven that the frequency
specifications of two ǫ-approximations are indeed very similar in H2
sense.
Theorem 6: If N(Ls ) is an ǫ-approximation of N(L) for some
0 ≤ ǫ < 1, then
s
kG − Gs kH2
ǫ(4 − ǫ)
≤
,
(69)
kGkH2
(1 − ǫ)(2 + ǫ)
where G(s) and Gs (s) represent the transfer matrices from input ξ
to output y of N(L) and N(Ls ), respectively.
Proof: According to the definition of ǫ-approximation and the
fact that Tr(L† ) is a homogeneous systemic performance measure of
order −1, we get
1
Tr(L† ).
1−ǫ
Moreover, it follows from Theorem 3 that
Tr(L†s ) ≤

(2 + ǫ)−1 (L)† ≤ (L + Ls )† .

(70)

(71)

By taking trace from both sides of (71), one obtains



1
Tr (L + Ls )† ≥
Tr L† .
(72)
2+ǫ
By applying result of Lemma 1, we can conclude that


Tr L̂† + L† − 4(L + L̂)†
kG − Gs k2H2
≤
kGk2H2
Tr(L† )



†
Tr Ls + Tr L† − 4 Tr (L + Ls )†
=
Tr(L† )
ǫ(4 − ǫ)
,
(73)
≤
(1 − ǫ)(2 + ǫ)

where the last inequality is obtained after using (70) and (72).
Fig. 4 depicts the upper bound in inequality (69) for the relative
H2 -norm error of a linear consensus network and its ǫ-approximation.
Corollary 1: Suppose that y is the output of network N(L) and ys
is the output of its corresponding ǫ-approximation N(Ls ) for some
0 ≤ ǫ < 1. Then, the steady-state expected value of their output error
can be bounded by
n
o

ǫ(4 − ǫ)
lim E ky(t) − ys (t)k22 ≤
Tr L† .
t→∞
2(1 − ǫ)(2 + ǫ)

The proof of this corollary is based on the proof of Theorem 6.
Remark 6: In [15], the authors consider a similar problem of
identifying a sparse representation of a given dense linear consensus
network. Their proposed method has two steps. First, an optimal
sparse network topology is obtained by adding the H2 -norm error
(c.f., Fig. 3) with another penalizing term that accounts for sparsity.
Then, the optimal link weights are chosen over the identified topology.
For both cases, approximation methods based on the BroydenFletcher-Goldfarb-Shanno method are employed in [15]. This method
chooses a descent direction based on an approximation of the Hessian
matrix. Therefore each update requires O(n6 ) operations [15]. In
comparison with Algorithm 1 in Section V, the proposed method in
[15] is computationally expensive. Furthermore, it does not provide
any guaranteed performance certificates.
VI.

L OCALIZED N ETWORK A BSTRACTION

Our methodology can be extended further to explore several
interesting network design problems, such as partial or localized
abstraction of a given large-scale consensus network. In this section,
we only look at one of such design problems. Let us consider a
slightly modified version of (7) by involving a predesigned state

11

feedback controller

VII.



ẋ(t) = −L0 x(t) + u(t) + ξ(t)
N(L0 + L1 ) : u(t) = −L1 x(t)


y(t) = Mn x(t)

(74)

with initial condition x(0) = x0 , where L0 is the Laplacian matrix of
the open-loop network and the Laplacian matrix L1 is the predesigned
state feedback gain matrix. Let us represent the corresponding coupling graph to L1 by G1 . If L1 is obtained via traditional optimal
control methods without incorporating sparsity measures, then one
should expect to get a dense interconnection topology for G1 ; we
refer to [18] for discussions on spatially decaying structure of
optimal controllers. Therefore, our design objective is to compute
a localized abstraction for the closed-loop network N(L0 + L1 ) that
only sparsifies G1 . Let us represent such an abstraction by Ĝ1 with
Laplacian L̂1 .
Theorem 7: Suppose that a linear consensus network with structure
(74), a homogeneous systemic performance measure ρ : Ln →√R+
8d
of order −α, and a design parameter d > 2 are given. For ǫ = d+2
,
there exists a subgraph abstraction Ĝ1 = (V, Ê, ŵ) of G1 = (V, E , w)
with at most dn/2 links that satisfies Ê ⊂ E and
Πρ (L0 + L1 ) − Πρ (L0 + L̂1 )
≤ ǫ.
Πρ (L0 + L̂1 )

(75)

Furthermore, it follows that
wtotal (L̂1 ) ≤ (1 + ǫ) wtotal (L1 )
in which wtotal (L) =

1
2

Tr(L).

Proof: According to [17, Th. 1.1], coupling graph G1 =
(V, E , w) has a weighted subgraph H = (V, Ê, ŵ) with |Ê| =
⌈d(n − 1)/2⌉ that satisfies
√
d + 2 + 8d
√
L1
(76)
L1  LH 
d + 2 − 8d
where LH is the Laplacian matrix of graph H. We define Ĝ1 =
(V, Ê , ŵ) based on the following Laplacian matrix
p
(1 − d/2)2
L̂1 :=
LH .
(77)
1 + d/2
From (76) and (77), it follows that
!
√
2d
L1  L̂1 
1−
d/2 + 1
Moreover, we know that
!
√
2d
L0  L0 
1−
d/2 + 1
From (78) and (79), we have
√ !
8d
(L0 + L1 )
1−
d+2




1+

1+

√

2d
d/2 + 1
√

2d
d/2 + 1

!
!

L1 .

(78)

8d
1+
d+2

!

Building upon the results of the previous section, we introduce
a distributed and parallel implementation of our proposed localized
algorithm. The main advantage of parallel abstraction is that several
localized abstraction problems can be solved simultaneously by
dividing a large-scale network abstraction problem into smaller in
size localized problems.
Definition 4: A base subgraph G0 of a network is a subgraph which
is formed by those feedback links that will stay unchanged throughout
the abstraction process.
Let us denote Laplacian matrix of a base subgraph G0 by L0 . For a
given natural number p, the original coupling graph can be partitioned
as the union of a base subgraph and p other subgraphs G1 , . . . , Gp ,
i.e.,
p
X
L = L0 +
Li ,
(81)
i=1

where Li is Laplacian matrix of subgraph Gi . Without loss of
generality, one may assume that the node set of all subgraphs is
V, where V is the node set of the original graph. This assumption
implies that the corresponding Laplacian matrices are compatible
n-by-n matrices. The network setup for parallel implementation of
abstraction takes the following form

ẋ(t) = −L0 x(t) + u(t) + ξ(t)



p

X
u(t) = −
Li x(t)
(82)


i=1


y(t) = Mn x(t)

with initial condition x(0) = x0 .
Assumption 4: The corresponding subgraphs to Li for i = 1, . . . , p
are link-disjoint and dense.
Theorem 8: Suppose that a linear consensus network with structure
(82), a homogeneous systemic performance measure ρ : Ln → R+ of
order −α, and a number d > 2 are given. If the coupling
graph of the
√
8d
network can be decomposed as (81), then for ǫ = d+2
there exists a
set of subgraph sparsifier {Ĝi }pi=1 for {Gi }pi=1 where each sparsifier
subgraph has at most dn/2 links and the global performance index
satisfies
P
P
Πρ (L0 + pi=1 Li ) − Πρ (L0 + pi=1 L̂i )
≤ ǫ.
(83)
Pp
Πρ (L0 + i=1 L̂i )
Furthermore, it follows that

wtotal (L̂i ) ≤ (1 + ǫ) wtotal (Li ),
L0 .

(79)

(L0 + L̂1 )
√

PARALLEL N ETWORK A BSTRACTION

(L0 + L1 ). (80)

Using
√ (80) and the result of Theorem 3, it yields that N(L0 + L̂1 ) is
8d
, d)-abstraction of N(L0 + L1 ).
a ( d+2
This result is particularly useful is abstraction of large-scale
consensus networks where the control objective is to abstract only
desired parts of a network without drastically affecting the global
performance.

for i = 1, 2, · · · , p.
Proof: For every i = 1, · · · , p, coupling subgraph Gi =
(V, Ei , wi ) has a weighted subgraph Hi = (V, Êi , ŵi ) with |Eˆi | =
⌈d(n − 1)/2⌉ whose Laplacian satisfies
√
d+1+2 d
√ Li
Li  LHi 
(84)
d+1−2 d
where LHi is the Laplacian matrix of graph Hi [17, Th. 1.1]. We
define every Ĝi = (V, Êi , ŵi ) according to the following Laplacian
matrix
p
(1 − d/2)2
(85)
LHi .
L̂i :=
1 + d/2
By putting (84) and (85) together, it follows that
√ !
√ !
8d
8d
Li  L̂i 
1+
Li .
1−
d+2
d+2

(86)

12

Moreover, we know that
√ !
8d
1−
L0  L0 
d+2

1+

√

8d
d+2

!

L0 .

(87)

From (86) and (87), we get
!
√
p
p
X
X
2d
(L0 +
Li )  L0 +
L̂i
1−
d/2 + 1
i=1
i=1
!
√
p
X
2d
(L0 +
Li ). (88)
 1+
d/2 + 1
i=1

From (88) and the√ result of Theorem 3, one can conclude that N(L0 +
Pp
Pp
8d
i=1 L̂i ) is a ( d+2 , d)-abstraction of N(L0 +
i=1 Li ).
Algorithm 1 can be implemented on several parallel localized processing units to abstract every Gi for i = 1, · · · , p. This parallelization
scheme cuts the time complexity of solving an abstraction problem
down to Õ(mmax ), where mmax is the number of links of the densest
graph among G1 , . . . , Gp .
VIII.

S HORTCOMINGS OF ℓ0 /ℓ1 -R EGULARIZED S PARSIFICATION
M ETHODS

In order to put our proposed methodology into perspective, we
discuss some of the shortcomings of the ℓ0 /ℓ1 -regularization based
sparsification methods. The common approach is to formulate an
optimal control problem that is augmented by a penalty term to
promote sparsity. The resulting optimal control problem can be
usually cast as a bilinear matrix optimization problem and convexified
using alternating methods [5], [34]. While ℓ0 /ℓ1 -regularization based
methods generally do not scale with network size and suffer from
high time complexities, we would like to accentuate a more important
issue by means of an example that shows ℓ0 /ℓ1 -regularized methods
do not always return sparse solutions. Let us consider a linear
consensus network that is governed by (7) whose feedback structure
is represented by a complete graph with identical link weights w0 ,
Laplacian matrix L0 , link set E0 , and incidence matrix E0 . The
control objective is to eliminate or reweigh some links of the network
while minimizing H2 -norm of the network from ξ to y. This problem
can be formulated as the following ℓ0 -problem
γ
Minimize kGF k2H2 +
kAF kℓ0
(89)
w(e)
2
subject to:
X
w(e)be bT
(90)
F =
e
e∈E0

w(e) ≤ w0

L0 − F ∈ Ln

(91)

(92)

in which GF (s) is the transfer matrix of network N(L0 − F ) from ξ
to y, AF is the adjacency matrix of N(L0 − F ), and be is the column
of incidence matrix E0 that corresponds to link e. Boundedness of
the cost function as well as constraint (92) ensures connectivity of the
coupling graph and positive semi-definiteness of the Laplacian matrix
of N(L0 − F ). In the penalty term, γ > 0 is a design parameter and
ℓ0 sparsity measure of matrix AF is equal to the total number of
nonzero elements of AF , which is defined by (2). For an undirected
graph, the value of this sparsity measure is equal to twice the number
of the edges. The value of cost function (89) is greater than or equal
to γ(n − 1). One can get arbitrarily close to this lower bound through
the following steps. Let us select a spanning tree T0 from link set E0
and set elements of F in a way that L0 − F becomes the Laplacian
matrix of T0 with link weights w0 − w(e). It is known that quantity
kGF kH2 is bounded if and only if the corresponding coupling graph
to L0 −F has at least n−1 links [12], which in our case T0 does have

n − 1 links. Therefore, the value of kGF kH2 can be made arbitrarily
close to 0 by letting w(e) get closer to −∞.
After relaxing ℓ0 -measure by ℓ1 -norm and representing the H2 norm in terms of Laplacian spectrum, the objective function (89) can
be rewritten as
n
1X
γ
kAF kℓ1
(93)
λi (L0 − F )−1 +
2 i=2
2
where kAF kℓ1 is equal to the sum of the absolute values of all
elements of AF and
X
(w0 − w(e)) = Tr(L0 − F ).
kAF kℓ1 = 2
e∈E0

The cost function (93) can be simplified further to obtain
n
n
1X
γ X
λi (L0 − F )−1 +
λi (L0 − F ).
2 i=2
2 i=2

(94)

Thus, the ℓ1 -problem is the minimization problem with cost function (94) and constraints (90)-(92). This problem is convex and has
a unique solution. This follows from the following facts that H2 norm is a systemic measure and convex, trace is a linear operator and
convex, and sum of these two convex functions results in a convex
cost function (94). The inequality (91) also represents a convex set.
Moreover, positive semi-definiteness of L0 − F and connectivity
of the resulting network N(L0 − F ) are both convex constraints;
therefore, constraint (92) is convex. By applying the arithmetic and
geometric means inequality, one can show that the spectral function
√
(94) is lower bounded by constant (n − 1) 2γ. By respecting all the
constraints and for all design parameters γ > 8n21w2 , this lower bound
0
can be achieved by a complete graph with identical link weights
∗
1
w(e) = n√2γ − w0 . An interesting scenario happens when γ = 2
and w0 > 14 n−1 where the lower bounds on the least achievable cost
values for both ℓ0 -problem and its relaxed ℓ1 -problem coincide and
become 2(n − 1). In this case, the optimal networks from solving the
ℓ0 -problem and ℓ1 -problem have very different sparsity patterns: the
ℓ0 -problem solution is a network with a spanning tree topology and
arbitrarily large link weights, while ℓ1 -problem identifies a network
whose coupling graph is complete with identical link weights. This
shows that ℓ1 -relaxation of a ℓ0 -regularized optimal control does not
always provide sparse solutions.
IX.

I LLUSTRATIVE E XAMPLES

In this section, we present several numerical examples to illustrate
our theoretical findings.
Example 1: We first consider a consensus network with 40 agents
defined over an unweighted coupling graph with two dense components which are connected by a single link, i.e., a cut edge. Each of
the components is obtained by adding 100 uniformly and randomly
selected links to an empty graph with 20 nodes; see Fig. 5(a).
Based on Algorithm 1, we sample low-connectivity coupling links
(i.e., feedback gains) with high probability and high-connectivity
coupling links with low probability. The probability of selecting a
link from the coupling graph is depicted in Fig. 6. One observes that
the probability of selecting the cut edge as an important link is much
higher than the probability of choosing other links. Fig. 5(b) shows a
(0.5, 3.05)-abstraction of the network after applying Algorithm 1 that
has 61 links and meets all requirements of Definition 3. The coupling
graph of the abstraction is weighted and has about 70% fewer links
than the original network. Although, we set ǫ = 0.5 when running
Algorithm 1, the performance loss of the resulting abstraction is less
than 24% according to Table II.

13
|Πρ (Ls )−Πρ (L)|
Πρ (Ls )

Systemic Performance Measure
System Hankel Norm: 21 λ2 −1
P
−1
Squared H2 Norm: 21 n
i=2 λi
Zeta Spectral Norm:

P

Local Deviation Error:

1
2

n
i=2

P

19.65 %
18.34 %

di

1
2

15.26 %

−1

23.16 %

λi −2

i∈V

× 100

TABLE II: Relative performance loss percentage of network Fig. 5(a)
with respect to its abstraction Fig. 5(b).

0.9

(a)

10

4

10
0.8

20

0.7

30

0.6

40

0.5

50

20

3.5

30

3

40

2.5

50
2

60

0.4

60

70

0.3

70

80

0.2

80

90

0.1

90

100
20

40

60

(a)

(b)
Fig. 5: (a) An unweighted coupling graph with 40 nodes, 201 links,
kGkH2 = 2.7837, and wtotal (L) = 201. (b) An abstraction of Fig. 5(a)
with 40 nodes, 61 links, kGs kH2 = 3.0805, and wtotal (Ls ) = 199.88.

80

100

0

1.5
1
0.5

100
20

40

60

80

100

0

(b)

Fig. 7: (a) This plot demonstrates the sparsity pattern of adjacency matrix
of network in Example 2 with coupling parameters c = 1 and γ = 0.05.
This network has 100 agents and 4, 950 links and the color intensity at
each pixel of this plot shows magnitude of the corresponding element
in the adjacency matrix. (b) This plot depicts the sparsity pattern of
adjacency matrix of an abstraction that has 1114 links. The relative H2
error of these two networks is kG − Gs kH2 /kGkH2 = 0.18 and the ratio
of their total weights is wtotal (Ls )/wtotal (L) = 1.0028.

0.03

Probability

0.025

replacements

0.02
0.015
0.01
0.005
0

0

20

40

60

80

100

120

140

160

180

200

Label of links
Fig. 6: The probability of selecting a link of the coupling graph given
by Fig. 5(a) as an important link. A cut edge is the most important link
with the highest probability: if we throw out the cut edge, the coupling
graph of the resulting abstraction will be disconnected for sure.

Example 2: Let us consider a consensus network with 100 agents
and exponentially decaying couplings that are defined by

w({i, j}) =



c e−γ|i−j|
0

if i 6= j
if i = j

(95)

where c and γ are positive numbers and i, j ∈ V. This class of networks arises in various applications where there is a notion of spatial
distance between the subsystems; we refer to [18] for more details.
Fig. 7(a) shows the adjacency matrix of the coupling graph of this
network. According to Theorem 4, this network has a (0.5, 27.85)abstraction. Fig. 7(b) illustrates a (0.5, 22.28)-abstraction of the
network after applying Algorithm 1, where the design parameter ǫ is
set to 0.5. The original network has 4, 950 links, while its abstraction
has 1, 114 coupling links and meets all requirements of Definition 3.
As a result, abstraction achieves 77.49 % sparsification. Although, in

this example, we allow 50% performance loss, numerous simulation
examples assert that the resulting bounds for performance loss can be
comparably smaller. As it is seen from Table III, the relative performance loss percentage is less than 11%. Fig. 8 depicts the probability
distribution of sampling process to select important links in Algorithm
1, where the color intensity of pixels show how important that link
is. According to Algorithm 1, low-connectivity coupling links are
sampled with higher probability than high-connectivity coupling links.
Example 3: Let us consider a dynamical network consists of 100
agents which are randomly distributed in a 30 × 30 square-shape
area in space and are coupled over a proximity graph. Every agent
is connected to all of its spatial neighbors within a closed ball of
radius r = 10. Fig. 9(a) shows the resulting coupling graph of
this dynamical network that has 100 nodes and 1, 291 links and
Fig. 9(b) depicts an(0.5, 16.62)-abstraction of this network, which
is obtained using Algorithm 1 with ǫ = 0.5. The number of coupling
links in this abstraction is 831, which is 35.63% sparsification, and
meets all requirements of Definition 3. Table IV summarizes the
percentage of the relative performance loss with respect to some
systemic performance measures.
Example 4: Let us consider a simple model for the formation
control of a group of autonomous vehicles, which is given by

 




0
x(t)
0
I
ẋ(t)
ξ(t) (96)
+
=
I
v(t)
−L −βL
v̇(t)
y(t) = Mn v(t)
(97)
where β > 0 is a design parameter. Each vehicle has a position
and a velocity variable. The state variable of the entire network
is denoted by [ x(t) v(t) ]T and is measured relative to a prespecified desired trajectory xd (t) and velocity vd (t). Without loss of
generality, we may assume that the position and velocity of each

14
|Πρ (Ls )−Πρ (L)|
Πρ (Ls )

Systemic Performance Measure
System Hankel Norm: 12 λ−1
P 2
−1
Squared H2 Norm: 12 n
i=2 λi
Zeta Spectral Norm:

P

Local Deviation Error:

1
2

n
i=2

P

λ−2
i

× 100

10.72 %
6.44 %
1

2

9.69 %

−1
i∈V di

3.07 %

TABLE III: Relative performance loss percentage of network Fig. 7(a)
with respect to its abstraction Fig. 7(b) that has 77.49 % fewer links.

−4

x 10
9
10
8
20
7
30
6
40

(a)

5

50

4

60
70

3

80

2

90

1

100
20

40

60

80

100

0

Fig. 8: This plot presents the probability distribution of the sampling
process to choose important links in Example 2. The color intensity of
each pixel shows importance of that link for sampling.

vehicle are scalar variables. The reason is that one can decouple
higher D-dimensional models into D decoupled (96)-(97) models.
The overall objective is for the network to reach a desired formation
pattern, where each autonomous vehicle travels at the constant desired
velocity vd while preserving a pre-specified distance between itself
and each of its neighbors. In this model, the state feedback controller
uses both position and velocity measurements and L is, in fact, the
corresponding feedback gain, which represents the coupling topology
in the controller array, and constant β is a design parameter [28], [35].
We consider the steady-state variance of the performance output of
this network as the performance measure. This quantity is indeed
equivalent to the square of the H2 -norm of the system from the
exogenous disturbance input to the performance output [28], [35]–
[39]. The squared H2 -norm of (96)-(97) can be characterized in terms
of Laplacian eigenvalues of the coupling graph as follows
n
h
i
1 X −2
1 2
Θ22 (L) := lim E y T (t)y(t) =
ζ (L). (98)
λ
=
t→∞
2β i=2 i
2β 2

We refer to [11] for more details. This quantity is a homogeneous
systemic performance measure; therefore, we can apply our abstraction algorithm. Suppose that the coupling graph of network (96)-(97)
is given by Fig. 9(a). Then, as we mentioned in Example 3, Fig. 9(b)
illustrates one example of (0.5, 16.62)-abstraction of this network that
is obtained using Algorithm 1. As shown in Example 3, this network
has fewer coupling links (831 links) compare to the original network.
Table V presents the percentage of the relative performance loss,
where both systemic performance measures are homogeneous of order
−2. This example shows that our proposed abstraction algorithm can

(b)
Fig. 9: (a) An unweighted coupling (proximity) graph of a consensus
network with 100 agents is presented. Every agent is connected to all
of its spatial neighbors within a closed ball of radius r = 10. This
graph has 1, 291 links and wtotal (L) = 1, 291. (b) This graph shows a
(0.5, 16.62)-abstraction of the network. Our abstraction algorithm results
in a network with a weighted coupling graph that has 831 links and
wtotal (Ls ) = 1293.4. The relative H2 error of these two networks is
kG − Gs kH2 /kGkH2 = 0.17.

be successfully applied to second-order linear consensus networks as
well.
X.

D ISCUSSION

We have introduced a notion of abstraction for a class of linear
consensus networks based on notions of spectral sparsification. There
have been several close-in-spirit notions of graph sparsifications in the
context of theoretical computer science. While these other notions
are interesting for their own sake from a combinatorial standpoint,
their connections to performance analysis and synthesis of dynamical
networks are not trivial and require further scrutiny. In this context,
for a given graph there are several ways to define sparse subgraphs,
namely, distance sparsifiers that approximate all pairwise distances

15
|Πρ (Ls )−Πρ (L)|
Πρ (Ls )

Systemic Performance Measure
Hankel Norm: 12 λ2 −1
P
Squared H2 -Norm: 12 n
i=2
Zeta Spectral Norm:

P

Local Deviation Error:

1
2

P

19.65 %
18.34 %

λi −1

n
i=2

λ−2
i

× 100

1
2

15.26 %

−1
i∈V di

23.16 %

TABLE IV: Relative performance loss percentage of network Fig. 9(a)
with respect to its abstraction Fig. 9(b) that has 35.63% fewer links.

Systemic Performance Measure
Pn
−2
1
Squared H2 -Norm: 2β
i=2 λi
1 Pn
Local Deviation Error: 2β i=1 di −2

|Πρ (L)−Πρ (Ls )|
Πρ (Ls )

× 100

17.58 %
11.38 %

TABLE V: Relative performance loss percentage of network (96)-(97)
with coupling graph Fig. 9(a) with respect to its abstraction Fig. 9(b).

up to a multiplicative and/or additive error (see [40] and subsequent
research on spanners), cut sparsifiers that approximate every cut to
an arbitrarily small multiplicative error [41], spectral sparsifier that
approximate every eigenvalue to an arbitrarily small multiplicative
error [31], and many more. It is shown that sparsifiers can be
constructed by sampling links according to their strength, effective resistance [16], edge connectivity [32], or by sampling random spanning
trees [42]. Benczúr and Karger propose a randomized algorithm to
construct a cut sparsifier in O(m log2 n) time for unweighted graphs
and O(m log3 n) time for weighted graphs [32], [41]. The notion
of spectral sparsifier is stronger than cut sparsifier, which implies
spectral sparsifiers are also cut sparsifiers. One of our current research
directions is to investigate all these methods of sparsification and
explore their connections to dynamical networks.
In our analysis, we assumed that the input matrix of the network
is an identity matrix. Further extension of the current work includes
linear consensus networks over directed coupling graphs with arbitrary input matrices. However, this generalization is challenging and
even the problem formulation demands some appropriate conditions
to guarantee the boundedness of performance measures.
ACKNOWLEDGMENT
The authors would like to thank Yaser Ghaedsharaf for suggesting
materials of Section VIII and Professor Victor M. Preciado for several
fruitful discussions about the subject.
R EFERENCES
[1]

[2]

[3]

[4]

[5]

M. Siami and N. Motee, “Systemic measures for performance and
robustness of large–scale interconnected dynamical networks,” in Proceedings of the 53rd IEEE Conference on Decision and Control, Dec.
2014, pp. 5119–5124.
——, “Schur–convex robustness measures in dynamical networks,” in
Proceedings of the 2014 American Control Conference, 2014, pp. 5198–
5203.
R. Olfati-Saber and R. Murray, “Consensus problems in networks of
agents with switching topology and time-delays,” IEEE Transactions
on Automatic Control, vol. 49, no. 9, pp. 1520–1533, Sept 2004.
M. Siami and N. Motee, “Robustness and performance analysis of cyclic
interconnected dynamical networks,” in Proceedings of the 2013 SIAM
Conference on Control and Its Application, Jan. 2013, pp. 137–143.
M. Fardad, F. Lin, and M. R. Jovanović, “Design of optimal sparse
interconnection graphs for synchronization of oscillator networks,”
IEEE Transactions on Automatic Control, vol. 59, no. 9, pp. 2457–
2462, 2014.

[6] T. H. Summers, F. L. Cortesi, and J. Lygeros, “On submodularity and
controllability in complex dynamical networks,” IEEE Transactions on
Control of Network Systems, vol. 3, no. 1, pp. 91–101, March 2016.
[7] A. Girard and G. J. Pappas, “Approximation metrics for discrete and
continuous systems,” IEEE Transactions on Automatic Control, vol. 52,
no. 5, pp. 782–798, May 2007.
[8] S. Gugercin, A. C. Antoulas, and C. Beattie, “h2 model reduction for
large-scale linear dynamical systems,” SIAM Journal on Matrix Analysis
and Applications, vol. 30, no. 2, pp. 609–638, 2008.
[9] B. Moore, “Principal component analysis in linear systems: Controllability, observability, and model reduction,” IEEE Transactions on
Automatic Control, vol. 26, no. 1, pp. 17–32, Feb 1981.
[10] M. Johansson and A. Rantzer, “Computation of piecewise quadratic lyapunov functions for hybrid systems,” IEEE Transactions on Automatic
Control, vol. 43, no. 4, pp. 555–559, Apr 1998.
[11] M. Siami and N. Motee, “Fundamental limits on robustness measures in
networks of interconnected systems,” in Proceedings of the 52nd IEEE
Conference on Decision and Control, Dec. 2013, pp. 67–72.
[12] ——, “Fundamental limits and tradeoffs on disturbance propagation in
linear dynamical networks,” IEEE Transactions on Automatic Control,
vol. 61, no. 12, pp. 4055–4062, 2016.
[13] X. Wu and M. R. Jovanović, “Sparsity-promoting optimal control of
consensus and synchronization networks,” in Proceedings of the 2014
American Control Conference, 2014, pp. 2948–2953.
[14] S. Hassan-Moghaddam and M. R. Jovanović, “An interior point method
for growing connected resistive networks,” in Proceedings of the 2015
American Control Conference, Chicago, IL, 2015, pp. 1223–1228.
[15] N. Dhingra, F. Lin, M. Fardad, and M. R. Jovanović, “On identifying sparse representations of consensus networks,” IFAC Proceedings
Volumes, vol. 45, no. 26, pp. 305 – 310, 2012.
[16] D. A. Spielman and N. Srivastava, “Graph sparsification by effective
resistances,” in Proceedings of the 14th Annual ACM Symposium on
Theory of Computing, ser. STOC ’08. New York, NY, USA: ACM,
2008, pp. 563–568.
[17] J. Batson, D. Spielman, and N. Srivastava, “Twice-ramanujan sparsifiers,” SIAM Review, vol. 56, no. 2, pp. 315–334, 2014.
[18] N. Motee and Q. Sun, “Sparsity and spatial localization measures for
spatially distributed systems,” SIAM Jounal on Control and Optimization, vol. 55, no. 1, pp. 200–235, 2017.
[19] C. Chen, G. Iyengar, and C. C. Moallemi, “An axiomatic approach to
systemic risk,” Management Science, vol. 59, no. 6, pp. 1373–1388,
2013.
[20] M. Siami and N. Motee, “Growing linear consensus networks via
systemic performance measures,” IEEE Transactions on Automatic
Control, Submitted, 2016.
[21] S. Hawking, “Zeta function regularization of path integrals in curved
space-time,” Communications in Mathematical Physics, vol. 133,
no. 55, 1977.
[22] V. D. Blondel, E. D. Sontag, M. Vidyasagar, and J. C. Willems, Open
Problems in Mathematical Systems and Control Theory.
Springer
Verlag, 1999.
[23] S. Boyd, L. E. Ghaoui, E. Feron, and V. Balakrishnan, Linear Matrix
Inequalities in System and Control Theory.
Society for Industrial
Mathematics, 1997.
[24] M. H. de Badyn, A. Chapman, and M. Mesbahi, “Network entropy: A
system-theoretic perspective,” in Proceedings of 54th IEEE Conference
Decision and Control, Dec 2015, pp. 5512–5517.
[25] K. Glover, “All optimal hankel-norm approximations of linear multivariable systems and their l, -error bounds,” International Journal of
Control, vol. 39, no. 6, pp. 1115–1193, 1984.
[26] J. Borwein and A. Lewis, Convex Analysis and Nonlinear Optimization:
Theory and Examples, ser. CMS Books in Mathematics. Springer New
York, 2005.
[27] S. Boyd., “Convex optimization of graph laplacian eigenvalues,” in Proceedings International Congress of Mathematicians, 2006, pp. 1311–
1319.
[28] B. Bamieh, M. Jovanović, P. Mitra, and S. Patterson, “Coherence in
large-scale networks: Dimension-dependent limitations of local feedback,” IEEE Transactions on Automatic Control, vol. 57, no. 9, pp.
2235 –2249, sept. 2012.

16

[29]
[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]
[41]

[42]

M. Newman, The Laplacian Spectrum of Graphs.
University of
Manitoba, 2001.
M. Rudelson and R. Vershynin, “Sampling from large matrices:
An approach through geometric functional analysis,” Journal
of the ACM, vol. 54, no. 4, Jul. 2007. [Online]. Available:
http://doi.acm.org/10.1145/1255443.1255449
D. A. Spielman and S.-H. Teng, “Nearly-linear time algorithms for
graph partitioning, graph sparsification, and solving linear systems,” in
Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of
Computing, ser. STOC ’04. New York, NY, USA: ACM, 2004, pp.
81–90.
W. S. Fung, R. Hariharan, N. J. Harvey, and D. Panigrahi, “A general
framework for graph sparsification,” in Proceedings of the Forty-third
Annual ACM Symposium on Theory of Computing, ser. STOC ’11.
New York, NY, USA: ACM, 2011, pp. 71–80. [Online]. Available:
http://doi.acm.org/10.1145/1993636.1993647
J. Doyle, K. Glover, P. Khargonekar, and B. Francis, “State-space solutions to standard H2 and H∞ control problems,” IEEE Transactions
on Automatic Control, vol. 34, no. 8, pp. 831–847, Aug 1989.
R. Arastoo, M. Bahavarnia, M. V. Kothare, and N. Motee, “Closedloop feedback sparsification under parametric uncertainties,” in 2016
IEEE 55th Conference on Decision and Control (CDC), Dec 2016, pp.
123–128.
S. Patterson and B. Bamieh, “Network coherence in fractal graphs,” in
Decision and Control and European Control Conference (CDC-ECC),
2011 50th IEEE Conference on, Dec. 2011, pp. 6445–6450.
G. F. Young, L. Scardovi, and N. E. Leonard, “Robustness of noisy consensus dynamics with directed communication,” in American Control
Conference (ACC), 2010, July 2010, pp. 6312–6317.
A. Jadbabaie and A. Olshevsky, “Combinatorial bounds and scaling
laws for noise amplification in networks,” in European Control Conference (ECC), July 2013, pp. 596–601.
B. Bamieh and D. Gayme, “The price of synchrony: Resistive losses
due to phase synchronization in power networks,” in American Control
Conference (ACC), 2013, September 2012, pp. 5815–5820.
E. Lovisari, F. Garin, and S. Zampieri, “Resistance-based performance
analysis of the consensus algorithm over geometric graphs,” SIAM
Journal on Control and Optimization, vol. 51, no. 5, pp. 3918–3945,
2013.
D. Peleg and A. A. Schäffer, “Graph spanners,” Journal of Graph
Theory, vol. 13, no. 1, pp. 609–638, 1989.
A. A. Benczúr and D. R. Karger, “Approximating s-t minimum
cuts in Õ(n2) time,” in Proceedings of the Twenty-eighth Annual
ACM Symposium on Theory of Computing, ser. STOC ’96. New
York, NY, USA: ACM, 1996, pp. 47–55. [Online]. Available:
http://doi.acm.org/10.1145/237814.237827
N. Goyal, L. Rademacher, and S. Vempala, “Expanders via random
spanning trees,” in Proceedings of the Twentieth Annual ACM-SIAM
Symposium on Discrete Algorithms, ser. SODA ’09. Philadelphia, PA,
USA: Society for Industrial and Applied Mathematics, 2009, pp. 576–
585.

Milad Siami received his dual B.Sc. degrees in
electrical engineering and pure mathematics from
Sharif University of Technology in 2009, M.Sc. degree in electrical engineering from Sharif University
PLACE
of Technology in 2011, and M.Sc. and Ph.D. degrees
PHOTO
in mechanical engineering from Lehigh University
HERE
in 2014 and 2017 respectively. From 2009 to 2010,
he was a research student at the Department of
Mechanical and Environmental Informatics at the
Tokyo Institute of Technology, Tokyo, Japan. He is
currently a postdoctoral associate in the Institute for
Data, Systems, and Society at MIT. His research interests include distributed
control systems, distributed optimization, and applications of fractional calculus in engineering. He received a Gold Medal of National Mathematics
Olympiad, Iran (2003) and the Best Student Paper Award at the 5th IFAC
Workshop on Distributed Estimation and Control in Networked Systems
(2015). Moreover, he was awarded RCEAS Fellowship (2012), Byllesby
Fellowship (2013), Rossin College Doctoral Fellowship (2015), and Graduate
Student Merit Award (2016) at Lehigh University.

Nader Motee (S’99-M’08-SM’13) received his
B.Sc. degree in Electrical Engineering from Sharif
University of Technology in 2000, M.Sc. and Ph.D.
degrees from University of Pennsylvania in Electrical
PLACE
and Systems Engineering in 2006 and 2007 respecPHOTO
tively. From 2008 to 2011, he was a postdoctoral
HERE
scholar in the Control and Dynamical Systems Department at Caltech. He is currently an Associate
Professor in the Department of Mechanical Engineering and Mechanics at Lehigh University. His current
research area is distributed dynamical and control
systems with particular focus on issues related to sparsity, performance, and
robustness. He is a past recipient of several awards including the 2008 AACC
Hugo Schuck best paper award, the 2007 ACC best student paper award, the
2008 Joseph and Rosaline Wolf best thesis award, a 2013 Air Force Office of
Scientific Research Young Investigator Program award (AFOSR YIP), a 2015
NSF Faculty Early Career Development (CAREER) award, and a 2016 Office
of Naval Research Young Investigator Program award (ONR YIP).

