1

Sensor placement by maximal projection on
minimum eigenspace for linear inverse problems

arXiv:1506.00747v3 [cs.DS] 5 Nov 2016

Chaoyang Jiang, Yeng Chai Soh, and Hua Li

Abstract—This paper presents two new greedy sensor placement algorithms, named minimum nonzero eigenvalue pursuit (MNEP) and maximal projection on minimum eigenspace
(MPME), for linear inverse problems, with greater emphasis on
the MPME algorithm for performance comparison with existing
approaches. In both MNEP and MPME, we select the sensing
locations one-by-one. In this way, the least number of required
sensor nodes can be determined by checking whether the estimation accuracy is satisfied after each sensing location is determined.
For the MPME algorithm, the minimum eigenspace is defined
as the eigenspace associated with the minimum eigenvalue of
the dual observation matrix. For each sensing location, the
projection of its observation vector onto the minimum eigenspace
is shown to be monotonically decreasing w.r.t. the worst case
error variance (WCEV) of the estimated parameters. We select
the sensing location whose observation vector has the maximum
projection onto the minimum eigenspace of the current dual
observation matrix. The proposed MPME is shown to be one
of the most computationally efficient algorithms. Our MonteCarlo simulations showed that MPME outperforms the convex
relaxation method [1], the SparSenSe method [2], and the
FrameSense method [3] in terms of WCEV and the mean square
error (MSE) of the estimated parameters, especially when the
number of available sensor nodes is very limited.
Index Terms—Linear inverse problem, sensor placement,
greedy algorithm, rank-one modification, local optimization.

I. I NTRODUCTION
ENSOR networks are widely used for monitoring
temporal-spatial physical fields. While each sensor node
can only observe the field intensity (e.g., temperature, humidity, concentration of contaminant, etc.) of a particular
location, with a network of sparse sensor observations, a
physical field of interest may be reconstructed by solving a
linear inverse problem [3]–[8]. In physical field estimation, the
number of sensor nodes and their spatial locations are closely
related to the coverage, cost, battery energy consumption, and
even the error of the estimated physical field. Therefore, the
determination of the least number of required sensor nodes
and their locations is critical in sensor network design.

S

Copyright (c) 2015 IEEE. Personal use of this material is permitted.
However, permission to use this material for any other purposes must be
obtained from the IEEE by sending a request to pubs-permissions@ieee.org.
The work was supported by Singapore’s National Research Foundation
under Grant NRF2011NRF-CRP001-090 Award Number NRF-CRP8-201103, and partially supported by the Energy Research Institute at NTU(ERI@N).
C. Jiang and Y. C. Soh are with the School of Electrical and Electronic
Engineering, Nanyang Technological University, Singapore 639798 (e-mail:
chaoyangjiang@hotmail.com; eycsoh@ntu.edu.sg).
H. Li is with the School of Mechanical and Aerospace Engineering, Nanyang Technological University, Singapore 639798 (e-mail: lihua@ntu.edu.sg.).

For a linear inverse problem, sensor placement is to seek the
least number of required sensor nodes and their corresponding
sensing locations within a known spatial domain such that the
estimation accuracy can meet the requirement. Specifically,
assuming that the observation models of all potential sensing
locations are known, we want to determine the least number
of required sensors with which the physical field of interest
can be recovered within a predefined accuracy. Obviously, one
straightforward method is to evaluate the performance of all
possible combinations of all potential sizes of the candidate
sensing locations, and then select the one with the least number
of sensor nodes that satisfies the required estimation accuracy. But such a combinatorial approach is computationally
intractable. In practice, direct enumeration is impossible if the
number of potential sensing locations is large. Apart from the
enumeration method, the optimal solution can also be obtained
by branch-and-bound methods [9], [10], which unfortunately
do take a very long time, even for a moderate scale problem
[1]. Consequently, in recent years the sensor placement for
the linear inverse problem has attracted increasing attention to
find a suboptimal solution via computationally more efficient
methods [1]–[8], [11]–[15].
A. Related prior work
Heuristics have been proposed to reduce the cost of exhaustive search. The simplest one is to place sensor nodes at the
spatial maxima and minima of proper orthogonal components
of the physical field of interest [5]. This method is simple
but only suitable for some special cases [6]. Other heuristics
include genetic algorithms [13], particle swarm optimizer [14],
tabu search [14], and cross-entropy optimization [15]. They all
involve a prohibitive computational cost and the solutions have
no optimality guarantee.
Joshi and Boyd [1] formulated the sensor placement problem as an elegant nonconvex optimization problem, and approximated it as a convex optimization problem by the relaxation of the nonconvex Boolean constraints that represent the
sensor placements, to a convex box set. This convex relaxation
was then used in many works [2], [11], [16]–[19]. The sensing
locations can be easily determined based on the solution of the
convex optimization problem. But the sensor placement may
lead to an ill-conditioned observation model due to the gap
between the nonconvex and the convex optimization problems,
especially when the number of sensor nodes is very limited.
Such a result has been shown to be no better than other works
[3], [18], [19]. However, the authors in [1] provided a local
optimization technique to improve the result. This technique

2

is computationally expensive but some numerical examples
showed that with the local optimization, the convex relaxation
method can indeed provide good results.
The sensor placement problem was also solved by some
greedy algorithms in which the sensor locations are individually determined by optimizing some proxies of the error of the
estimated physical field, such as the determinant of Fisher information matrix [12], and the condition number [6]–[8] or the
frame potential [3] of the observation matrix. The η-confidence
ellipsoid of the estimation error depends on the determinant of
the Fisher information matrix [1], which was optimized using
one greedy method in [12], but it is shown to be no better
than other methods in the examples in [3]. For the sensor
placement problem, the minimum requirement of the solution
is that the observation model should be well-conditioned.
Therefore, some researchers determined the sensing locations
by minimizing the condition number of the observation matrix
[6]–[8]. However, the condition number is a concept for
nonsingular matrix, and we need to firstly determine a group
of sensing locations to guarantee that the observation matrix
is nonsingular [7], which is unfortunately a combinatorial
problem. Additionally, the minimum condition number of the
observation matrix does not mean the minimum estimation
error except when all the observation vectors have the same
norm because the sensing energy should be considered, which
is related to the signal-to-noise ratio. Recently, Ranieri et al.
[3] provided a novel greedy algorithm by minimizing the
frame potential of the observation matrix. This method is
computationally efficient but: 1) like the condition number
minimization, it is only effective for the case where all the
observation vectors have the same norm; 2) it cannot guarantee
that the observation matrix is well-conditioned.
All the above mentioned works focused on the case where
the number of sensor nodes is fixed. One sparse-promoting
technique has been used to minimize the number of required
sensor nodes by adding a sparsity-promoting penalty term
to the cost function [2]. This method works well when the
dimension of the estimated parameter is small (e.g., the
dimension is set as 2 in the example of Ref. [2]). However,
if the dimension of the estimated parameter is large (e.g., a
few tens, which is very common in fluid field reconstruction
problems [6], [7], [20]), this method will be ineffective in
determining the least number of required sensor nodes, which
will be discussed in detail later.
Besides the sensor placement for linear inverse problems,
many other excellent sensor placement works have focused
on the continuous system [11], nonlinear model [16], energy
saving [4], [18], state estimation for dynamic system [18],
[19], [21]–[23], and Gaussian process interpolation [24]–[27].
B. Our contributions
In this paper, we propose a new greedy algorithm to
minimize the number of required sensor nodes and determine
their locations for the linear inverse problem such that the
estimation error meets the requirement. We determine the
sensing locations one-by-one until the estimation accuracy is
satisfied by maximizing the projection of each observation

vector onto the eigenspace of the minimum eigenvalue of
the current dual observation matrix. It is shown that such a
projection is monotonically decreasing w.r.t. the worst case
error variance (WCEV).
Compared with the state-of-the-art, the proposed greedy
algorithm which we call the maximal projection on minimum
eigenspace (MPME), has the following advantages:
• The MPME can readily determine the minimum number
of required sensor nodes.
• The MPME outperforms the convex relaxation method
[1], the SparSenSe method [2], and the FrameSense
method [3] in terms of the WCEV and the mean square
error (MSE) of the estimated vector, especially when the
number of available sensor nodes is very limited.
• The MPME can guarantee that the observation matrix is well-conditioned but the convex relaxation, the
SparSenSe and the FrameSense methods cannot guarantee such a condition, especially when the number of
available sensor nodes is very limited.
• For general sensor placement problems, the MPME without local optimization [1] outperforms the state-of-the-art
with local optimization.
• The proposed MPME is computationally one of the most
efficient sensor placement algorithms.
C. Outline and notations
The rest of this paper is organized as follows. In Section
II, we introduce the linear inverse problem and the sensor
placement problem, and briefly review three current methods.
In Section III, we develop the MPME algorithm. We then
provide four examples to compare the effectiveness of MPME
with the current methods via Monte-Carlo simulations in
Section IV. In Section V, we analyze the computational cost of
the MPME algorithm and compare it with those of the current
methods. The conclusions are given in Section VI.
This paper uses the following notations: Upper (lower)
bold letters, e.g. A (a) or Φ (ϕ), indicate matrices (column
vectors). I represents an identify matrix with proper dimension
whose i-th column vector is denoted by ei . 1 is a vector of
proper dimension with all entries one. (·)T , (·)† , E(·), tr(·),
k · k, det(·), span(·), null(·), dim(·), and rank(·) are respectively the transposition, pseudo-inverse, expectation, trace,
norm, determinant, spanned space, null space, dimension, and
rank operators.
II. P ROBLEM S TATEMENT
A. Linear inverse problem
We consider a physical field f ∈ RN described as
f = Φ̃α

(1)

where α ∈ Rn is a vector of parameters to be estimated with
n  N , and Φ̃ ∈ RN ×n is a known full column-rank matrix,
which we call the signal representation matrix and its column
vectors compose a basis of the physical field.
It is expensive and impractical to sense the physical field f
with N sensor nodes since N is very large and depends on the

3

resolution of the discrete physical space [3]. However, part of
the physical field can be observed from sensor networks, i.e.

B. Sensor placement problem

is a pruned matrix from the rows of Φ̃ indexed by
{s1 , s2 , ..., sM }, and ϕT
si is the si -th row of Φ̃ and represents
the observation model of the i-th sensor node, which we call
the observation vector. The measurement noise ν ∈ RM is
assumed to be zero-mean i.i.d. Gaussian random process with
variance σ 2 I.
From (2), we can obtain the following minimum variance
unbiased estimate (MVUE)

We denote the set of selected sensing locations by S =
{s1 , s2 , ..., sM }, and the set of potential sensing locations by
N = {1, 2, ..., N }, which correspond to the row indices of Φ
and Φ̃, respectively. Then, we formulate the following sensor
placement problem.
Problem 1: Given the signal representation matrix Φ̃ =
[ϕ1 , ϕ2 , ..., ϕN ]T ∈ RN ×n , select M rows of Φ̃ indexed
by s1 , s2 , ..., sM to construct the observation matrix Φ =
[ϕs1 , ϕs2 , ..., ϕsM ]T ∈ RM ×n , such that the error of the
estimated parameters α̂ in (3) is small enough and the number
of rows of Φ, i.e. M , is minimized.
This actually is a sensing location selection problem. We
aim to find the minimum number of sensing locations with
which the error of α̂ is less than a predefined threshold. In this
paper, we use the WCEV as the error indicator, and equation
(6) shows that a small WCEV can guarantee a small MSE.
Then, this sensor placement problem can be formulated as the
following cardinality minimization problem

α̂ = Φ† y

Ŝ = arg min |S| subject to λn ≥ γ

y = Hf + ν = Φα + ν

(2)

where H ∈ RM ×N whose i-th row is eT
si , si ∈ N =
{1, 2, ..., N } corresponds to the i-th sensing location, and
M (n ≤ M  N ) is the number of sensor nodes. The
observation matrix
Φ = HΦ̃ = [ϕs1 , ϕs2 , ...ϕsM ]T

(3)

(7)

S⊆N

where Φ† = (ΦT Φ)−1 ΦT is the pseudo-inverse of Φ. The
mean square error (MSE) of this MVUE [1]–[3] is
n
X

1
(4)
MSE(α̂) = E kα̂ − αk22 = σ 2 tr(Ψ−1 ) = σ 2
λk
k=1

where λ1 ≥ λ2 ≥ ... ≥ λn stand for the eigenvalues of
Ψ = ΦT Φ
which we call the dual observation matrix.
With some standard operations, we can obtain the variance
of α̂ as


Σ = E (α̂ − α)(α̂ − α)T


= E Φ† νν T (Φ† )T
=

σ 2 Φ† (Φ† )T = σ 2 Ψ−1

kxk2 =1

σ2
λn

(5)

For more detail about WCEV, do refer to [1]. Since Φ† (Φ† )T
= Ψ−1 , it is easily found from (4) and (5) that
MSE(α̂)

= σ 2 kΦ† k2F

WCEV(α̂)

= σ 2 kΦ† k22

The combinatorial optimization problem (7) is NP-hard
[29]. Here, we briefly review three current and related methods. Two of them are originally designed for the case where
the number of available sensors is fixed. However, they can
be simply modified and applied to the case where the number
of sensors is unknown, which is discussed in Remark 1.
1) Convex relaxation [1]: If the number of sensor nodes is
fixed, the sensor placement problem can be formulated as
!
N
X
T
maximize
log det
wi ϕi ϕi
subject to

1T w = M
wi ∈ {0, 1},

i∈N

(8)

with variable w ∈ RN . Here wi = 1 means i ∈ S and wi = 0
means i ∈
/ S. Performing a convex relaxation, i.e. replacing
the nonconvex Boolean constraints wi ∈ {0, 1} by wi ∈ [0, 1],
we can obtain the following convex optimization problem:
!
N
X
T
maximize
log det
wi ϕi ϕi
i=1

subject to

Consequently, the two error indicators are equivalent due to
the equivalence of the two matrix norms [28]. Specifically,
WCEV(α̂) ≤ MSE(α̂) ≤ nWCEV(α̂)

C. The state of the art

i=1

Then, we introduce the following worst case error variance
(WCEV) of the MVUE α̂
WCEV(α̂) = max xT Σx = λmax (Σ) =

where | · | returns the cardinality of a set, and γ corresponds
to the maximum acceptable WCEV.

(6)

It is clear in (4) and (5) that both MSE and WCEV depend
on the eigenvalues of the dual observation matrix Ψ, which
fully depends on the sensing locations.

1T w = M
wi ∈ [0, 1],

i∈N

(9)

with variable w. This problem can be solved by the interiorpoint methods [30]. Rearranging the entries of the solution
of the relaxed problem (9), i.e. w∗ (∈ [0, 1]N ), in descending
order yields the sequence {wŝ∗1 , wŝ∗2 , . . . , wŝ∗N }. Then, the set
of the sensing indices is given by Ŝ = {ŝ1 , ŝ2 , . . . , ŝM }, i.e.
the indices of the M largest elements of w∗ .

4

2) SparSenSe [2]: To determine the number of required
sensor nodes, the following convex optimization, called sparseaware sensor selection (SparSenSe), is formulated:
minimize
subject to

kwkl1
 PN


wi ϕi ϕT
ej
i
 0, j = 1, ..., n
eT
xj
j
kxkl1 ≤ γ 0 , xj ≥ 0, j = 1, ..., n
i=1

wi ∈ [0, 1],

i∈N

(10)

where γ 0 corresponds to the maximum acceptable MSE index.
This is a linear matrix inequalities problem and can be solved
by using the CVX toolbox [31]. With the solution w∗ and a
prior threshold τ (0 / τ  1), we can determine the sensing
indices. If wi∗ < τ , set wi∗ = 0. The number of required sensor
nodes is the number of nonzero entries of w∗ .
3) FrameSense [3]: The ensemble of the rows of a matrix
can be viewed as a frame. If all the observation vectors have
the same norm, according to the frame theory, the observation
matrix Φ achieves the minimum MSE when it achieves the
minimum frame potential [3], [32]. For the basic concept of the
frame theory, do refer to [33]. The sensor placement problem
can be solved by minimizing the following frame potential
FP(Φ) =

X

2
(ϕT
i ϕj )

number
PM −1 of searched sensor configurations can be reduced to
i=0 (N − i), since at the first step over N possible sensing
locations are searched, then N − 1, and so on.
Admittedly, each sensor node may have correlated influence
with others, and one sensor reading is informative for a given
sensor configuration but may be meaningless for others. When
finding the sensing locations one-by-one, we do not know
the contribution of each sensor node for the final sensor
configuration; therefore, such a strategy cannot guarantee the
optimal solution. However, we are trying to make a tradeoff
between the computational cost and the number of required
sensor nodes, i.e. to find an effective sensor configuration with
proper number of sensor nodes by determining the sensing
locations one-by-one.
When determining the sensing locations one-by-one, we can
obtain an observation vector sequence {ϕsk }M
k=1 . For simplicity, we introduce a new matrix Φk ∈ Rk×n to denote the first
k(1 ≤ k ≤ M ) rows of Φ, i.e. Φk = [ϕs1 , ϕs2 , ...ϕsk ]T
corresponds to the first k sensing locations. Corresponding to
M
{ϕsk }M
k=1 , we can obtain the matrix sequence {Φk }k=1 and
M
the dual observation matrix sequence {Ψk }k=1 . Here Ψk =
(k) n
ΦT
k Φk has a nonincreasing eigenvalue sequence {λi }i=1 .
The notations that will commonly appear in this paper are
listed below for easy reference.

(11)

i,j∈S

One greedy “worst-out” algorithm, called the FrameSense,
can provide a near-optimal solution in the sense of the minimum frame potential. At each step, it removes the row of Φ̃
that maximally increases the frame potential. If Φ̃ corresponds
to an equal-norm frame, the row index is in fact the index of
the row/column of (Φ̃Φ̃T )2 which has the largest 1-norm.
Here, A2 denotes a matrix whose entries are the square of the
corresponding entries of A.
Remark 1: With simple modifications, convex relaxation
and FrameSense can be used to determine the least number
of required sensors. For the convex relaxation method, it can
be found by increasing the sensor number from n until the
constraint in (7) is satisfied. For FrameSense, when removing
each row of Φ̃, we check the constraint in (7). If the constraint
is not satisfied, reserve the row and the number of remaining
rows of Φ̃ is the least number of required sensors.
III. M AXIMAL P ROJECTION ON M INIMUM E IGENSPACE
As mentioned before, one apparent method to solve the
cardinality optimization problem (7) is to evaluate the minimum eigenvalue of the dual observation matrix (i.e. λn ) of
all potential sensor configurations, and then find the configuration with the minimum number of sensors that satisfies the
constraint. Unfortunately, the computational cost of exhaustively searching 2N potential configurations is unaffordable
for large scale problems. One simple strategy to reduce the
number of searched sensor configurations is to determine
the sensing locations one-by-one. With such a strategy, the
minimum number of required sensor nodes, M , can be easily
found by judging whether the constraint in (7) is satisfied
after each sensing location is determined. In this way, the

ϕsk
Φk
Ψk
(k)
λi
(k)
ui
µn
λn

the k-th selected observation vector corresponding to the k-th
sensing location. ϕT
sk is the k-th row of Φ and sk -th row of Φ̃.
includes the first k observation vectors. It consists of the first k
rows of the observation matrix Φ = ΦM .
= ΦT
k Φk , is the dual observation matrix associated with Φk .
the i-th eigenvalue of Ψk , i.e. λi (Ψk ).
(k)
the normalized eigenvector of Ψk associated with λi .
(k−1)
the multiplicity of the minimum eigenvalue λn
w.r.t. Ψk−1 .
(M )
the minimum eigenvalue of Ψ = ΨM , i.e. λn .

(k)

For all k < n, the minimum eigenvalue of Ψk , λn = 0
because rank(Ψk ) = rank(Φk ) ≤ k. Therefore, the number
of required sensor nodes M must be no less than n. Since Φ̃
is a full column-rank matrix, the nonsingular Ψn exists, which
implies that the optimal M may be equal to n. Consequently,
to minimize M we should guarantee that Ψn is nonsingular. In
that case, the vectors in {ϕsk }nk=1 are mutually independent
and rank(Ψk ) = rank(Φk ) = rank({ϕsi }ki=1 ) = k for
all k ≤ n. In practice, we can easily guarantee that ϕsk is
independent with the vectors in {ϕsi }k−1
i=1 when determining
the k-th sensing location for all k ≤ n.
Our purpose is to find the shortest observation vector
sequence {ϕsk }M
k=1 by determining the sensing locations oneby-one, such that the constraint in (7), i.e. λn ≥ γ, is
satisfied. For a given sensor configuration corresponding to
Φk−1 (1 ≤ k < M ), we need to formulate some guidelines
to determine the next sensing location sk . Intuitively, we can
traverse all N −k+1 unselected observation vectors to find the
one that can maximally increase λn . Then, the other sensing
locations can be similarly determined one-by-one until λn > γ
and meanwhile the number of selected sensing locations is the
minimum number of required sensor nodes, i.e. M .
However, the challenge is that we do not know how ϕsk

5

(M )

affects λn (= λn ) since M and {ϕsi }M
i=k+1 are unknown
when we find the k-th sensing location. In other words,
we cannot build an explicit mapping between ϕsk and λn .
Therefore, it is impossible to find the optimal k-th sensing
location s∗k by directly optimizing λn .
Our main idea is to find a new criterion instead of λn .
When determining the k-th sensing location, we optimize the
new criterion. The criterion should satisfy three conditions:
1) It can be directly obtained from Φk−1 and ϕsk .
2) Optimizing the criterion can guarantee that all the vectors in {ϕsk }nk=1 are mutually independent.
3) λn is positively correlated with the criterion.
The first condition implies that we can directly assess the
contributions of all potential observation vectors for the new
criterion. The second condition guarantees that Ψn is nonsingular, and the last condition guarantees that increasing the new
criterion can increase λn , i.e. decrease the WCEV. If such a
criterion exists, we can determine the sensing locations oneby-one by maximizing the new criterion. Accordingly, we can
find a suboptimal sensor configuration. In what follows, we
shall present two alternative criteria.

(k+1)

It can be easily found that
T
T
T
T
Ψk = ΦT
k Φk = [Φk−1 ϕsk ][Φk−1 ϕsk ] = Ψk−1 +ϕsk ϕsk

This equation implies that all the eigenvalues of Ψk satisfy
the first condition of the criterion used to replace λn , i.e. the
eigenvalues of Ψk can be found if Φk−1 and ϕsk are known.
Amongst all the eigenvalues of Ψk , we guess that the minimum
(k)
(k)
nonzero eigenvalue, i.e. λk when k ≤ n and λn when k >
n, is one choice of the criterion to be used to replace λn .
(k)
Obviously, for any k ≤ n, maximizing λk can guarantee
(k)
that λk > 0, which implies that for any k ≤ n, the vectors in
{ϕsi }ki=1 are mutually independent. Therefore, the minimum
nonzero eigenvalue of Ψk satisfies the second condition. We
then utilize the following theorem to show that it also satisfies
the third condition.
Theorem 1: Suppose B = A + ccT where A ∈ Rn×n is
symmetric, and c ∈ Rn is a non-zero vector. Then,
λ1 (B) ≥ λ1 (A) ≥ λ2 (B) ≥ λ2 (A) ≥ ... ≥ λn (B) ≥ λn (A)
Proof: See [34] and the Theorem 8.1.8 in [28].
Since Ψk = Ψk−1 + ϕsk ϕT
sk , considering Theorem 1, we
can obtain
for all

k≥n

(k)
λk

for all

k≤n

≤

(k−1)
λk−1

From the two equations, we can easily find that
)
−1)
λ(M
≥ λ(M
≥ ... ≥ λ(n)
n
n
n

λ(n)
n

≤

(n−1)
λn−1

≤ ... ≤

(1)
λ1
(k)

(M )

Algorithm 1: minimum nonzero eigenvalue pursuit

A. Minimum nonzero eigenvalue pursuit (MNEP)

(k−1)
λ(k)
n ≥ λn

(k)

λn
is positively correlated with λn . Since λn = λn ≥
(M −1)
(k+1)
(k)
λn
≥ ... ≥ λn
≥ λn , λn is positively correlated
(k)
with λn for any n ≤ k < M .
(k)
For any k < n, (13) shows that λk is the upper bound of
(k+1)
λk+1 . Therefore, if we select sensing location to maximize
(k)
(n)
(k+1)
λk , we maximize the upper bound of λn . Actually, λk+1
(k)
is monotonically increasing w.r.t. λk for any k < n, which
(n)
will be shown later. Hence, λn is monotonically increasing
(k)
(M )
w.r.t. λk for all k < n. Since λn = λn
is positively
(n)
correlated with λn , we conclude that λn is also positively
(k)
correlated with λk for any k < n.
In summary, λn is positively correlated with the minimum
(k)
(k)
nonzero eigenvalue of Ψk , i.e. λk for k < n and λn for
k ≤ n, which satisfies the third condition.
Therefore, the minimum nonzero eigenvalue of Ψk can be
a criteria in place of λn to optimize the k-th sensing location.
(k)
To maximize λn , we can select ϕsk to maximize λk when
(k)
k < n and maximize λn when k ≥ n. The greedy algorithm
for the sensor placement problem named minimum nonzero
eigenvalue pursuit (MNEP) is summarized in Algorithm 1.

(12)
(13)

For any n ≤ k < M , (12) shows that λn is the lower
(k+1)
(k)
bound of λn
. If we maximize λn by proper selection
(k+1)
of ϕsk , we maximize the lower bound of λn
. Hence,

1
2

Input: Φ̃ = [ϕ1 , ϕ2 , ..., ϕN ]T ∈ RN ×n
Output: Φ ∈ RM ×n , S, M
Initialization: N = {1, 2, ..., N }, S = ∅.
Determine the first n − 1 sensing locations:
(a) Φ0 = [ ], k = 1.
T
(b) ŝk = arg max λk (ΦT
k−1 Φk−1 + ϕi ϕi ).
i∈N \S

3

T
(c) Update: S = S ∪ {ŝk }, Φk = [ΦT
k−1 ϕŝk ] .
(d) Set k = k + 1 and repeat step (b-c) until k = n.
Determine the remaining sensing locations:
T
(a) ŝk = arg max λn (ΦT
k−1 Φk−1 + ϕi ϕi ).
i∈N \S

T
(b) Update: S = S ∪ {ŝk }, Φk = [ΦT
k−1 ϕŝk ] .
(k)
(c) If λn ≥ γ return S, M = k, and Φ = Φk , else set
k = k + 1 and repeat step (a-b).

We determine the sensing locations one-by-one. For the
first n − 1 sensors, the k-th sensing location can be obtained
from the optimization problem in step 2(b). To solve this optimization problem, we traverse all the unselected observation
(k)
vectors and find the one that maximizes λk . After n − 1
sensing locations have been determined, we find the remaining
sensing locations by solving the optimization problem in step
(k)
3(a), which is similar to the previous one but maximizes λn ,
i.e. the minimum eigenvalue of Ψk . Meanwhile, we check the
constraint in (7) after each sensing location is determined. If
the constraint is satisfied, stop the algorithm.
When determining the k-th sensing location, we need to
traverse N − k + 1 rows of Φ̃, and evaluate the minimum
nonzero eigenvalue of Ψk for each case. Solving eigenvalue
problems for all N −k +1 cases is computationally expensive.
Can we find a simpler alternative criterion for the observation
vectors in {ϕi }N
i=1 to avoid solving eigenvalue problems for
all possible dual observation matrices?

6

In what follows, we provide another criterion, i.e. the magnitude of the projection of ϕsk onto the minimum eigenspace
of Ψk−1 , and it is shown to satisfy the three aforementioned
conditions. Compared with the MNEP, the greedy algorithm
via optimizing the new criterion is computationally more
efficient and effective. The definition of minimum eigenspace
will be given later.
B. Maximal projection on minimum eigenspace (MPME)
Sensor placement is about selecting proper observation
vectors to guarantee that the eigenvalues of ΨM meet certain requirements. To understand how the observation vectors
{ϕsi }ki=1 affect the eigenvalues of Ψk , we introduce the
following theorem.
Theorem 2: For any matrix Φk ∈ Rk×n , the symmetric
matrix Ψk = ΦT
k Φk has a nonincreasing eigenvalue sequence
(k)
{λi }ni=1 , and
(k)

λi

(k)

= kΦk ui k22 =

k
X
(k) 2
(ϕT
sj ui )

(14)

j=1
(k)

(k)

where ui is the normalized eigenvector associated with λi .
Proof: See Appendix A.
(k)
represents the magnitude of the projection
In (14), ϕT
sj ui
(k)
of ϕsj onto the eigenspace span(ui ), which is associated
(k)
with the eigenvalue λi . Theorem 2 shows that the eigenvalue
of Ψk equals the square summation of the projections of all
columns of ΦT
k onto its eigenspace.
(k)
For any k ≥ n, the minimum eigenvalue of Ψk , i.e. λn ,
equals the square summation of the projections of {ϕsi }ki=1
onto the eigenspace associated with the minimum eigenvalue.
However, before the k-th sensing location is determined,
the eigenspace of Ψk is unknown. Therefore, to assess the
(k)
contribution of the all unselected observation vectors for λn ,
we need to solve the eigenvalue problems for all potential
cases, like the MNEP, which is computationally expensive.
To analyze the relation between the observation vectors in
{ϕsi }ki=1 and the eigenspace associated with the minimum
eigenvalue of Ψk , we present the following theorem.
Theorem 3: The normalized eigenvector associated with
(k)
λn of Ψk
2
u(k)
(15)
n = arg minkΦk xk2
kxk2 =1

(k)

and one sufficient and necessary condition of λn > γ is that
for any nonzero normalized vector x ∈ Rn ,
kΦk xk22 > γ

(16)

Proof: See Appendix B.
(k−1)
For any k > n, equation (15) shows that span(un
) is
the subspace onto which the square summation of the projections of {ϕsi }k−1
i=1 is minimum. However, if the minimum
(k−1)
eigenvalue of Ψk−1 , i.e. λn
, is a multiple eigenvalue with
multiplicity µn , considering equations (14) and (15) we can
find that the optimization problem in (15) has µn different

optimal solutions, which are exactly the normalized eigenvectors associated with the minimum eigenvalue of Ψk−1 , i.e.
(k−1)
(k−1)
(k−1)
λn−µn +1 = λn−µn +2 = ... = λn
.
For any k ≤ n, the projection of any vector in {ϕsi }k−1
i=1
onto the null space of Φk−1 , i.e. null(Φk−1 ), is zero. It is
clear that the square summation of the projections of {ϕsi }k−1
i=1
onto any other subspace except the subspace of null(Φk−1 ) is
nonzero. Therefore, null(Φk−1 ) is exactly the subspace with
the highest dimension onto which the square summation of
the projections of all vectors in {ϕsi }k−1
i=1 is minimum.
For simplicity, we introduce a new concept, the minimum
eigenspace, as follows.
Definition 1: For any positive semi-define symmetric matrix A ∈ Rn×n with the nonincreasing eigenvalue sequence
{λi (A)}ni=1 , the minimum eigenspace of A is the eigenspace
associated with all the minimum eigenvalues of A, i.e.
Uk:n (A) = span(uk , uk+1 , ..., un )
where ui is the eigenvector associated with λi (A), and
λk−1 (A) > λk (A) = λn (A).
Equation (16) implies that to meet the requirement on
(M )
λn (= λn ), i.e. λn ≥ γ, the square summation of the
n
projections of {ϕsk }M
k=1 onto any non-trivial subspace of R
should be larger than γ. Therefore, it is reasonable that when
determining the k-th sensing location we select the observation
vector ϕs∗k that has the largest projection onto the non-trivial
subspace onto which the square summation of the projections
of {ϕsi }k−1
i=1 is minimum.
Therefore, if k ≤ n we can select the k-th sensing location
whose observation vector has the largest projection onto the
null space of Φk−1 . It is easily found that the null space
of Φk−1 is exactly the minimum eigenspace of Ψk−1 , i.e.
null(Φk−1 ) = Uk:n (Ψk−1 ). If k > n, the square summation of the projections of {ϕsi }k−1
i=1 onto the µn subspaces
(k−1)
(k−1)
(k−1)
) are
span(un−µn +1 ), span(un−µn +2 ),..., and span(un
is
a
simple
eigenvalue
equal and minimum. Generally, λk−1
n
and µn = 1. If µn > 1 we can select the k-th observation
vector that has the largest projection onto the spanned subspace
(k−1)
(k−1)
(k−1)
), which is exactly the
span(un−µn +1 , un−µn +2 , ..., un
minimum eigenspace of Ψk−1 .
In summary, for all k ≥ 1, we can determine the k-th
sensing location by maximizing the projection of the observation vector on the minimum eigenspace of the current dual
observation matrix Ψk−1 .
For simplicity, we denote
z = (U(k−1) )T ϕsk
(k−1)

(k−1)

(k−1)

(17)

where U(k−1) = [u1
, u2
, ..., un
], and let zi be the
i-th component of z. It is clear that the square of the projection
of ϕsk onto the minimum eigenspace of Ψk−1 is

n
X


zi2
if k < n


n

X
i=k
ζk =
zi2 =
n
X


i=n−µn +1

zi2 if k ≥ n


i=n−µn +1

7

Let Pk−1 be a projection matrix which can project any
vectors in Rn onto the minimum eigenspace of Ψk−1 . When
k < n, the minimum eigenspace of Ψk−1 is the null space of
Φk−1 . Then, we can find that

Algorithm 2: maximal projection on minimum eigenspace

1
2

Pk−1 = In×n − Rk−1 RT
k−1
where Rk−1 = orth(ΦT
k−1 ) whose column vectors are
obtained from the Gram-Schmidt Orthonormalization of all
k−1
the column vectors of ΦT
k−1 , i.e. the vector group {ϕsi }i=1 .
When k ≥ n, it is clear that
Pk−1 = U(k−1)
(U(k−1)
)T
n
n
(k−1)
Un

where
=
can obtain that

Then we

ζk = kPk−1 ϕsk k22
Apparently ζk can be obtained if Φk−1 and ϕsk are known,
i.e. ζk satisfies the first condition of the new criterion used to
replace λn . If ζk 6= 0 for any k < n, the projection of ϕsk onto
null(Φk−1 ) is nonzero; therefore, ϕsk is independent with all
k−1
the vectors in {ϕsi }i=1
, which implies that ζk satisfies the
second condition. Next, we utilize the following theorem to
show that ζk satisfies the third condition.
Theorem 4: Given any observation matrix Φk = [ϕs1 , ϕs2 ,
..., ϕsk ]T ∈ Rk×n , and its corresponding dual observation matrix Ψk = ΦT
k Φk with a nonincreasing eigenvalue sequence
(k) n
{λi }i=1 .
If k ≤ n and Φk is full row-rank, then
ζk
(k)
(18a)
λk =
k−1
P
zi2
1+
(k−1)
(k)
i=1,zi 6=0
(k)

−λk

λi

(k)

λk+1 = λk+2 ... = λ(k)
n =0
(k)

(18b)
(k−1)

and λk is monotonically increasing w.r.t. λk−1 .
If k ≥ n, then
ζk
(k)
(k−1)
λn−µn +1 = λn−µn +1 +
n−µ
Pn
zi2
1+
(k−1)
(k)
i=1,zi 6=0
(k)

(k)

λi

(k−1)
λn−µn +2 = λn−µn +3 ... = λ(k)
n = λn
(M )

i∈N \S

3

(k−1)
(k−1)
(k−1)
[un−µn +1 , un−µn +2 , ..., un
].

(19a)

−λn−µn +1

(19b)

and for any M ≥ n, λn is monotonically increasing w.r.t.
ζk for all k ≤ M .
Proof: See Appendix C.
This theorem shows that λn is monotonically increasing
w.r.t. ζk . Accordingly, WCEV is monotonically decreasing
w.r.t. ζk . It is clear that ζk can be another choice of the criterion
instead of λn to optimize the k-th sensing location. Therefore,
to find the k-th sensing location, we maximize the magnitude
of the projection of ϕsk onto the minimum eigenspace of
Ψk−1 instead of maximizing the minimum nonzero eigenvalue
of Ψk . The greedy sensor placement algorithm, which we call
maximal projection on minimum eigenspace (MPME), is given
in Algorithm 2.
The k-th sensing location is obtained from the optimization
problem in step 2(b) or step 3(a). To solve the optimization
problem, we traverse all the unselected observation vectors

Input: Φ̃ = [ϕ1 , ϕ2 , ..., ϕN ]T ∈ RN ×n
Output: Φ ∈ RM ×n , S , M
Initialization: N = {1, 2, ..., N }, S = ∅.
Determine the first n − 1 sensing locations:
(a) Set Φ0 = [ ], P0 = In×n and k = 1.
(b) ŝk = arg max kPk−1 ϕi k22 .
T
(c) Update: S = S ∪ {ŝk }, Φk = [ΦT
k−1 ϕŝk ] ,
T
Rk = orth(Φk ), Pk = In×n − Rk RT
k.
(d) Set k = k + 1 and repeat step (b-c) until k = n.
Determine the remaining sensing locations:
(a) ŝk = arg max kPk−1 ϕi k22 .
i∈N \S

T
(b) Update: S = S ∪ {ŝk }, Φk = [ΦT
k−1 ϕŝk ] ,
T
T
T
Φk Φk = UΛk U , Pk = Un Un .
(k)
(c) If λn ≥ γ return S, M = k, and Φ = Φk , else set
k = k + 1 and repeat step (a-b).

and find the one that maximizes ζk . Meanwhile, if k ≥ n,
we check the constraint in (7) after each sensing location is
determined. If the constraint is satisfied, stop the algorithm.
C. Discussions about MNEP & MPME
In both algorithms we need to solve the optimization
problem in step 2(b) or step 3(a). In Algorithm 1, to solve
the optimization problem, we need to evaluate the minimum
nonzero eigenvalues of all N −k +1 possible dual observation
matrices, while in Algorithm 2 we compute the projection of
N − K + 1 possible observation vectors onto the minimum
eigenspace of Ψk−1 . The computational cost to find the
eigenvalue of an n × n matrix is much more expensive than
projecting one vector in Rn onto a known subspace. Therefore,
the MPME is computationally much more efficient.
(k)
Equations (18a) shows that λk is monotonic increasing
2
w.r.t. ζk and decreasing w.r.t. zi for all i < k ≤ n. Generally
(k−1)
is a simple eigenvalue when k > n, i.e. µn = 1, and
λn
(19a)-(19b) can be simplified as
ζk

(k−1)
λ(k)
+
n = λn

1+

n−1
P
i=1,zi 6=0

(k)

(20)
zi2
(k−1)

λi

(k)

−λn

Equation (20) shows that λn is monotonic increasing w.r.t.
ζk and decreasing w.r.t. zi2 for all i < n ≤ k. Therefore, the
MNEP algorithm prefers to select the observation vector with
large ζk and small zi2 , which may not be with the largest ζk
but achieves a balance between a large ζk and a small zi2 . It is
Pn
Pk
Pn
(k)
clear that i=1 zi2 = kϕsk k22 and i=1 kϕsi k22 = i=1 λi ;
(k)
(k−1)
2
therefore, small zi means small increment of λi from λi
for all i < k when k < n, and all i < n when k ≥ n.
(k)
(k)
Additionally, (18a) and (20) show that both λk and λn are
(k−1)
monotonically increasing w.r.t. λi
. Therefore, selecting the
observation vector with small zi2 leads to a relatively smaller
(k )
(k )
λk++ and λn + , where k+ > k, and the MPME probably

8

100×20 Gaussian random matrices

4

convex relaxation
SparSenSe
FrameSense
MNEP
MPME
WCEV index threshold=0.3

3

10

2

convex relaxation
SparSenSe
FrameSense
MNEP
MPME
MSE index threshold=1.5

4

10

3

mean MSE Index

10

mean WCEV Index

100×20 Gaussian random matrices

10

1

10

10

2

10

1

10

0

10

0

−1

10

10

20

22

24

26

28
30
32
number of sensor nodes

34

36

38

40

20

100×20 Bernoulli random matrices

5

24

26

28
30
32
number of sensor nodes

34

36

38

40

100×20 Bernoulli random matrices

5

10

10
convex relaxation
SparSenSe
FrameSense
MNEP
MPME
WCEV index threshold=1.5

3

10

convex relaxation
SparSenSe
FrameSense
MNEP
MPME
MSE index threshold=8

4

10
mean MSE index

4

10

mean WCEV index

22

2

10

1

10

3

10

2

10

1

10

0

10

−1

10

20

0

22

24

26

28
30
32
number of sensor nodes

34

36

38

40

10

20

22

24

26

28
30
32
number of sensor nodes

34

36

38

40

Fig. 1: The performance comparison between the MPME and other sensor placement methods for Example 1 and Example 2. For the MPME
and the MNEP we do not consider the stopping criteria but show the mean WCEV index and the mean MSE index w.r.t. the number of
sensor nodes, increasing from 20 to 40. For the SparSenSe method, we do not consider the minimum number of required sensor nodes but
determine the sensing locations like the convex relaxation method by finding the indices of the M largest elements of w∗ .

(k)

outperforms the MNEP in terms of finding the largest λn for
k ≥ n.
In MPME we maximize ζk , which can guarantee a large
minimum nonzero eigenvalue of the updated dual observation
matrix. In MNEP we directly maximize the minimum nonzero
eigenvalue of the current dual observation matrix. Therefore,
(k)
both algorithms guarantee that λn is not much smaller than
(k)
λi for i < n and k ' n, which implies that both algorithms
can guarantee that Ψk is well-conditioned when k ' n. Here,
k ' n means k is slightly larger than n.
In both algorithms, the minimum number of required sensor
(k)
nodes is determined by judging whether λn ≥ γ is satisfied
after each sensing location is determined when k ≥ n. It
is clear that in both algorithms the constraint in (7) is only
considered in step 3(c), i.e. the last sub-step. In other words,
the constraint in (7) is only used to judge whether the number
of sensor nodes is enough.
Remark 2: We can change the constraint in (7) to other
constraints described by MSE or det(Σ), if other measures
are more interesting. Correspondingly, in step 3(c) we check
the new constraint.
IV. EFFECTIVENESS OF THE MPME ALGORITHM
In this section, we provide four examples to illustrate the
effectiveness of the MPME. The detailed analysis of the
comparisons with the state-of-the-art, i.e. the convex relaxation
[1], SparSenSe [2], and FrameSense [3] will also be presented.

Example 1: Φ̃ ∈ R100×20 is a Gaussian random matrix
with independent components ϕij ∼ N (0, 1), and the variance of the sensor noise σ 2 = 1.
Example 2: Φ̃ ∈ R100×20 is a Bernoulli random matrix
with independent components ϕij ∼ B(1, 0.5) with B representing the Binomial distribution, and the variance of the
sensor noise σ 2 = 1.
The mean WCEV index and the mean MSE index of 200
Monte-Carlo simulation run results for the two examples are
given in Fig. 1. The optimization problems (9) and (10)
are solved using the SDPT3 solver [35] and CVX toolbox
[31], respectively. Actually, the SDPT3 solver is used as the
computational engine of the CVX toolbox.
For the i-th (1 ≤ i ≤ 200) simulation run, we determine the
(i)
observation matrix Φk (20 ≤ k ≤ 40) based on the random
signal representation matrix Φ̃(i) , and obtain the following
MSE index and WCEV index from (4) and (5), respectively:
(i)

(i)

MSEk = tr((Ψk )−1 )
(i)
WCEVk
(i)

(i)

=

(i)
λmax ((Ψk )−1 )

(i)

(21)
(22)

where Ψk = (Φk )T Φk . Then, the mean MSE index and
the mean WCEV index of 200 Monte-Carlo simulation run
results are given by
1 X200
(i)
MSEk
i=1
200
1 X200
(i)
WCEVk =
WCEVk
i=1
200
MSEk =

9

index of the convex relaxation method are much larger than
those of MPME, respectively.
100×20 Gaussian random matrices
6

10

mean condition number of Ψk

It is shown in Fig. 1 that for both examples, the MPME
outperforms all the other methods in terms of the mean WCEV
index and the mean MSE index. If the same number of sensor
nodes are used, the MPME can provide the best results of
linear inverse problems as compared with the other methods.
If we set the WCEV index threshold to be 0.3 (i.e.
γ = 10/3) for Example 1, the top left figure shows that
the minimum number of required sensor nodes MMNEP =
MMPME = 23, Mconvex relaxation = MSparSenSe = 28, and
MFrameSense = 37. If we set the MSE index threshold to
be 1.5, the top right figure shows that the minimum number
of required sensor nodes MMPME = 23, MMNEP = 25,
Mconvex relaxation = MSparSenSe = 26, and MFrameSense =
36. Therefore, to meet the accuracy requirement, the proposed
MPME algorithm requires the least number of sensor nodes.
For the Bernoulli random data matrix we can easily obtain the
same conclusion from the bottom two figures.
Fig. 1 shows that MPME outperforms MNEP, which has
been analyzed in Section III-C. Additionally, we find that for
all the five algorithms, the improvement of WCEV and MSE
are increasingly insignificant with an increase in the number
of sensor nodes. It means that the influence of additional
sensor observation declines and its location is not so critical
as the previously determined sensing locations. It is clearly
shown in Fig. 1 that MPME is much better than the convex
relaxation method, SparSenSe, and FrameSense when the
number of sensor nodes is very limited, i.e. the MPME method
significantly outperforms the state-of-the-art in finding the
critical sensing locations, which is analyzed as follows.

convex relaxation
SparSenSe
FrameSense
MNEP
MPME

5

10

4

10

3

10

2

10

1

10

20

22

24

26

28
30
32
number of sensor nodes (k)

34

36

38

40

Fig. 2: The mean condition number of the dual observation matrix
Ψk = ΦT
k Φk for Example 1. Here Φk is obtained from the five
sensor placement algorithms.

In practice, the solution of the convex optimization problem
(9), w∗ ∈ [0, 1]N , is mapped into {0, 1}N to find the sensing
locations. The largest M elements of w∗ are mapped to 1
and other elements are mapped to 0. In such a mapping, the
singularity of Ψ is not considered. The number of sensor nodes
is nearer the dimension of the estimated vector α̂, giving a
higher probability of Ψ being ill-conditioned. However, the
proposed MNEP and MPME algorithms can guarantee a large
minimum nonzero eigenvalue of Ψk and accordingly a wellconditioned ΨM for M ≥ n.

A. Comparison with convex relaxation

B. Comparison with SparSenSe

Fig. 1 shows that the mean MSE index and the mean
WCEV index of the convex relaxation method are much larger
than those of the MPME method when the number of sensor
nodes is slightly larger than the dimension of the vector to be
estimated, i.e. when k ' n = 20 in this example. Comparing
the left two figures with the right two figures in Fig. 1, we
find that when using the convex relaxation method, the WCEV
index (i.e. the maximum eigenvalue of Ψ−1
k , see equation (22))
contributes the main part of the MSE index (i.e. the trace of
Ψ−1
k , see equation (21)), especially when the number of sensor
nodes is small. It means that the maximum eigenvalue of Ψ−1
k
is overwhelmingly larger than the others when k ' n. In other
words, the minimum eigenvalue of Ψk is much smaller than
the other eigenvalues, which implies that Ψk is ill-conditioned,
and hence the estimated vector α̂ is inaccurate.
The mean condition number of Monte-Carlo simulation
result for Example 1 is shown in Fig. 2. For i-th (1 ≤ i ≤ 200)
(i)
simulation run, the condition number of Ψk is denoted by
(i)
κ(Ψk ). The mean condition number is given by
1 X200
(i)
κ(Ψk )
κk =
i=1
200

It is claimed that SparSenSe can determine the minimum
number of required sensor nodes by utilizing the sparsity of
the variable w in (10). With a predefined threshold τ and the
solution of optimization problem (10), i.e. w∗ , if wi∗ < τ set
wi∗ = 0. The sensing indices then exactly correspond to the
nonzero entries of w∗ and the number of nonzero entries is
the minimum number of required sensor nodes. This strategy
works well for the example in [2] in which Φ̃ ∈ R50×2 , and the
largest 3 entries of w∗ are much larger than other elements.
We can set τ as a small value and easily find the largest 3
entries corresponding to the selected sensing indices.
However, this strategy is ineffective if the dimension of the
estimated vector α is large. In the pervious two examples,
w ∈ R100 with at least 20 nonzero entries is not sparse. We
introduce another example to illustrate this problem.
Example 3: Φ̃ ∈ R1500×20 is a Gaussian random matrix
with independent components ϕij ∼ N (0, 1). The variance
of the sensor noise σ 2 = 1, and the maximum acceptable MSE
index γ 0 = 1.5.
In Example 3, N  n guarantees that the decision variable
w is sparse. Fig. 3 shows that if τ = 0.02, 98 sensor
nodes are selected. If τ is set as 0.05 and 0.1, then 71 and
31 sensor nodes are selected, respectively. We can see the
result of SparSenSe from Fig. 4 that 31 sensor nodes can
guarantee that the MSE index is less than the maximum
acceptable MSE index. However, the minimum number of

Fig. 2 shows that for k ≤ 23, Ψk obtained from the convex
relaxation method is ill-conditioned, whereas Ψk obtained
from MNEP or MPME is well-conditioned. Accordingly, as
shown in Fig. 1, the mean MSE index and the mean WCEV

10

1500×20 Gaussian random matrix
selected sensor indices when τ = 0.02
τ = 0.05
τ=0.1

0.25

w*

0.2

0.15

0.1

0.05

0

200

400

600

800
sensor index

1000

1200

1400

Fig. 3: Selected sensing indices with SparSenSe for Example 3.
1500×20 Gaussian random matrix

convex relaxation
SparSenSe
FrameSense
MNEP
MPME
MSE index threshold=1.5

2

MSE Index

10

1

10

0

10

20

22

24

26

28
30
32
number of sensor nodes

34

36

38

40

Fig. 4: The MSE index of α̂ estimated from 20 to 40 sensor
observations for Example 3.

required sensor nodes is 23. For this example, if we set
τ = τ ∗ ∈ [0.1129, 0.1140], the 23 largest elements of w∗
will be selected. In practice, however, the optimal threshold
τ ∗ is a prior unknown; therefore, utilizing the sparsity of w to
determine the minimum number of sensor nodes is ineffective.
In practice, we can set M = n and select the sensing indices
that correspond to the M largest entries of w∗ . Then, we check
whether the accuracy (i.e. WCEV index or MSE index) is
acceptable. If not, increase M , reselect the sensing indices and
recheck the accuracy until the accuracy is acceptable. Using
this strategy for Example 3, we can easily find the minimum
number of required sensor nodes M = 23.
Like the convex relaxation method, Fig. 1 and Fig. 4 shows
that the solutions of MPME are much better than those of
SparSenSe when k ' n. The reason is that the sensing
indices corresponding to the k largest elements of w∗ cannot
guarantee a well-conditioned Ψk as shown in Fig. 2.
C. Comparison with FrameSense
It is apparent from Fig. 1 and Fig. 2 that FrameSense
provides the worst results for the first two examples in which
Φ̃ is not an equal-norm frame, i.e. the norms of the rows of
Φ̃ are not equal. For these cases, minimization of the frame
potential in (11) will select the rows of Φ̃ with small norms
to construct the observation matrix Φ. FrameSense prefers to
drop the rows with large norms [3]. It is easily found that
XM
Xn
kϕsi k2 = tr(Ψ) =
λi
i=1

i=1

Compared this equation with the MSE in (4), we conclude
that small norms of the rows of the observation matrix Φ
lead to a large MSE of the estimated vector α̂. From another
perspective, we find that the smaller the norm of ϕsi for
i = 1, ..., M , the smaller is the signal-to-noise ratio of the
measurement model. Therefore, FrameSense is only suitable
for the case where Φ̃ corresponds to an equal-norm frame.
Actually, even if Φ̃ corresponds to an equal-norm frame,
the proposed MPME algorithm still outperforms FrameSense,
which will be illustrated by the following example.
Example 4: Φ̃ ∈ R100×20 is a random matrix with normalφT
20
i
is a
ized rows, whose i-th row ϕT
i = kφi k , and φi ∈ R
random vector with independent components φij ∼ N (0, 1).
The variance of sensor noise σ 2 = 1.
The mean WCEV index and the mean MSE index of 200
Monte-Carlo run results are shown in Fig. 5. The two figures
show that FrameSense outperforms the convex relaxation
method and SparSenSe when the number of sensor nodes is
small. The right figure shows that the five methods except
MNEP provide almost the same mean MSE indices when the
number of sensor nodes is large enough, which indicates the
effectiveness of FrameSense in pursuing the minimum MSE.
However, like the convex relaxation method and SparSenSe,
in Fig. 5, both WCEV and MSE of FrameSense are much
larger than those of MPME when the number of sensor nodes
is small (e.g., k = 20 or 21), which indicates that FrameSense
cannot guarantee a well-conditioned Ψk when k ' n.
Additionally, Fig. 5 shows that MPME requires the least
number of sensor nodes to meet the accuracy requirement,
and that the required sensor nodes of FrameSense is less than
those of the convex relaxation method and SparSenSe.
If Φ̃ corresponds to an equal-norm frame, the minimum
frame potential of Φ implies the minimum MSE, but the
“worst-out” strategy in FrameSense cannot find the optimal
solution, and even cannot guarantee that Ψ is well-conditioned
if the available sensor nodes is limited. The solution of FrameSense is near-optimal because of the sub-modularity of the
cost function; however our MPME algorithm still outperforms
FrameSense in the four examples. Hence, our future work may
focus on exploring the reasons why MPME outperforms the
near-optimal solution from a theoretical perspective.

D. Local optimization
The four examples show that the current methods are not
suitable for the cases that the number of sensors is small. This
drawback can be overcome by a computationally expensive
technique, i.e. the so called local optimization technique [1].
Definition 2 (Local optimization): For a given set of sensing locations S, exchange one-at-a-time all the sensing location in S with each available candidate location in N /S to
re-locate the sensor nodes at new position that can further
reduce one criterion of interest (e.g., MSE or WCEV) until
there is no further decrease.
This technique is similar with Fedorov’s exchange algorithm
[36], and Wynn’s algorithm [37]. It has also been discussed
in [1], [7]. For any results of local optimization, replacing

11

100×20 normalized Gaussian random matrices

100×20 normalized Gaussian random matrices

5

5

10

10
convex relaxation
SparSenSe
FrameSense
MNEP
MPME
WCEV index threshold=5

mean WCEV index

10

3

10

convex relaxation
SparSenSe
FrameSense
MNEP
MPME
MSE index threshold=35

4

10
mean MSE index

4

2

10

3

10

2

10
1

10

1

10

0

10

20

22

24

26

28
30
32
number of sensor nodes

34

36

38

40

20

22

24

26

28
30
32
number of sensor nodes

34

36

38

40

Fig. 5: The mean WCEV index and mean MSE index of α̂ estimated from 20 to 40 sensor observations for Example 4.
local minimization of WCEV

100×20 Gaussian random matrices

local minimization of MSE

2
1.8

4.5

convex relaxation + local optimization
SparSenSe + local optimization
FrameSense + local optimization
MNEP + local optimization
MPME + local optimization
MPME
WCEV index threshold=0.3

1.4
1.2
1

convex relaxation + local optimization
SparSenSe + local optimization
FrameSense + local optimization
MNEP + local optimization
MPME + local optimization
MPME
MSE index threshold=1.5

4
mean MSE Index

1.6
mean WCEV Index

100×20 Gaussian random matrices

5

0.8
0.6

3.5
3
2.5
2
1.5

0.4

1

0.2
0
20

22

24

26

local minimization of WCEV

28
30
32
number of sensor nodes

34

36

38

0.5
20

40

100×20 normalized Gaussian random matrices

22

24

26

local minimization of MSE

35

28
30
32
number of sensor nodes

34

36

38

40

100×20 normalized Gaussian random matrices

110
100

30

convex relaxation + local optimization
SparSenSe + local optimization
FrameSense + local optimization
MNEP + local optimization
MPME + local optimization
MPME
WCEV index threshold=5

20

80
mean MSE index

mean WCEV index

25

convex relaxation + local optimization
SparSenSe + local optimization
FrameSense + local optimization
MNEP + local optimization
MPME + local optimization
MPME
MSE index threshold=35

90

15

70
60
50
40

10

30
5
20
0
20

22

24

26

28
30
32
number of sensor nodes

34

36

38

40

10
20

22

24

26

28
30
32
number of sensor nodes

34

36

38

40

Fig. 6: The performance comparison between MPME and five methods with local optimization for Example 1 and Example 4.

any selected sensing location by any unselected one cannot
improve the solution, which is called 2-opt.
We apply the local optimization technique to the solutions
obtained from the five methods for the four examples. Fig. 6
shows the mean WCEV indices and the mean MSE indices
of the improved sensor configurations, together with those
directly obtained from MPME, i.e. without local optimization.
In Fig. 6 the solutions of the convex relaxation method,
SparSenSe, and FrameSense are remarkably improved by the
local optimization, especially when the number of sensor
nodes is small. However, the solutions of MPME almost
have no improvement. Nevertheless, the two top figures show
that the solution of MPME without local optimization still
outperforms all the other solutions with local optimization in
terms of both indices.

The bottom right figure shows that with local optimization,
the solution of FrameSense for normalized Gaussian random
matrices are sightly better than the solution of MPME without
local optimization. However, the local optimization is computationally very expensive, and the MPME provides the best
result amongst the five methods for all the other cases. How
the local optimization affects a given sensor configuration and
which types of sensor configuration can be greatly improved
by local optimization are still open problems.

Additionally, Fig. 6 shows that for all cases, to meet the
accuracy requirement, the solutions of MPME without local
optimization require the least number of sensor nodes. From
this perspective, MPME without local optimization outperforms the state-of-the-art with local optimization.

12

TABLE I: The computational effort of the five sensor placement methods
Convex Relaxation
O(ic N 3 )

SparSenSe
O(is N 3 )

FrameSense
O(N 3 )

V. COMPUTATIONAL COST OF THE MPME ALGORITHM
In this section, we compare the computational cost of
MPME with that of the state-of-the-art.
The computational effort of the convex relaxation method
is O(ic N 3 ) [1]. The convex optimization problem is solved
using the interior-point method and ic is the iteration number
Typically, the iteration number is of a few tens [1].
Similar to the convex relaxation method, the computational
effort of SparSenSe is O(is N 3 ) where is is the iteration
number of solving the convex optimization problem (10).
When using FrameSense,
 N −M rows are removed from Φ̃.
It costs O (N − k + 1)2 to determine the k-th removed row.
PN
Since M  N , the total cost of FrameSense is O( i=1 i2 −
PM 2
3
i=1 i ) = O(N ).
Finding the eigenvalues of Ψk costs O(n3 ) operations.
When we find the k-th sensing location via MNEP, the
main computational cost is to solve the minimum nonzero
eigenvalue maximization problem in which N − k + 1 eigen
value problems are solved. The computation cost is O N n3 .
Therefore, to determine all the M sensing locations via MNEP,
the total computational effort is O(N M n3 ).
To determine the k-th sensing location via MPME, the main
computational cost is attributed to the optimization problem

ŝk = arg max kPk−1 ϕi k2 which costs O (N − k + 1)n2 .
i∈N \S

Hence, finding all the M sensing locations costs O(N M n2 ).
N×20 Gaussian random matrices

3

10

mean computation time (second)

2

10

convex relaxation
SparSenSe
FrameSense
MNEP
MPME

1

10

0

10

−1

10

MNEP
O(N M n3 )

MPME
O(N M n2 )

results are shown in Fig. 7. Both Table I and Fig. 7 show that
MPME is computationally the most efficient one amongst the
five algorithms if N  M ≥ n.

VI. C ONCLUSIONS
Sensor placement for linear inverse problems is an interesting but challenging combinatorial problem. The optimal
solution can be solved by the exhaustive search and branchand-bound methods [9], [10], but the methods are both impractical due to the extremely expensive computational cost,
especially for some large scale problems. Therefore, in the
last decade, many works have focused on finding an effective
suboptimal solution via computationally efficient algorithms.
To the best of our knowledge, the proposed MPME algorithm
is computationally one of the most efficient sensor placement
algorithms.
Our proposed MNEP and MPME algorithms select the sensing locations one-by-one. In this way, the minimum number of
the required sensor nodes can be readily determined. Different
with many popular methods, MNEP and MPME can guarantee
that the dual observation matrix is well-conditioned when the
number of sensor nodes is small and even near the dimension
of the estimated vector.
The sufficient and necessary condition of meeting the requirement on WCEV is shown to be that the square summation of the projections of all selected observation vectors
onto any non-trivial subspace of Rn is large enough. The
proposed MPME algorithm determines each sensing location
by maximizing the projection of its observation vector onto the
subspace onto which the square summation of the projections
of all selected observation vectors is minimum.
We perform Monte-Carlo simulations to compare the MNEP
and MPME algorithms with the convex relaxation method [1],
SparSenSe [2], and FrameSense [3]. Based on the simulation
results, we conclude that amongst the five methods:

−2

10

•

−3

10

100

200

300

400
500
600
700
800
number of potential sensing locations (N)

900

1000

Fig. 7: The mean computation time of the five sensor placement
algorithms for N × 20 Gaussian random matrices where N is from
100 to 1000. In the simulations, the number of available sensor nodes,
i.e. M , is set as 20 for the convex relaxation method, FrameSenSe,
MNEP and MPME. The computation time is estimated by the
MATLAB tic-toc commands. The simulation is run in a laptop with
a 2.4GHz Intel i3-3110M processor. The mean computation time is
the mean value of 50 different simulations, and for each simulation,
Φ̃ ∈ RN ×20 with independent entries ϕij ∼ N (0, 1).

We summarize the computational efforts of the five methods
in Table I. The mean computation time of 50 simulation run

•

•

•

To meet the accuracy requirement, the solution of MPME
requires the least number of sensor nodes;
The MPME algorithm provides the best solution in the
sense of minimum WCEV or minimum MSE, especially
when the number of sensor nodes used is small;
MNEP and MPME work well when the number of
available sensor nodes is very limited, while the stateof-the-art cannot;
For the general cases, the solution of the MPME without
local optimization is even better than those of the stateof-the-art with local optimization.

To encourage future works, we provide all the Matlab code
used in this paper, which can be found from IEEE Xplore or
https://github.com/CJiang01/SensorPlacement.git.

13

J = {j|1 ≤ j ≤ n, zj = 0}, removing the j-th row and j-th
column of Λk−1 and Λ̂k yields Λ̃k−1 and Λ̃k , respectively,
and removing the j-th entry of vi and z yields ṽi and z̃,
respectively. Then,

A PPENDIX A
P ROOF OF T HEOREM 2
Proof: The spectrum decomposition of Ψk is
(k)
Ψ k = ΦT
Λk (U(k) )T
k Φk = U
(k)

(k)

(23)

(k)

Λ̃k ṽi = Λ̃k−1 ṽi + z̃z̃T ṽi = λi ṽi

(k)

where U(k) = [u1 , u2 , ..., un ] is an orthonormal matrix,
(k)
and Λk is a diagonal matrix whose diagonal entry Λii =
(k)
λi . Then, we can obtain
(k)
Λk = (U(k) )T ΦT
k Φk U

Proof: For all j ∈ J , removing the j-th row of the
following equation directly yields (27).

(k)
Λk vi = Λk−1 vi + z zT vi = λi vi

from which (14) can be directly found.

(k−1)

λi (A) =

max
dim(U)=i

xT Ax
06=x∈U xT x
min

∈

Proof: See the proof of Theorem 8.1.2 in [28].
Next, we prove Theorem 3.
2
Proof: Since xT Ψk x = xT ΦT
k Φk x = kΦk xk2 , from
Lemma 5 we have
kxk2 =1

(k−1)

rank(Λ̂k − λi

I)

=

(24)

T
2
λ(k)
n = min x Ψk x = min kΦk xk2
kxk2 =1

(k−1)

Lemma 8: If λi
= λi+µi −1 is an eigenvalue of Λk−1
Pi+µ −1
(k−1)
with multiplicity µi and j=i i zj2 6= 0, then λi
is an
eigenvalue of Λ̂k with
µi − 1.
Pi+µmultiplicity
−1
Proof: Since j=i i zj2 6= 0, we can obtain

A PPENDIX B
P ROOF OF T HEOREM 3
To proof Theorem 3, we need the following lemma.
Lemma 5 (Courant-Fischer Minimax Theorem): If A
Rn×n is symmetric, then for i = 1 : n,

(27)

(25)

Then, from (14) and (25), we can obtain (15).
Next, we show the sufficient and necessary condition of
(k)
λn > γ is that for any nonzero normalized vector x ∈ Rn ,
kΦk xk22 > γ.
Sufficiency: Considering (14), if kΦk xk22 > γ for any
(k)
nonzero normalized vector x ∈ Rn , we can obtain λn > γ.
(k)
Necessity: Since λn > γ, considering (25) we conclude
that kΦk xk22 > γ for any nonzero normalized vector x ∈ Rn .

(k−1)

dim span(Λ̂k − λi

=

dim span([Λk−1 −

=

n − µi + 1

I)

(k−1)
λi
I

z])

where for any matrix A, dim span(A) represents the dimension of a linear space spanned by all the column vectors of
(k−1)
A. Therefore, λi
is an eigenvalue of Λ̂k with multiplicity
µi − 1.
(k−1)
is a multiple eigenvalue of Λk−1 with
Lemma 9: If λn
Pn
(k)
2
multiplicity µn and
j=n−µn +1 zj 6= 0, then λn−µn +1 6=
(k−1)
λi
for all i satisfying zi 6= 0.
Proof: It follows from Theorem 1 that
(k−1)

λi

≤ λi

(k)

≤ λi−1

(k−1)

for all 1 < i ≤ n

(28)

(k−1)

(k)

(k−1)

(29)

Hence,
λn−µn +1 ≤ λn−µn +1 ≤ λn−µn
Then, considering Lemma 8, we can obtain
(k)

(k−1)

(k)

λn−µn +1 > λn−µn +1 = λ(k−1)
= λn−µn +2 = λ(k)
n
n

(30)

(k−1)

A PPENDIX C
P ROOF OF T HEOREM 4

Denote the multiplicity of λn−µn w.r.t. Λk−1 by µ, where
µ ≥ 1. Hence,

Considering (17) and (23), we can obtain another description of Ψk , i.e.

λn−µn −µ > λn−µn −µ+1 = λn−µn −µ+2 = ... = λn−µn (31)
Pn−µn
(k−1)
If i=n−µ
z 2 6= 0, considering Lemma 8, λn−µn is
n −µ+1 i
an eigenvalue of Λ̂k with multiplicity µ − 1. Therefore, if

T
(k−1)
Ψk= ΦT
(Λk−1+zzT)(U(k−1))T (26)
k−1Φk−1+ϕskϕsk = U

Let Λ̂k = Λk−1 + zzT . From (23) and (26), we find that Ψk ,
Λk , and Λ̂k are mutually similar, which implies that they share
the same eigenvalues.
To proof Theorem 4, we need the following four lemmas.
(k−1)
Lemma 6: If zi = 0, λi
is an eigenvalue of Λ̂k , and
the corresponding eigenvector is ei
Proof: As zi = 0, we can obtain
(k−1)

Λ̂k ei = Λk−1 ei + zzT ei = λi
(k−1)

ei

It is clear that λi
is an eigenvalue of Λ̂k and ei is the
corresponding eigenvector.
Lemma 7: For all i ∈ I = {i|1 ≤ i ≤ n, zi 6= 0}, denote
(k)
by vi the eigenvector of Λ̂k associated with λi . For all j ∈

(k−1)

(k−1)

(k−1)

(k−1)

(k−1)

(k)

λn−µn = λn−µn +1

(32)

(k)

the multiplicity of λn−µn +1 w.r.t. Λ̂k is µ − 1 and
(k)

(k)

(k)

(k)

λn−µn +1 = λn−µn = ... = λn−µn −µ+3 < λn−µn −µ+2 (33)
(k−1)

(k)

From (31)-(33), we can obtain λn−µn −µ+1 < λn−µn −µ+2 ,
(k)
which obviously contradict with (28). Hence, λn−µn +1 6=
(k−1)
λn−µn .
Pn−µn
2
Consequently, if
i=n−µn −µ+1 zi 6= 0, considering (29)
and (30) we can obtain
(k−1)

(k)

(k−1)

(k−1)

λn−µn +1 < λn−µn +1 < λn−µn ≤ λj

, j < n − µn

14

else (

Pn−µn

2
i=n−µn −µ+1 zi

(k−1)

(k)

= 0)

(k)

(k−1)

(k−1)

λn−µn +1 < λn−µn +1 ≤ λn−µn ≤ λj

, j < n − µn

which implies this lemma.
Next, leveraging the four Lemmas, we are ready to prove
Theorem 4.
(k−1)
Proof: Let λn
be the minimum eigenvalue of Ψk−1
(k−1)
(Λk−1 ) with multiplicity µn (≥ 1). If k < n, λn
= 0 and
µn = n − k + 1. From Lemma 8, we can directly obtain (18b)
and (19b).
Pn
If i=n−µn +1 zi2 = 0, it is obvious that ζk = 0. According
to Lemma
Pn 6, we can2 easily obtain (18a) and (19a).
If
i=n−µn +1 zi 6= 0, according to Lemma 7, we can
obtain
(k)

(Λ̃k−1 − λn−µn +1 I)ṽn−µn +1 + z̃(z̃T ṽn−µn +1 ) = 0

(34)

(k)
Lemma 9 can guarantee that Λ̃k−1 −λn−µn +1 I is nonsingular,
and therefore from (34), we find that z̃T ṽn−µn +1 6= 0. Then,
(k)
left multiplying z̃T (Λ̃k−1 −λn−µn +1 I)−1 to both sides of (34)

yields

(k−1)

Since λn−µn +1 > 0 and λi
> 0 for all i ≤ n − µn , we
(k)
(k−1)
can obtain that dλn−µn +1 /dλn−µn ≥ 0, which implies that
(k)
(k−1)
λn−µn +1 is monotonically increasing w.r.t. λn−µn , i.e.
(k−1)

(k)

(k−1)

(k−1)

(k)

(k−1)

(k−1)

(k)
dλn−µn+1
(k−1)
dλn−µn+1

(k−1)

(k−1)

λi

Taking the derivative of ζk w.r.t.
that
dζk

=1+

(k)

dλn−µn+1
(k−1)

(k−1)

n−µ
Xn

(λi

(k−1)

i=1,zi 6=0

(k)

− λn−µn +1

(k)
λn−µn+1 ,

(λi

(35)

we can obtain

(k)

− λn−µn+1 )2

where ‘a ↔ b’ means that b is monotonically increasing w.r.t.
a.
(k−1)
Taking derivative of both sides of (35) w.r.t. λn−µn and with
some operations, we can obtain
(k−1)

dλn−µn
where
x=

(k)

=

2
λn−µn +1 zn−µ
n
(k−1)

(k)

(λn−µn − λn−µn +1 )2 (1 + x)

n−µ
Xn

(k−1) 2
zi
(k−1)
(k)
− λn−µn +1 )2
i=1,zi 6=0 (λi

λi

1+

zi2
(k)
(k−1)
−λn−µn +1 )2
(λ
i=1,zi 6=0 i
n−µ
Pn

(k−1)
(k−1)
−λn−µn+1 )zi2
(k)
(k−1)
−λn−µn +1 )2
(λ
i=1,zi 6=0 i

(λi

(k−1)

(k)

(k+1)
)
ζk ↔ λ(k)
↔ ... ↔ λ(M
n ↔ λn
n

(39)

(40)

If µn > 1, from (36) and (37) we can obtain that
(k)

(k+1)

ζk ↔ λn−µn +1 ↔ λn−µn +2 ↔ ... ↔ λn(k+µn −1)

(41)

is a simple eigenvalue, considering (39) and
Since λn n
(41) we can find
)
n)
ζk ↔ λn(k+µn −1) ↔ λ(k+µ
↔ ... ↔ λ(M
n
n

(42)

From (40)-(42), we can obtain that
(M )
λ(n)
n ↔ λn

(k−1)

(k−1)

(k)

=

n−µ
Pn

Since λi
≥ λn−µn +1 for all i ≤ n − µn , we can obtain
(k)
(k−1)
(k)
that dλn−µn +1 /dλn−µn +1 > 0, which implies that λn−µn +1
(k−1)
is monotonically strictly increasing w.r.t. λn−µn +1 ; therefore,

− λn−µn+1 )zi2

Since λi
≥ λn−µn +1 for all i ≤ n − µn , it is obvious that
(k)
(k)
dζk /dλn ≥ 1. Therefore, 0 < dλn−µn +1 /dζk ≤ 1, which
(k)
implies that λn−µn +1 is monotonically strictly increasing w.r.t.
ζk , i.e.
(k)
ζk ↔ λn−µn +1
(36)

dλn−µn +1

1+

(k+µ −1)

(k−1)

(λn−µn+1 −λn−µn+1 )zi2

i=1,zi 6=0

(38)

For n ≤ k ≤ M , generally µn = 1 and from (36) and (39)
we can obtain that

from which we can directly obtain (19a). If k ≤ n, λk
=0
and µn = n − k + 1, substituting them into (19a) yields (18a).
It is clear that equation (19a) is a general description of
(18a). From (19a), we can obtain

ζk = λn−µn+1−λn−µn+1 +

is

Taking the derivative of both sides of (35) w.r.t. λn−µn+1
and with some operations, we can obtain that

(k−1)

(k)

(k)

(k)

λk−1 ↔ λk

λn−µn +1 ↔ λn−µn +1

1 + z̃T (Λ̃k−1 − λn−µn +1 I)−1 z̃ = 0

n−µ
Xn

(37)

If k ≤ n, we have µn = n − k + 1 and therefore, λk
(k−1)
monotonically increasing w.r.t. λk−1 for all k ≤ n, i.e.



(k)
z̃T ṽn−µn +1 1 + z̃T (Λ̃k−1 − λn−µn +1 I)−1 z̃ = 0
Hence,

(k)

λn−µn ↔ λn−µn +1

(43)

(k−1)

w.r.t. Ψk−1 is n−k+1,
For k < n, the multiplicity of λn
i.e. µn = n − k + 1. Then, considering (36), (38) and (43), we
can obtain that
(k)

(k+1)

(M )
ζk ↔ λk ↔ λk+1 ↔ ... ↔ λ(n)
n ↔ λn

(44)

In summary, from (40), (42) and (44), we can conclude that
(M )
for any M ≥ n, λn is monotonically increasing w.r.t. ζk for
all k ≤ M .
R EFERENCES
[1] S. Joshi and S. Boyd, “Sensor selection via convex optimization,” IEEE
Trans. Signal Process., vol. 57, no. 2, pp. 451–462, 2009.
[2] H. Jamali-Rad, A. Simonetto, and G. Leus, “Sparsity-aware sensor
selection: Centralized and distributed algorithms,” IEEE Signal Process.
Lett., vol. 21, no. 2, pp. 217–220, 2014.
[3] J. Ranieri, A. Chebira, and M. Vetterli, “Near-optimal sensor placement
for linear inverse problems,” IEEE Trans. Signal Process., vol. 62, no. 5,
pp. 1135–1146, 2014.
[4] S. Liu, A. Vempaty, M. Fardad, E. Masazade, and P. K. Varshney,
“Energy-aware sensor selection in field reconstruction,” IEEE Signal
Process. Lett., vol. 21, no. 12, pp. 1476–1480, 2014.

15

[5] K. Cohen, S. Siegel, and T. McLaughlin, “A heuristic approach to
effective sensor placement for modeling of a cylinder wake,” Comput.
Fluids, vol. 35, no. 1, pp. 103–120, 2006.
[6] K. Willcox, “Unsteady flow sensing and estimation via the gappy proper
orthogonal decomposition,” Comput. Fluids, vol. 35, no. 2, pp. 208–226,
2006.
[7] B. Yildirim, C. Chryssostomidis, and G. Karniadakis, “Efficient sensor
placement for ocean measurements using low-dimensional concepts,”
Ocean Model., vol. 27, no. 3, pp. 160–173, 2009.
[8] P. Astrid, S. Weiland, K. Willcox, and T. Backx, “Missing point
estimation in models described by proper orthogonal decomposition,”
IEEE Trans. Autom. Control, vol. 53, no. 10, pp. 2237–2251, 2008.
[9] E. L. Lawler and D. E. Wood, “Branch-and-bound methods: A survey,”
Oper. Res., vol. 14, no. 4, pp. 699–719, 1966.
[10] W. J. Welch, “Branch-and-bound search for experimental designs based
on D-optimality and other criteria,” Technometrics, vol. 24, no. 1, pp.
41–48, 1982.
[11] S. P. Chepuri and G. Leus, “Continuous sensor placement,” IEEE Signal
Process. Lett., vol. 22, no. 5, 2015.
[12] M. Shamaiah, S. Banerjee, and H. Vikalo, “Greedy sensor selection:
Leveraging submodularity,” 49th IEEE Conf. Decision Control (CDC),
2010, pp. 2572–2577.
[13] L. Yao, W. A. Sethares, and D. C. Kammer, “Sensor placement for
on-orbit modal identification via a genetic algorithm,” AIAA journal,
vol. 31, no. 10, pp. 1922–1928, 1993.
[14] S. Lau, R. Eichardt, L. Di Rienzo, and J. Haueisen, “Tabu search
optimization of magnetic sensor systems for magnetocardiography,”
IEEE Trans. Magn., vol. 44, no. 6, pp. 1442–1445, 2008.
[15] M. Naeem, S. Xue, and D. Lee, “Cross-entropy optimization for sensor
selection problems,” Int. Symp. Common. Info. Tec. (ISCIT), 2009, pp.
396–401.
[16] S. P. Chepuri and G. Leus, “Sparsity-promoting sensor selection for
non-linear measurement models,” IEEE Trans. Signal Process., vol. 63,
no. 3, pp. 684–698, 2015.
[17] S. P. Chepuri, G. Leus et al., “Sparsity-exploiting anchor placement
for localization in sensor networks,” Proc. Eur. Signal Process. Conf.
(EUSIPCO), 2013, pp. 1–5.
[18] Y. Mo, R. Ambrosino, and B. Sinopoli, “Sensor selection strategies
for state estimation in energy constrained wireless sensor networks,”
Automatica, vol. 47, no. 7, pp. 1330–1338, 2011.
[19] X. Shen and P. K. Varshney, “Sensor selection based on generalized
information gain for target tracking in large sensor networks,” IEEE
Trans. Signal Process., vol. 62, no. 2, pp. 363–375, 2014.
[20] E. Iuliano and D. Quagliarella, “ Proper orthogonal decomposition, surrogate modelling and evolutionary optimization in aerodynamic design,”
Comput. Fluids, vol. 84, pp. 327–350, 2013.
[21] X. Shen, S. Liu, and P. Varshney, “Sensor selection for nonlinear systems
in large sensor networks,” IEEE Trans. Aerosp. Electron. Syst., vol. 50,
no. 4, pp. 2664–2678, 2014.
[22] S. Liu, M. Fardad, E. Masazade, and P. K. Varshney, “Optimal periodic
sensor scheduling in networks of dynamical systems,” IEEE Trans.
Signal Process., vol. 62, no. 12, pp. 3055–3068, 2014.
[23] S. P. Chepuri and G. Leus, “Sparsity-promoting adaptive sensor selection for non-linear filtering,” IEEE Int. Conf. Acoust., Speech, Signal
Process.(ICASSP), 2014, pp. 5080–5084.
[24] S. Liu, E. Masazade, M. Fardad, and P. K. Varshney, “Sparsity-aware
field estimation via ordinary kriging,” IEEE Int. Conf. Acoust., Speech,
Signal Process.(ICASSP), 2014, pp. 3948–3952.
[25] H. Wang, K. Yao, G. Pottie, and D. Estrin, “Entropy-based sensor
selection heuristic for target localization,” Proc. Int. Symp. Inf. Process.
Sens. Netw., 2004, pp. 36–45.
[26] D. MacKay, “Information-based objective functions for active data
selection,” Neural comput., vol. 4, no. 4, pp. 590–604, 1992.
[27] C. Guestrin, A. Krause, and A. P. Singh, “Near-optimal sensor placements in gaussian processes,” Proc. Int. Conf. Mach. Learn., 2005, pp.
265–272.
[28] G. H. Golub and C. F. Van Loan, Matrix computations, JHU Press, 2013.
[29] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization:
Algorithms and Complexity, Courier Corporation, 1998.
[30] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004.
[31] M. Grant and S. Boyd (2014), CVX: Matlab software for disciplined convex programming, Version 2.1 [Online]. Available: http://cvxr.com/cvx/.
[32] J. J. Benedetto and M. Fickus, “Finite normalized tight frames,” Adv.
Comput. Math., vol. 18, no. 2-4, pp. 357–385, 2003.
[33] J. Kovacevic and A. Chebira, “Life beyond bases: The advent of frames
(part I),” IEEE Signal Process. Mag., vol. 24, no. 4, pp. 86–104, 2007.

[34] R. Thompson, “The behavior of eigenvalues and singular values under
perturbations of restricted rank,” Linear Algebra Appl., vol. 13, no. 1,
pp. 69–78, 1976.
[35] K. C. Toh, M. J. Todd and R. H. Tütüncü, “SDPT3 – a MATLAB
software package for semidefinite programming, version 1.3,” Optim.
Methods Softw., vol. 11, no. 1-4, pp. 545–581, 1999.
[36] A. J. Miller and N.-K. Nguyen, “Algorithm as 295: A fedorov exchange
algorithm for D-optimal design,” Appl. Stat., pp. 669–677, 1994.
[37] H. P. Wynn, “Results in the theory and construction of D-optimum
experimental designs,” J. R. Stat. Soc. Series B, pp. 133–147, 1972.

