52

Int. J. Sensor Networks, Vol. 17, No. 1, 2015

A decentralised linear programming approachto energy-efficient event detection
Kun Yuan and Qing Ling*
Department of Automation,
University of Science and Technology of China,
Hefei, Anhui 230027, China
Email: kunyuan@mail.ustc.edu.cn
Email: qingling@mail.ustc.edu.cn*Corresponding author

Zhi Tian
Department of Electrical and Computer Engineering,Michigan Technological University,
Houghton, Michigan 49931, USA
Email: ztian@mtu.edu
Abstract: This paper addresses the problem of decentralised event detection in a large-scale
wireless sensor network (WSN), where without the coordination of any fusion centre, sensor
nodes autonomously make decisions through information exchange with their neighbours. We
formulate the event detection problem as a linear program, and propose a heuristic decentralised
linear programming (DLP) approach to solve it. Compared to the existing algorithms which solve
decentralised optimisation problems, the DLP algorithm requires low communication cost periteration and shows fast convergence. Convergence property of the DLP algorithm is theoreticallyanalysed, and then validated through simulation results. We also implement the DLP algorithm inthe structural health monitoring application and demonstrate its effectiveness in decentralised event
detection.
Keywords: WSN; wireless sensor network; decentralised optimisation; event detection; linear
programming.
Reference to this paper should be made as follows: Yuan, K., Ling Q. and Tian, Z. (2015)‘A decentralised linear programming approach to energy-efficient event detection’, Int. J. Sensor
Networks, Vol. 17, No. 1, pp.52–62.
Biographical notes: Kun Yuan received the BE in Telecommunication Engineering from Xidian
University in 2011. He is now pursuing his MS in Control Theory and Control Engineering at the
Department of Automation, University of Science and Technology of China. His current research
focuses on decentralised optimisation of networked multi-agent systems.
Qing Ling received the BE in Automation and the PhD in Control Theory and Control Engineeringfrom University of Science and Technology of China in 2001 and 2006, respectively. From 2006
to 2009, he was a postdoctoral research fellow with the Department of Electrical and Computer
Engineering, Michigan Technological University. Since September 2009, he has been an Associate
Professor with the Department of Automation, University of Science and Technology of China. His
current research focuses on decentralised optimisation of networked multi-agent systems.
Zhi Tian received the BE in Automation from the University of Science and Technology of China
in 1994, the MS and PhD in Electrical Engineering from George Mason University in 1998 and
2000, respectively. Since August 2000, she has been with the Department of Electrical and Computer
Engineering, Michigan Technological University, where she is currently a Professor. Her researchinterests are in the areas of signal processing for wireless communications, estimation and detection
theory. She served as Associate Editors for IEEE Transactions on Wireless Communications andIEEE Transactions on Signal Processing. She received a CAREER award in 2003 from the US
National Science Foundation.

Copyright © 2015 Inderscience Enterprises Ltd.

A decentralised linear programming approach to energy-efficient event detection

1 Introduction
Event detection is one of the most important applications ofwireless sensor networks (WSNs) (Ling et al., 2010). Typicalevent detection tasks include detecting nuclear radioactive
sources (Sundaresan et al., 2007), monitoring structural
health conditions (Lynch, 2007), discovering presence ofcontaminants (Sun and Coyle, 2010), to name a few. In a
traditional event detection WSN, data collection and signal
processing are separated. A fusion centre collects sensory datafrom distributed wireless sensor nodes, and then processes
the sensory data to accomplish the event detection task. Sucha centralised infrastructure suffers from sharp degradationsof energy efficiency and robustness when the network scale
increases (Liu et al., 2011).
To address this issue, decentralised algorithms in WSNs
have attracted considerable research interest in recent years(Rabbat and Nowak, 2006; Nedic and Ozdaglar, 2009; Predd
et al., 2007; Zhu et al., 2007; Schizas et al., 2008; Bazerqueand Giannakis, 2010; Ling and Tian, 2010; Jakovetic et al.,2011). In the absence of any fusion centre, sensor nodes
autonomously exchange information with their neighbours
and collaboratively detect the events. This decentralised
infrastructure, compared to the traditional centralised one,
avoids collecting sensory data to a fusion centre while exploits
collaboration of neighbouring sensor nodes to realise innetwork signal processing. Therefore, the network can achieve
lightweight communication and improved energy efficiency.
In addition, avoiding centralised collection of sensory dataalso strengthens network robustness since the network nolonger relies on several critical sensor nodes to relay sensory
data. For detailed discussions on the benefits of decentralised
algorithms in WSNs, readers are referred to Predd et al. (2007).
This paper elaborates on developing an energy-efficientand robust decentralised algorithm, which scales with network
size, for the event detection application of WSNs. Specifically,
we confine the event sources to be at a set of candidate
positions (here we use sensor node positions as candidate
positions), and model the event detection problem as
recovering a decision vector which represents the event
magnitudes at the candidate positions. Though the existing
decentralised in-network signal processing techniques, suchas consensus optimisation, are applicable to this recovery
problem, they often lead to high communication cost (Schizas
et al., 2008; Bazerque and Giannakis, 2010; Ling and Tian,
2010; Jakovetic et al., 2011). For example, in the consensus
optimisation formulation, each sensor node holds a local copyof the signal to recover, and the local copies of neighbouring
sensor nodes consent to the same value. Decentralised iterativealgorithms which solve the consensus optimisation problem
require sensor nodes to exchange their current local copies
with their neighbours; therefore, for each sensor node, thecommunication cost per iteration is proportional to the size of
its local copy (Schizas et al., 2008; Bazerque and Giannakis,
2010; Ling and Tian, 2010; Jakovetic et al., 2011). Since thesize of each local copy is equal to the number of sensor nodes inour model, the communication cost per sensor node increases
at least linearly with the network size, which is unacceptable
for large-scale WSNs.

53

This paper develops a decentralised linear programming(DLP) algorithm to solve the event detection problem inan energy-efficient manner. Different from the consensus
optimisation technique, we set an alternative objective thatis simple yet effective. Sensor nodes no longer optimise andconsent on the entire decision vector as in the consensus
optimisation approach; in contrast, we let each sensor node
optimise its own decision variable corresponding to a scalarelement in the decision vector. Indeed, each sensor node solves
a simple linear program through limited communication with
its neighbouring sensor nodes. This strategy works since
the sensory data in the event detection application often
exhibits local correlation other than global correlation; that
is, an occurring event only influences the measurements ofsome nearby sensor nodes, but has little effect on faraway
sensory readings. Therefore, recovering the whole decision
vector at each sensor node and letting the whole network
reach consensus are both unnecessary. Theoretically, we provethat under mild conditions, the DLP algorithm approximately
solves the original event detection problem. We further showthat for a certain scenario, the DLP algorithm converges
to the exact solution; this scenario appears in applications
such as structural health monitoring, etc. Compared tothe alternating direction method (ADMM) algorithm whichsolves the consensus optimisation problem, the proposed
DLP algorithm shows much faster convergence and lower
communication cost through numerical simulation.
This paper is organised as follows. The event detection
problem is formulated in Section 2. Section 3 proposes
the DLP algorithm and Section 4 theoretically analyses its
convergence property. Numerical simulation and applicationin structural health monitoring are demonstrated in Sections 5
and 6, respectively. Section 7 concludes the paper.

2 Problem formulation
Suppose that a large-scale WSN is densely deployed in a
two-dimensional sensing field. The network has a set of L
sensor nodes, denoted as L = {vi }L
i=1 . Sensor nodes have acommon communication range rC . Each sensor node can andonly can communicate with its one-hop neighbours within
the communication range, and no multi-hop communicationis permitted to avoid excessive coordination efforts. Given
the communication range rC , the network is bidirectionallyconnected.
The event detection task is performed periodically. Withineach sampling period, multiple events may occur in the sensing
field. Each event has an influence on part of the sensing field,
centring around the source of the event; influences of multiple
events are then superposed on the whole sensing field. After
collecting the sensory data, distributed sensor nodes cooperate
to localise the sources and estimate the amplitudes of theevents.
To make the event detection problem tractable, we assume
that there are a set of candidate positions for the event
sources. Typical choices of candidate positions include virtual
grid points in the sensing field (Bazerque and Giannakis,
2010) and positions of sensor nodes (Ling and Tian, 2010).

54

K. Yuan et al.

Setting the virtual grid points as the candidate positions
makes the resolution of event detection adjustable; however,in decentralised algorithm design, this setting requires eachsensor node to detect all events in the whole sensing field,
and hence brings high communication cost (Bazerque andGiannakis, 2010). Contrarily, by choosing the positions of thesensor nodes as the candidate positions, the resolution of event
detection is directly decided by the density of the sensor nodes.
When the WSN nodes are densely deployed, this setting makes
sense. More importantly, this setting simplifies decentralised
algorithm design since each sensor node only needs to detect
whether there is an event occurring at its own position, as weshall see below. Therefore, we assume that
(A1) Events occur only at the positions of some sensor nodes.
When the source of one event coincides with the position of
vj , we denote the amplitude of the event by a scalar cj > 0;otherwise cj = 0.
Based on (A1), we can formulate the event detection problem
as recovering a nonnegative vector c = [c1 , ..., cL ]T from thesensory data. Figure 1 shows the case where sensor nodes are
deployed randomly in the sensing field and events occur at
sensor node points.
Figure 1 Blue points are 400 sensor nodes deployed randomly inthe sensing field, red squares are events, and red circles
are events’ influence areas (see online version
for colours)

and fij = fji . We suppose that fij = 0 if dij ≥ rC , where dij
is the distance between sensor nodes vi and vj .
The assumption (A2) enables design of simple decentralised
algorithms, since it eliminates the interrelationship between
multi-hop sensor nodes and avoids the necessity of multi-hop
communications.
Finally, we make a commonly-used assumption that the
influences of the events are linearly superposed. Combining
with (A2), we have(A3) The measurement of one sensor node is the superpositionof the influences of all events plus random noise. Since fij =0 for ∑dij ≥ rC , the measurement bi of vi can be written asbi = vj ∈Ni ∪vi fij cj + ei , where ei is random noise, and Ni
denotes the one-hop neighbours of vi .
We now introduce a key observation that the vector c, which
we want to recover, is sparse. That is, the number of nonzero
elements in c is much smaller than the vector size L. Thisprior knowledge holds since event detection for a large-scale
WSN is meaningless if the sensing field is full of event sources.
Nevertheless, we do allow the influences of these sparse eventsto span over the whole sensing field. Hence, reconstruction of cboils down to minimising a sparsity-imposing metric ||c||1 thatis the ℓ1 norm of c (Donoho, 2006), subject to measurement
constraints. From (A3), two similar formulations arise, one isa linear program that postulates a bound θ of measurement
noise at each sensor nodes:
min ||c||1c∑s.t. |bi − vj ∈Ni ∪vi fij cj | ≤ θ, ∀vi ∈ L
ci ≥ 0, ∀vi ∈ L.

Sensor Deployment
20

(1)

18

And the other is a second-order cone program that confines
the total energy of the measurement noise to be lower than ϵ:1614

min ||c||1
c
∑
∑
2
s.t.
vj ∈Ni ∪vi fij cj ) ≤ ϵvi ∈L (bi −ci ≥ 0, ∀vi ∈ L.

12
10

(2)

8
6
4
2
0

0

5

10

15

20

Next, we notice that in many event detection applications, one
event only has a limited influence on its nearby region in thesensing field. For example, in nuclear radioactive detection,
the influence of a nuclear source decreases polynomiallyin distance. Similar distance-dependent influences can beobserved from events such as fire sources and structural
damages. By carefully setting the communication range rC ,we can confine the influence of an event occurring at theposition of one sensor node to the range of the sensor node’s
one-hop neighbours; more specifically.
(A2) Each event only influences its nearby region in
the sensing field. The influence of a unit-amplitude event
occurring at the position of vj on the sensor node vi is fij ,Both equations (1) and (2) incorporate the prior knowledge ofsparse events, which is important in alleviating the undesired
false alarm rates of otherwise non-sparse solutions produced
by general signal recovery approaches such as thresholding or
least squares. In this paper, we focus on the linear program
equation (1) and devote to designing an efficient algorithm aswell as analysing its recovery performance.

3 Decentralised algorithms
Indeed, we can reformulate the event detection problem (1) asa consensus optimisation problem via introducing local copiesof c and imposing equality constraints on the local copies
of neighbouring sensor nodes. This consensus optimisation
problem can be solved based on the alternating direction
method of multipliers (ADMM) (Bertsekas and Tsitsiklis,
1997). For details of the ADMM-based decentralised
algorithm, readers are referred to Bazerque and Giannakis(2010) and Ling and Tian (2010). However, the resulting
decentralised algorithm requires each sensor node to share its

A decentralised linear programming approach to energy-efficient event detection
current local copy of c with its neighbouring sensor nodes.
Since in our model, the size of c is equal to the number of
sensor nodes, this approach does not scale when the network
size increases. Further, the consensus optimisation scheme
requires that all sensor nodes reach a consensus, which often
brings slow convergence rate for a large-scale WSN.
To reduce the communication cost per iteration as well as
accelerate the algorithm, this paper proposes a heuristic DLP
algorithm to solve equations (1). Specifically, sensor node vi
solves the following linear program:min cici

s.t. |bi − fii ci −ci ≥ 0.

∑

vj ∈Ni fij cj | ≤ θ(3)Indeed, equation (3) is corresponding to part of the objectivefunction and part of the constraints of equation (1).
equation(3)
isci = [bi − θ −∑ Solution + to
+
f
c
]
/f
.
Here
[·]
denotestheprojection toiij∈Ni ij jmax{·, 0}. Therefore we have the following heuristic DLP
algorithm as in Algorithm 1.

Algorithm 1 Decentralized Linear Programming(DLP) Algorithm for sensor vi
Require: Event influence set Ni , coefficient vector Fi =[fi1 , fi2 , · · · , fiL ]T , measurement bi and predefined
threshold θ
1: Initialize ci = 0;
2: for t = 0, 1, 2, . . ., sensor vi do
3:Transmit ci (t) to, and receive cj (t) from j ∈ Ni ;4:
Updateci (t + 1) according to ci = [bi − θ −P+j∈Ni fij cj ] /fii
5: end for
6: Returns ci (t + 1).

55

Before going to the theoretical analysis, we rewrite
equation (1) to its equivalent matrix form as
min 1T ccs.t. Fc − b ≥ −θ1
Fc − b ≤ θ1
c ≥ 0.

(4)

Here 1 = [1, 1, ..., 1]T is an L × 1 vector, b = [b1 , b2 , ..., bL ]Tcontains sensory measurements, and
f11 · · · f1L
F =  ... . . . ...  .
fL1 · · · fLL
In the matrix F, all diagonal elements are 1; an off-diagonal
element fij ≥ 0 and fij = 0 if vj ∈/ Ni ∪ vi . Since fij = fji ,F is symmetric.
Proposition 1: If a symmetric non-negative matrix F isstrictly diagonally dominant and all of its diagonal elements
are equal to 1, then the proposed DLP algorithm converges tothe optimal solution of a linear programming problem
min 1T Fc
cs.t. Fc − b ≥ −θ1c ≥ 0.

(5)

Proof: It is proved in Mangasarian (1976) that if a nonnegative
matrix F is strictly diagonally dominant, then the optimal
solution of linear program (5) is equivalent to that of thefollowing linear complementarity problem:cT (Fc − b + θ1) = 0, s.t. Fc ≥ b − θ1, c ≥ 0.

(6)

Let us rewrite (6) into a quadratic program
min cT (Fc − b + θ1)cCompared with the ADMM-based decentralised algorithm,
the DLP algorithm just needs to exchange its own decisionvariables ci , other than the local copy of c hold by itself with
its neighbours. This way, the communication cost per iteration
can be greatly reduced. Further, as we will demonstrate withnumerical simulation, the DLP algorithm converges much
faster than the ADMM-based decentralised algorithm. The
two properties make the DLP algorithm very energy-efficientin the event detection application.

4 Convergence property of DLP
In this section, we elaborate on the convergence property ofthe proposed DLP algorithm. First, we prove that under mild
conditions, the DLP algorithm solves an optimisation problem
which is similar to the original linear program (1). Second,
we further show that for a certain scenario, the DLP algorithm
exactly converges to the optimal solution of equation (1);this scenario appears in applications such as structural healthmonitoring, etc.

s.t. Fc − b ≥ −θ1c ≥ 0.

(7)

As proved in Mangasarian (1991), if F = P + Q and P −Q are both positive definite, and F, P, and Q are all
symmetric, then the quadratic program (7) can be solved bya matrix splitting algorithm c(t + 1) = [c(t + 1) − (Pc(t +1) + Qc(t) − b + θ1)]+ .
Let P = I be an L × L identity matrix, then Q = F −I. Obviously F, P, and Q are all symmetric matrices. Notethat F and P − Q = 2I − F are both symmetric and strictly
diagonally dominant, F and P − Q are both positive definite.
The corresponding matrix splitting algorithm to (7) is hencec(t + 1) = [b − θ1 − (F − I)c(t)]+ , which is equivalent to
the DLP algorithm. Therefore, the proposed DLP algorithm
converges to the optimal solution of equation (5).
Remark 1: In Proposition 1, the only notable assumption
is that F is strictly diagonally dominant. It means thatthe influence of an event decays fast enough with respect
to distance. That is, if an event occurs at the positionof sensor node vi with unit magnitude ci = 1, then its

56

K. Yuan et al.

accumulated
influence on other sensor nodes is less than 1,∑
i.e., vj ∈Ni fij < 1.
Proposition 1 shows that under mild conditions, the DLP
algorithm solves equation (5), a linear programming problem
similar to the original problem (4). The objective functionof equation (5) is 1T Fc, which reweights the objectivefunction of equation (4), i.e., 1T c. In addition, the solutionof equation (5) is not necessarily satisfying the inequality
constraint Fc − b ≤ θ1. Note that Proposition 1 only gives
sufficient conditions on the equivalence; the strictly diagonallydominant assumption can be relaxed, as we will demonstratein the simulation results.
Next, we will give an important proposition which guarantees
that the DLP algorithm exactly solves equation (4). This
proposition shows that if the events’ magnitudes are large
enough (i.e., the signal-to-noise ratio is large enough), the DLP
algorithm can converge to the optimal solution of equation (4)with a proper choice of the parameter θ.
Summing on the rows of the coefficient matrix F, wedenote smax and smin the maximum and minimum values,
respectively. Besides, we denote c0 as the vector which
represents real event occurrence in the sensing field. If c0i ̸= 0,
then an event occurs at the position of sensor node vi withmagnitude c0i . Moveover, we denote n as the noise involved
in measurement b. The following proposition proves when the
DLP algorithm exactly solves the original problem (4).

Proposition 2 gives a guideline of adjusting β based on thevalues of smax and smin . When sensor nodes are randomly
deployed, we can estimate smax and smin via the statisticalproperty of F. For applications which allow us deploy sensor
nodes in a regular manner, smax and smin can be exactly
determined. Next we show a special example where sensor
nodes are placed at virtual grid points in the square sensing
field, as shown in Figure 2. In the structure health monitoring
application, as we will show in Section 4, sensor nodes canoften be deployed in this manner.
Figure 2 Blue points are 400 sensor nodes deployed at virtual grid
points, red solid squares are events, and red circles are
events’ influence ranges (see online version for colours)

Sensor Deployment
20
18
16
14
12
10
8
6
4
2

Proposition 2: Suppose that F is symmetric non-negative,
strictly diagonally dominant, all of its diagonal elements are1min −1equal to 1, and ssmax−1 > β > 0. Then for any event occurringat the position of sensor node vi with c0i ≥ (β + 1) ∥n∥∞ ,if we set θ ≥ β ∥n∥∞ , the DLP algorithm exactly solves theoriginal problem (4).
Proof : First, in Appendix A.III, we prove that under the above
conditions, equation (4) is equivalent to:
min 1T ccs.t. Fc − b ≥ −θ1c ≥ 0.

(8)

Second, in Proposition 1, we prove that if F is symmetric nonnegative, strictly diagonally dominant, and all of its diagonal
elements are equal to 1, then the DLP algorithm converges
to the optimal solution of equation (5). Therefore, to prove
Proposition 2, we only need to show the equivalence between
equations (8) and (5), which is shown in Appendix A.IV. 
Remark 2: Proposition 2 indicates that given smax and smin ,if the signal-to-noise ratio is larger than a certain threshold(for any event occurring at vi , c0i ≥ (β + 1) ∥n∥∞ ) and theparameter θ is properly chosen (θ ≥ β ∥n∥∞ ), then the DLP
algorithm exactly solves the original problem (4).
Remark 3: Proposition 2 shows that when θ > β∥n∥∞ ,the DLP converges to (4). Actually, β∥n∥∞ , as shown inAppendix A, is quite a conservative bound for θ. Simulation
results show that for ∥n∥∞ < θ < β∥n∥∞ , DLP may also beable to converge to equation (4).

0

0

5

10

15

20

Corrolary 3: If sensors are deployed as in Figure 2, Then forany event occurring at the position of sensor node vi with c0i ≥5 ∥n∥∞ , if we set θ ≥ 4 ∥n∥∞ , the DLP algorithm exactly
solves equation (4).
Proof: If sensors are deployed as in Figure 2, it is easy to1min −1
deduce that ssmax−1 > 4 . And from Proposition 2, Corollary 3
is established.


5 Simulation results
In our simulation, we divide the sensing field into an N × N
lattice, and deploy L = N 2 sensor nodes at the grid points.
The distance between two neighbouring sensor nodes is r,
such that the lattice grid can be represented by sensor positions{(xr, yr) : x, y = 1, 2, ..., N }. Suppose that events occur atseveral grid points. We use the following basis function toapproximate the influence of unit-magnitude event:
{ d2
− ij
2
fij = fj (vi ) = e σ dij < rE .
(9)0
dij ≥ rE
Here we let rC = rE . In addition, sensory measurements arepolluted by uniformly random noise, ranging from −0.01 to
0.01.

A decentralised linear programming approach to energy-efficient event detection

Figure 3 DLP converges to the optimal solution of equation (4)when θ > 0.01 (see online version for colours)

aerospace and mechanical engineering systems (Lynch, 2007).
The application of WSNs in SHM has attracted much attention
in recent years. By collecting the structure health information
through distributed and unattended sensor nodes, damages oranomalies in a structure can be localised and the severities ofdamages or anomalies can be identified.

Figure 4 DLP vs. ADMM (see online version for colours)
ADMM
1.4

event at (3r,5r)
event at (5r,5r)

1.2

Decision Variable

First we check the convergence property of the
DLP algorithm. Suppose four events with magnitude
0.25, 0.5, 0.75 and 1 (satisfying c0i ≥ 5∥n∥∞ ) occurat (3r, 5r), (4r, 2r), (6r, 6r) and (8r, 7r), respectively.
Meanwhile, σ 2 is set as 0.5 and rE = 0.01 to keep F being
strictly diagonally dominant. Denote c0 as the true event
vector, ctlp as the optimal solution of problem (4) and cdlp as
the fixed point of DLP. ∥ctlp − cdlp ∥2 denotes the gap between
the fixed point of DLP and optimal solution of (4). During
the simulation, θ varies from 0 to 0.04 while ∥n∥∞ is fixed at
0.01.
Figure 3 depicts that when θ > 0.01, DLP converges to the
optimal solution of equation (4). Actually, from the deductionof Proposition 2 we know it is quite conservative to choose
θ > 4∥n∥∞ . DLP performs much better than our theoreticalanalysis.

57

1

0.8

0.6

0.4

0.06

0.2
0.05

||cdlp−dtlp||2

0

0

20

40

60

80

100

Iteration

0.04

DLP
0.03

event at (3r,5r)
event at (5r,5r)

1.2
0.02

0

0

0.005

0.01

0.015

0.02

0.025

0.03

0.035

0.04

θ

Next we compare the convergence between DLP and ADMM.
Suppose two events, with magnitudes 1 and 0.5, occurat (3r, 5r) and (5r, 5r). During the simulation, σ 2 = 0.5,
rE = 0.01, ∥n∥∞ = 0.01 and θ = 0.05. Figure 4 shows
the convergence behaviour of the two algorithms. These
two decentralised algorithms both provide accurate locations
and converge to the solution of model (4). However, theADMM algorithm converges after 90 iterations, while the
DLP algorithm converges after only 4 iterations. With lesscommunication cost per iteration and much faster convergence
rate, DLP greatly improves energy-efficiency of the network.
Finally we will show DLP can also perform well in somecases where F is not diagonally dominant. Note that we canadjust σ 2 to vary the diagonal dominance of F and it is easy toverify that when σ 2 > 0.65 and rE = 0.01, F is not diagonallydominant. Figure 5 shows that when σ 2 ≤ 1.2, DLP will
always converge exactly to the optimal solution of problem(4), but after that, DLP can hardly converge.

0.8

0.6

0.4

0.2

0

0

1

2

3

4

5

6

7

Iteration

Figure 5 DLP can still converge to the optimal solution ofequation (4) even if F is not strictly diagonallydominant. Note DLP cannot converge when σ 2 ≥ 1.2,
where we force it to stop after 200 iterations (see online
version for colours)
1.4

1.2

1

||cdlp−dtlp||2

0.01

Decision Variable

1

0.8

0.6

0.4

6 Structural health monitoring
0.2

This section demonstrates the application of the DLP
algorithm in a structure health monitoring (SHM) network.
SHM refers to the process of damage detection for civil,

0
0.5

0.6

0.7

0.8

0.9

σ2

1

1.1

1.2

1.3

K. Yuan et al.

Figure 6 Two-dimensional model of a steel frame structure with12 stories and 9 bays. Gaussian random white noise is
imposed to the foundation to simulate ambient
vibrations (see online version for colours)

DLP algorithm. We can also observe that the DLP algorithm
converges within 8 iterations, a tremendously fast convergence
rate.
Figure 7 Spatial distribution of the damage sensitive coefficients
after reducing stiffness for the column between (7,5) and(8,5) (see online version for colours)
Damage Sensitive Coefficient

The decentralised SHM system works with three stages (Ling
et al., 2009; Ling and Tian, 2009). Firstly in a modelling stage,
sensor nodes collect baseline responses from a undamaged
structure. Secondly in a statistical pattern recognition stage,
each sensor node collects operational responses and achieves
a damage sensitive coefficient by comparing with baseline
responses. Thirdly in a decentralised decision-making stage,
the damage sensitive coefficients are used to estimate a vector
of damage severity coefficients, which denotes the positions
and severities of damages. Since each damage in a structure
only influences the nearby sensor nodes and the vector ofdamage severity coefficients is often sparse. By restricting thelocations of damages on sensor node points, we can establish
an event detection model as in equation (1).
Consider the example in Ling and Tian (2009). Supposethat there is a steel frame structure with 12 stories and 9bays, simplified as a two-dimensional model, as illustrated in
Figure 6. A grid network of 120 sensor nodes is deployedat the joint points. The width of a bay is 24 feet and theheight of a floor is 14 feet. Ambient vibrations are imposed to
the foundation with Gaussian white noise. Responses of thestructure are analysed by the finite element software OpenSees(Pacific Earthquake Engineering Research Center, 1999). By
reducing 72% stiffness for the column between sensors (7,5)(located in 7th floor, 5th bay) and (8,5) (located in 8th floor,
5th bay), two damages are introduced to the structure. A
typical spatial distribution of the damage sensitive coefficients,
namely b, is shown in Figure 7.

0.15
0.1
0.05
0
−0.05
8

6

4

2

Bay

10

8
6
Story

4

2

12

Figure 8 Convergence of the damage severity coefficients forsensors (7, 5) and (8, 5) when θ = 0.03 (see online
version for colours)
0.12

events at (7r,5r)
events at (8r,5r)

0.1

decision variables

58

0.08

0.06

0.04

0.02

0

1

2

3

4

5

6

7

8

9

10

iterations

7 Conclusion

The measurement matrix F is decided through simulating thestructure. Denoting the positions of vi and vj as (mi , ni )and (mj , nj ), respectively, simulation results indicate that themeasurement coefficient fij ≃ exp(−(mi − mj )2 − (ni −nj )2 ). The communication range rC is set to be slightly larger
than 24 feet, such that each sensor can communicate with
4 neighbouring sensors. The threshold θ = 0.03 in the DLP
algorithm. As depicted in Figure 8, even when the matrix
F under these setting is not diagonally dominant, we canstill successfully detect damages at (7,5) and (8,5) with the

In this paper, we consider energy-efficient event detection witha WSN. We formulate the event detection problem as a linear
program and design a heuristic DLP algorithm to solve it. The
DLP algorithm is with light-weight communication cost periteration and fast convergence rate. The convergence propertyof the DLP algorithm is analysed theoretically. Numericalsimulation in both the synthetic examples and the SHM
application shows that the DLP algorithm outperforms theADMM-based consensus optimisation method.

References
Bazerque, J. and Giannakis, G. (2010) ‘Distributed spectrum sensing
for cognitive radio networks by exploiting sparsity’, IEEE
Transactions on Signal Processing, Vol. 58, pp.1847–1862.

A decentralised linear programming approach to energy-efficient event detection
Bertsekas, D. and Tsitsiklis, J. (1997) Parallel and Distributed
Computation: Numerical Methods, 2nd ed., Athena Scientific.
Dantzig, G. (1963) Linear Programming and Extensions, Princeton
University Press, Princeton, New Jersey, USA.
Donoho, D. (2006) ‘Compressed sensing’, IEEE Transactions on
Signal Processing, Vol. 52, pp.1289–1306.
Jakovetic, D., Xavier, J. and Moura, J. (2011) ‘Cooperative convex
optimization in networked systems: augmented Lagrangianalgorithms with direct gossip communication’, IEEE
Transactions on Signal Processing, Vol. 59, pp.3889–3902.
Ling, Q. and Tian, Z. (2009) ‘A decentralized Gauss-Seidel approach
for in-network sparse signal recovery’, Information Fusion,
2009. FUSION’09. 12th International Conference on, IEEE,
Seattle, USA, pp.380–387.
Ling, Q. and Tian, Z. (2010) ‘Decentralized sparse signal recovery
for compressive sleeping wireless sensor networks’, IEEE
Transactions on Signal Processing, Vol. 58, pp.3816–3827.
Ling, Q., Fanzi, Z. and Tian, Z. (2010) ‘Energy-efficient decentralized
event detection in large-scale wireless sensor networks’,
Acoustics Speech and Signal Processing (ICASSP), 2010
IEEE International Conference on, IEEE, Dallas, USA,pp.3386–3389.
Ling, Q., Tian, Z., Yin, Y. and Li, Y. (2009) ‘Localized
structural health monitoring using energy-efficient wirelesssensor networks’, IEEE Sensor Journal, Vol. 9, pp.1596–1604.
Liu, Y., He, Y., Li, M., Wang, J., Liu, K., Mo, L., Dong, W., Yang, Z.,
Xi, M., Zhao, J. and Li, X. (2011) ‘Does wireless sensor network
scale? A measurement study on GreenOrbs’, INFOCOM, 2011
Proceedings IEEE, IEEE, Shanghai, China, pp.873–881.
Lynch, J. (2007) ‘An overview of wireless structural healthmonitoring for civil structures’, Philosophical Transactions of
the Royal Society A, Vol. 365, pp.345–372.
Mangasarian, O. (1976) ‘Solution of linear complementarity
problems by linear programming’, Numerical Analysis,Vol. 506, pp.166–175.
Mangasarian, O. (1991) ‘Convergence of iterates of an inexact
matrix splitting algorithm for the symmetric monotone linear
complementarity problem’, SIAM Journal of Optimization,
Vol. 1, pp.114–112.
Nedic, A. and Ozdaglar, A. (2009) ‘Distributed subgradient methods
for multi-agent optimization’, IEEE Transactions on AutomaticControl, Vol. 54, pp.48–61.
Pacific Earthquake Engineering Research Center (1999) OpenSees:
Open System for Earthquake Engineering Simulation.
Predd, J., Kulkarni, S. and Poor, V. (2007) ‘Distributed learning inwireless sensor networks’, IEEE Signal Processing Magazine,
Vol. 24, pp.56–69.
Rabbat, M. and Nowak, R. (2006) ‘Quantized incremental algorithms
for distributed optimization’, IEEE Journal on Selected Areasin Communications, Vol. 23, pp.798–808.
Schizas, I., Ribeiro, A. and Giannakis, G. (2008) ‘Consensus in
ad hoc WSNs with noisy links – Part I: distributed estimation ofdeterministic signals’, IEEE Transactions on Signal Processing,Vol. 56, pp.350–364.
Sun, X. and Coyle, E. (2010) ‘Low-complexity algorithms forevent detection in wireless sensor networks’, IEEE Journal on
Selected Areas in Communications, Vol. 28, pp.1138–1148.
Sundaresan, A., Varshney, P.K. and Rao, N.S.V. (2007) ‘Distributed
detection of a nuclear radioactive source using fusionof correlated decisions’, Information Fusion, 2007 10th
International Conference on, IEEE, Quebec, Canada, pp.1–7.

59

Zhu, Y., Liu, Y., Ni, L.M. and Zhang, Z. (2007) ‘Low-power
distributed event detection in wireless sensor networks’,
INFOCOM 2007. 26th IEEE International Conference on
Computer Communications. IEEE, IEEE, Anchorage, USA,
pp.2401–2405.

Appendix A
Notations: In this part upper curlicue letters are used for index
set. By projecting the elements of the column vector a, therows and the columns of the matrix A on the index set I, we
achieve aI , A(I,:) and A(:,I) respectively. Further, we always
use AI in place of A(:,I) for simplicity.

I. Preliminary: the simplex method
Introduce slack variables cL+1 , cL+2 , ..., c2L and rewrite
equation (8) into
max eT xxs.t. Ax = dx ≥ 0,(10)

where e = [−1T , 0T ]T with −1 = [−1, · · · , −1]T and
0 = [0, · · · , 0]T both being L × 1 vectors, d = [−b1 +θ, · · · , −bL + θ]T , x = [c1 , · · · , cL , cL+1 , · · · , c2L ]T , andA = [−F, I].
Let B and N denote the index set of basic variables andnonbasic variables, respectively. Besides, define B = AB and
N = AN , then equation (10) can be transformed into:max

xB ,xNeTB xB + eTN xN

s.t. BxB + NxN = d{xB , xN } ≥ 0(11)Since B is nonsingular, equation (11) can be transformed into:max

xB ,xNeTB B−1 d − ((B−1 N)T eB − eN )T xN

s.t. xB = B−1 d − B−1 NxN{xB , xN } ≥ 0(12)Lemma 4: Suppose x∗ ∈ R2L . If B−1 d ≥ 0 and(B−1 N)T eB − eN ≥ 0, let x∗B = B−1 d and x∗N = 0, thenx∗ is optimal for problem (10).

Proof: See Dantzig (1963).



Define the index set I = {1, 2, ..., 2L}, I1 = {1, 2, ..., L} andI2 = {L + 1, L + 2, ..., 2L}, B1 = {j ∈ I1 , j ∈ B}, B2 ={j ∈ I2 , j ∈ B}, N1 = {j ∈ I1 , j ∈ N } and N2 = {j ∈I2 , j ∈ N }.
Lemma 5: Suppose x∗ is optimal for problem (10), then x∗I1
is optimal for equation (8). If FB1 x∗B1 ≤ b + θ1, the solutionof equation (8) equals that of equation (4).

60

K. Yuan et al.

Proof: The first half is obvious, we now prove thesecond half. Note that the objective functions of the two
problem are exactly the same, and hence we just need toprove Fx∗I1 ≤ b + θ1. Since Fx∗I1 = FB1 x∗B1 + FN1 x∗N1 =
FB1 x∗B1 ≤ b + θ1, and hence the lemma is established. 

Let w̄ij denote the element of matrices B̄−1 in the ith row andjth column. Due to the special structure of B̄, we have
if j ∈ N1 and i = j
1
if j ∈ N1 and i ̸= j .
w̄ij = 0(16)w̄ij if j ∈ B1

II. Preliminary: property of the matrix F

Since B̄−1 B̄ = I, combining equations (14) and (16) we havethe following equations:Lemma 6: Suppose that F is symmetric non-negative,
strictly diagonally dominant, all of its diagonal elements areequal to 1. Then∑
(1) when i ∈ N1 , j ∈ B1 : −fij − k∈B∑1 w̄ik fkj = 0(2) when i ∈ B1 , j ∈ B1 and i = j : − ∑k∈B1 w̄ik fkj = 1 .
(3) when i ∈ B1 , j ∈ B1 and i ̸= j : − k∈B1 w̄ik fkj = 0•

0 ≤ F−1 1 ≤ 1.

•

Denote smax and smin as the maximum and minimum1min −1row’s sums of matrix F. Given that ssmax−1 > β > 0,then if θ ≥ β∥n∥∞ , we have0 ≤ F−1 (θ1 − n) ≤ θ1 − n.

Proof: See Appendix B.

(17)
Let D̄ = B̄−1 N̄. For the special structure of ēB and ēN ,inequality (13) can be equivalent to:{ T
1B1 D(B1 ,B1 ) ≤ 0TB1.
(18)
1TB1 D(B1 ,N1 ) ≤ 1TN1


D(B1 ,B1 ) = (B̄−1 )(B1 ,B1 ) ,D(B1 ,N1 ) = −(B̄−1 )(B1 ,B1 ) F(B1 ,N1 ) .

III. Proof of the equivalence between equations (4)and (8)Proof: Step 1. To prove x∗ is optimal for equation (10).
It is sufficient to prove B−1 d ≥ 0 and (B−1 N)T eB −eN ≥ 0 from Lemma 1, and we will prove (B−1 N)T eB −eN ≥ 0 first. It is easy to show that there always exist
permutation matrices P1 and P2 to make B̄ = BP1 and N̄ =NP2 , where B̄ and N̄ all have unit-absolute value diagonal
elements. Meanwhile, let ēB = PT1 eB and ēN = PT2 eN .
Then (B−1 N)T eB − eN ≥ 0 can be shown equivalent to(13)

Let b̄ij and n̄ij denote the element of matrices B̄ and N̄ in the
ith row and jth column. Then we have1b̄ij = 0

−fij

1
n̄ij = 0−fij

if j ∈ N1 and i = j
if j ∈ N1 and i ̸= j ,if j ∈ B1
if j ∈ B1 and i = j
if j ∈ B1 and i ̸= j .
if j ∈ N1(19)

From equation (17), we have:

Suppose that c0 is the true event vector. Define Z ={i ∈ I1 : c0i = 0}, Z̄ = {i ∈ I1 : c0i > 0}, Z + L = {j :j = i + L, ∀ i ∈ Z} and Z̄ + L = {j : j = i + L, ∀ i ∈ Z̄}.
The train of thought to prove Proposition 2 is as follows:Let
N = Z ∪ (Z̄ + L)
andB = Z̄ ∪ (Z + L).
Meanwhile, define B = AB and N = AN . Suppose x∗ ∈R2L , let x∗B = B−1 d and x∗N = 0. We first prove x∗ is
optimal for (10) and hence x∗I1 is optimal for (8). Next, we
will prove FB1 x∗B1 ≤ b + θ1, which leads to Proposition 2.

(B̄−1 N̄)T ēB − ēN ≥ 0.

From equations (14) and (16), we have:

(14)

(15)

(B̄−1 )(B1 ,B1 ) F(B1 ,B1 ) = −I.

(20)

Combining equations (19) and (20), inequality (18) is
equivalent to:{T
1TB1 F−1(B1 ,B1 ) ≥ 0B1
.
(21)
−1
T
1B1 F(B1 ,B1 ) F(B1 ,N1 ) ≤ 1TN1
Since F(B1 ,B1 ) is with the same characteristics with F, andthe column sums of F(B1 ,N1 ) are less than 1. From Lemma 3
we can achieve (21), and hence (B−1 N)T eB − eN ≥ 0 isestablished.
Next we will prove B−1 d ≥ 0, which is equivalent to−1
B̄ d ≥ 0. Recall that d = −b + θ1 = −Fc0 − n + θ1,
and hence B̄−1 d ≥ 0 is equivalent to B̄−1 Fc0 ≤ B̄−1 (θ1 −n).
Let L = B̄−1 F and lij denotes the element of matrices L.
From equations (16) and (17), it is easy to verify: −1 if j ∈ B1 and i = j
if j ∈ B1 and i ̸= j .
lij = 0(22)
lij if j ∈ N1
Recall that the special structure of c0 , we have Ec0 = −c0 andB̄−1 Fc0 ≤ B̄−1 (θ1 − n) is equivalent to B̄−1 (θ1 − n) ≥−c0 , which, considering (16), is also equivalent to:(B̄−1 )(B1 ,B1 ) (θ1 − n)B1 ≥ −(c0 )B1(23)(B̄−1 )(N1 ,:) (θ1 − n) ≥ 0.

(24)

To prove (23), recall that (B̄−1 )(B1 ,B1 ) = −F−1
(B1 ,B1 ) , andfrom Lemma 3 it is sufficient to prove (θ1 − n)B1 ≤ (c0 )B1

A decentralised linear programming approach to energy-efficient event detection
when θ ≥ β∥n∥∞ . The inequality clearly holds because(c0 )B1 ≥ (β + 1) ∥n∥∞ .
Inequality (24) is equivalent to (B̄−1 )(N1 ,B1 ) (θ1 −n)B1 ≥ −(θ1 − n)N1 . Combining equations (17); thisinequality is also equivalent to F(N1 ,B1 ) F−1(B1 ,B1 ) (θ1 −n)B1 ≤ (θ1 − n)N1 , which will hold if F(N1 ,B1 )(θ1 − n)B1 ≤ (θ1 − n)N1 holds when θ ≥ β∥n∥∞ from
Lemma 3. Since ∥F(N1 ,B1 ) ∥∞ ≤ 21 , which can be easily
verified, we have F(N1 ,B1 ) (θ1 − n)B1 ≤ (θ1 − n)N1 isestablished, so is (24). Finally, B−1 d ≥ 0 can be reached.
Step 2. To prove FB1 x∗B1 ≤ b + θ1.
Recall that b = Fc0 + n and d = −Fc0 − n + θ1, anddefine G = FB1 (B−1 )(B1 ,:) , then FB1 x∗B1 ≤ b + θ1 isequivalent to (G + I)Fc0 ≥ G(θ1 − n) − (θ1 − n).
Define H = G + I, from equations (16) and (17), we have:0
if j ∈ N1


−1
if j ∈ B1 , i ∈ B1 and i = jgij =, (25)0ifj ∈ B1 , i ∈ B1 and i ̸= j
∑
if j ∈ B1 , i ∈ N1
k∈B1 fik w̄kj

1



0
hij =
0


∑

k∈B1 fik w̄kj

if j ∈ N1 , and i = j
if j ∈ N1 , and i ̸= j.
if j ∈ B1 , i ∈ B1
if j ∈ B1 , i ∈ N1

(26)

Define R = HF, combining equations (17) and (25), we have:{0
if j ∈ B1
rij =
.
(27)
rij if j ∈ N1
Recall that the special structure of c0 , we have Rc0 = 0.
Therefore, all we need to prove is G(θ1 − n) − (θ1 − n) ≤0. Note that:G(θ1 − n) = FB1 (B̄−1 )(B1 ,B1 ) (θ1 − n)B1
= −FB1 F−1(B1 ,B1 ) (θ1 − n)B1
≤ 0.

61

Similar to (21), to prove (B−1 N)T eB − eN ≥ 0 is
equivalent to prove{T
1T FB1 F−1(B1 ,B1 ) ≥ 0B1
.
(29)
−1
T
1 FB1 F(B1 ,B1 ) F(B1 ,N1 ) ≤ 1T FN1
For the first inequality in equation (29), note that
1T FB1 F−1(B1 ,B1 )= 1T [FT(B1 ,B1 ) FT(N1 ,B1 ) ]T F−1(B1 ,B1 )= 1T [I FT(N1 ,B1 ) ]T F−1(B1 ,B1 ) .

(30)

It is easy to show F(N1 ,B1 ) F−1(B1 ,B1 ) ≥ 0. Supposeto the contrary that F(N1 ,B1 ) F−1
after(B1 ,B1 ) < 0,multiplying F(B1 ,B1 ) to the right side we achieve
F(N1 ,B1 ) F−1(B1 ,B1 ) F(B1 ,B1 ) < 0 F(B1 ,B1 ) , i.e. F(N1 ,B1 ) < 0,which is impossible. Now we can conclude (30) is positive.
For the second inequality in equation (29), it is established
if we can prove:{T
1TB1 F(B1 ,B1 ) F−1(B1 ,B1 ) F(B1 ,N1 ) ≤ 1B1 F(B1 ,N1 ). (31)−1T
1N1 F(N1 ,B1 ) F(B1 ,B1 ) F(B1 ,N1 ) ≤ 1TN1 F(N1 ,N1 )The first inequality in equation (31) holds clearly.
For the second inequality, since F−1(B1 ,B1 ) F(B1 ,N1 ) ≥ 0,−1
T
T
T
1N1 F(N1 ,B1 ) ≤ 1B1 and 1B1 F(B1 ,B1 ) ≤ 1TB1 , we have
−1T
1TN1 F(N1 ,B1 ) F−1(B1 ,B1 ) F(B1 ,N1 ) ≤ 1B1 F(B1 ,B1 ) F(B1 ,N1 ) ≤1TB1 F(B1 ,N1 ) < 1TN1 F(N1 ,N1 ) , and hence equation (31) holds
and so does (29). Therefore (B−1 N)T eB − eN ≥ 0 isestablished and x∗ is also optimal for problem (8).
Appendix B(28)

First we show two obvious but useful lemmas, both of which
are easy to verify.

Since θ ≥ β ∥n∥∞ , we have G(θ1 − n) ≤ 0 ≤ θ1 − n, andhence FB1 x∗B1 ≤ b + θ1.
Lemma 7: If A ∈ Rn×n is nonsingular with all its row’ssums equal to s, then the row’s sums of A−1 all equal to 1s .

IV. Proof of the equivalent between equation (5)and (8)Proof: Proving the equivalence between equations (5) and (8)is actually a problem concerning sensitivity analysis in linear
programming, where coefficients in the objective function
are perturbed. Under the assumptions in Proposition 2, weknow, from Appendix A.III, that the basic variables set B =Z̄ ∪ (Z + L) and nonbasic variables set N = Z ∪ (Z̄ + L)
are optimal for problem (5). Suppose that x∗ is the optimal
solution of problem (5), then we have x∗B = B−1 d and x∗N =0. Now we prove x∗ is also optimal to problem (8).
Problem (8) can also be transformed into equations (10)–(12), with e = [−1T F, 0T ]T . Since x∗B = B−1 d ≥ 0 andx∗N = 0, it is obvious that x∗ is feasible for problem (8). If we
can further prove that (B−1 N)T eB − eN ≥ 0, the conclusionthat x∗ is also optimal to problem (8) is established.

Lemma 8: Suppose A0 , △A, B0 , △B ∈ Rn×n , and both
A0 and A0 + △A are nonsingular, besides, suppose A−1
0 =B0 , then we have (A0 + △A)−1 = B0 + △B, where △B =−B0 △AB0 − B0 △A△B.
The following lemma is important to later theoretical analysis.
Lemma 9: Suppose F is nonsingular. Split F into F = F0 +△F, where F0 is nonsingular with all row’s sums equal.
If ∥△F∥∞ ≤ α∥F0 ∥∞ , where α ∈ [0, 12 ), then when θ ≥1−1(θ1 − n) ≥ 0.
1−2α ∥n∥∞ , we have F
Proof: Suppose G0 , △G ∈ RL×L , and G0 = F−1
0 , (G0 +△G) = (F0 + △F)−1 . By Lemma 5, we have △G =−G0 △FG0 − G0 △F△G. It is easy to achieve(1 − ∥G0 ∥∞ ∥△F∥∞ )∥△G∥∞ ≤ ∥G0 ∥∞ ∥△F∥∞ ∥G0 ∥∞ .

62

K. Yuan et al.

Note that ∥F0 ∥∞ ∥G0 ∥∞ = 1 and 1 − ∥G0 ∥∞ ∥△F∥∞ >α0, and hence we can achieve ∥△G∥∞ ≤ 1−α∥G0 ∥∞ <1∥G0 ∥∞ for α ∈ [0, 2 ).
On the other hand, note that F−1 (θ1 − n) = (G0 +△G)(θ1 − n), and to prove F−1 (θ1 − n) ≥ 0 it issufficient to prove (∥G0 ∥∞ + ∥△G∥∞ )∥n∥∞ ≤ (∥G0 ∥∞ −∥△G∥∞ ) θ, which is equivalent toθ ≥ (1 + ∥F0 ∥∞ ∥△G∥∞ )∥n∥∞ /(1 − ∥F0 ∥∞ ∥△G∥∞ ).
It is easy to show (1 + ∥F0 ∥∞ ∥△G∥∞ )∥n∥∞ /(1 −∥F0 ∥∞ ∥△G∥∞ ) ≤ ∥n∥∞ /(1 − 2α), and (32) holds for θ ≥1(1−2α) ∥n∥∞ .
Now we prove Lemma 6.
Proof: Split F into F = F0 + △F, where in F0 all row
sums equal smax and all diagonal elements equal one,and △F is nonnegative with zero diagonal elements.
It is noted that such split will always exists. Let
smax = 1 + x and smin = 1 + y, we have 1 > x > y ≥0. Note that ∥△F∥∞ = (1 + x) − (1 + y) = x − y, thus
we have 12 ∥F0 ∥∞ − ∥△F∥∞ = 21 smax − (x − y) = 21 (1 −x) + y > 0, i.e., ∥△F∥∞ < 12 ∥F0 ∥∞ . That is to say, theperturbation matrix △F satisfies the assumptions of Lemma 6.
Let n = 0, we have F−1 1 ≥ 0. Because if Fx = 1 and x ≥ 0,then x ≤ 1, and hence F−1 1 ≤ 1.
Second, since xy > β1 , α = ∥△F∥∞ /∥F0 ∥∞ = (x −x< 12 (1 − β1 ). From Lemma 6y)/(1 + x) < (1 − β1 ) 1+x
WE know if θ ≥ β∥n∥∞ , we have F−1 (θ1 − n) ≥ 0. And
F−1 (θ1 − n) ≤ 1 is easy to verify.
