Sparse Recovery over Graph Incidence Matrices: Polynomial Time
Guarantees and Location Dependent Performance

arXiv:1803.09631v1 [] 26 Mar 2018

Mengnan Zhao, M. Devrim Kaba, René Vidal, Daniel P. Robinson, and Enrique Mallada
Abstract— Classical results in sparse recovery guarantee the
exact reconstruction of a sparse signal under assumptions on
the dictionary that are either too strong or NP hard to check.
Moreover, such results may be too pessimistic in practice since
they are based on a worst-case analysis. In this paper, we
consider the sparse recovery of signals defined over a graph,
for which the dictionary takes the form of an incidence matrix.
We show that in this case necessary and sufficient conditions
can be derived in terms of properties of the cycles of the
graph, which can be checked in polynomial time. Our analysis
further allows us to derive location dependent conditions for
recovery that only depend on the cycles of the graph that
intersect this support. Finally, we exploit sparsity properties on
the measurements to a specialized sub-graph-based recovery
algorithm that outperforms the standard `1 -minimization.

I. INTRODUCTION
Sparse recovery methods have been a popular approach to
compress and process data in recent years [1], [2], that have
found widespread applications in data acquisition [3], machine learning [4], [5], medical imaging [6]–[8], networking
[9]–[11], etc.
In this framework, the goal is to recover a signal x ∈ Rn
from its linear measurements y ∈ Rm , where y = Φx for a
matrix Φ ∈ Rm×n with m < n. In general, this problem is
ill-posed unless we make additional assumptions about x.
For example, if we assume that x is s-sparse, where s 
n, then we can formulate the problem of recovering x from
y as the following `0 -minimization problem:
min kxk0 s.t. y = Φx

(1)

where kxk0 is the number of nonzero entries in x. However,
this problem is known to be NP-hard [12]. To address this
challenge, a common strategy is to solve the following
convex relaxation of (1) based on `1 -minimization:
min kxk1 s.t. y = Φx.

(2)

The latter problem can be cast as a linear program, and the
sparse signal can successfully be recovered from (2), if the
measurement matrix Φ satisfies certain conditions.
In general, these conditions are either computationally
hard to verify, or often too conservative, which leads to false
negative certificates. For example, the Nullspace Property
(NUP) [13] – which provides a necessary and sufficient
M. Zhao and E. Mallada are with the Department of Electrical and
Computer Engineering, M.D. Kaba and D.P. Robinson are with the Department of Applied Mathematics and Statistics, and R. Vidal is with
the Department of Biomedical Engineering, at The Johns Hopkins University, Baltimore, MD 21218, USA. Emails: {mzhao21, mkaba1,

rvidal, daniel.p.robinson, mallada}@jhu.edu
This work was supported by NSF grant AMPS 1736448.

condition – and the Restricted Isometry Property (RIP) [14],
[15] – which is only sufficient – are both NP-Hard [16].
On the other hand, the Mutual Coherence [17] property is a
sufficient condition that can be efficiently computed [16].
Yet, it is conservative and fails to certify many practical
measurement matrices where recovery is possible.
However, the major limitation of these recovery guarantees
and their computational complexity analysis stems from the
worst case approach used in their derivation. For example,
the fact that NUP and RIP are NP-hard does not prohibit
efficient verification of them for a particular subclass of
matrices Φ. Similarly, even when the NUP is not satisfied
for a sparsity level s, it may still be possible to recover
the s-sparse signal within a subset of the possible supports.
These observations suggest that a more specialized analysis
that exploits specific application structure and that derives location/support dependent guarantees can lead to significantly
less restrictive outcomes. We develop such analysis here for
the case of graph incidence matrices.
In this paper, we study sparse recovery of signals defined
over graphs using the incidence matrix. Our interest in
incidence matrices stems from the fact that it is a fundamental representation of graphs, and thus a natural choice
for dictionary in analysis of network flows. In various application areas like communication networks, social networks,
and transportation networks, the incidence matrices appear
very naturally when we would like to model the flow of
information, disease, and goods. The search for the cause of
a change in the observation at the nodes of these networks
which took place after a rare, hence sparse, event at some
of the edges, can be modeled as (1), where the incidence
matrix is used as a measurement matrix.
The main contributions of this paper is as follows:
1) We derive a topological characterization of the NUP
of incidence matrix which overcomes NP-hardness in
this case.
2) We derive necessary and sufficient conditions of perfect recovery in terms of cycles of the graph, both
globally and locally.
3) We propose a specialized algorithm which utilizes the
sparsity pattern of the measurement that requires even
weaker conditions for recovery guarantees.
The remainder of this paper is organized as follows. In
Section II we review preliminary concepts. In Section III
we formulate the problem and develop conditions for global
and location-dependent recovery, and propose an efficient
algorithm to solve the problem. Numerical results to confirm

the main theorems are presented in Section IV, followed by
brief conclusion in Section V.

8
9

II. PRELIMINARIES
A. Notation
We will denote the `p -norm by k · kp for p ≥ 1. As it is
common in the literature, with a slight abuse of notation, we
will denote the function which counts the nonzero entries
of a vector by k · k0 . Although, mathematically speaking,
this function does not classify as a norm, we will stick to
the common practice and call it the `0 -norm of the vector.
For p ≥ 1, we define the unit `p -sphere, Sn−1
, in Rn as
p
n−1
n
Sp
:= {x ∈ R : kxkp = 1}. Similarly, the unit `p -ball,
Bnp , will be defined as Bnp := {x ∈ Rn : kxkp ≤ 1}.
The nullspace of a matrix Φ will be denoted by Null(Φ).
As usual, |S| denotes the cardinality of a set S. For a vector
x ∈ Rn and a nonempty index set S ⊆ {1, . . . , n}, we denote
the projection onto the coordinates in S by ΓS and the result
of the projection is denoted by xS . That is, ΓS : Rn → R|S|
and xS := ΓS (x).
B. Convex analysis
Here we briefly review concepts from convex analysis.
Our main interest is in extreme points of a convex set and
quasi-convex functions.
Definition 1: An extreme point of a convex set C ⊂
Rn is a point in C which cannot be written as a convex
combination of two different points from C.
Definition 2: Let C ⊆ Rn be a convex set. A function
f : C → R is called quasi-convex if for all x, y ∈ C and
λ ∈ [0, 1] we have
f (λx + (1 − λ)y) ≤ max{f (x), f (y)}
It is also easy to show that a function f : C → R is
quasi-convex if and only if every sublevel set Sα := {x ∈
C | f (x) ≤ α} is a convex set. An example of a quasiconvex function is the `p -norm function k · kp for p ≥ 1.
More generally, every convex function is quasi-convex. The
following result on quasi-convex functions is well-known in
the literature, but we still include it for completeness.
Proposition 1: Let C ⊂ Rn be a compact convex set and
f : C → R be a continuous quasi-convex function. Then f
attains its maximum over an extreme point of C.
C. Graph theory
A directed graph with the vertex set V = {v1 , . . . , vm }
and the edge set E = {e1 , . . . , en } ⊆ V × V will be denoted
by G(V, E). When the edge and vertex sets are irrelevant to
the discussion, we will drop them from the notation and
simply denote the graph by G. The graph G is called simple
if there is at most one edge connecting any two vertices and
no edge of G starts and ends at the same vertex, i.e. G has
no self loops. In the rest of the paper G will always denote
a simple directed graph with finite number of edges and
vertices. While in this paper we focus on directed graphs,
our analysis will only require the undirected versions of
definitions for paths, cycles, and connectivity.

1

1

/



2

4


o
4

8



7
O
2

3


3

7

5

/

5

6

/

6

o

10

9

Fig. 1: A simple connected directed graph.

We say that the two vertices a, b ∈ V are adjacent if either
(a, b) ∈ E or (b, a) ∈ E. A sequence (u1 , . . . , ur ) of distinct
vertices of a graph G such that ui and ui+1 are adjacent for
all i ∈ {1, . . . , r − 1} will be called a path. We will say
that the graph G is connected if for any two distinct vertices
a, b ∈ V , there exists a path starting from a and ending at b.
A sequence (u1 , . . . , ur , u1 ) of adjacent vertices of a graph
G is called a (simple) cycle if r ≥ 3 and ui 6= uj whenever
i 6= j. The length of such a cycle is r. The length of the
shortest simple cycle in a graph G is called the girth of G.
For an acyclic graph, the girth is defined to be +∞.
The incidence matrix A = A(G) ∈ Rm×n of the graph G
is defined as


−1, if vi is the initial vertex of the edge ej ,
aij =
1, if vi is the terminal vertex of the edge ej ,


0, otherwise.
(3)
Let C = (u1 , . . . , ur , ur+1 = u1 ) be a simple cycle of a
simple directed graph G. Then, C can be associated with a
vector w ∈ Rn , where each coordinate wi is given by


 1, if ei = (uj , uj+1 ) for some j ∈ {1, . . . , r}
wi = −1, if ei = (uj+1 , uj ) for some j ∈ {1, . . . , r}


0, otherwise.
(4)
In this way the set of all simple cycles of G spans a subspace
in Rn , which is called the cycle space of G.
Remark 1: The cycle space of G is exactly the nullspace
of incidence matrix A(G).
Remark 2: The dimension of the nullspace of A is n −
m + k where k is the number of connected components of
the graph G. Hence, the rank of A is m − k.
Example 1: The incidence matrix of the graph in Fig. 1
is given by


−1 0 0 −1 0 0 0 0 0 0
 1 −1 0 0 0 0 0 0 1 0 


 0 1 −1 0 −1 0 0 0 0 0 


0 0 1 1 0 0 0 0 0 0



A=
 0 0 0 0 1 −1 0 0 0 0  ,
 0 0 0 0 0 1 −1 0 0 1 


0 0 0 0 0 0 1 1 0 0


 0 0 0 0 0 0 0 −1 −1 0 
0 0 0 0 0 0 0 0 0 −1

with w1 , w2 ,

w1 = 1

w2 = 0

w3 = 1

w3 being the three simple cycles in the graph
T
1 1 −1 0 0 0 0 0 0
T
1 0 0 1 1 1 −1 1 0
T
0 1 −1 −1 −1 −1 1 −1 0

Notice that w3 = w1 −w2 and hence Null(A) is of dimension
2. The addition/subtraction operations on wi ’s correspond to
“addition/subtraction” of edges.
D. Sparse Recovery
Here we formally define the nullspace property and review
other relevant concepts and results from sparse recovery
literature.
Definition 3 (Nullspace Property, NUP): A matrix Φ ∈
Rm×n is said to satisfy the nullspace property (NUP) of
order s, if for any η ∈ Null(Φ) \ {0}, and any nonempty
index set S ⊆ {1, . . . , n} with |S| ≤ s, we have
kηS k1 < kηS c k1
where ηS (resp. ηS c ) denotes the part of η supported on S
(and the complement S c of S in {1, . . . , n} resp.).
Another relevant concept for our discussion is the spark
of a matrix.
Definition 4 (Spark): The spark of a matrix Φ ∈ Rm×n
is the smallest number of linearly dependent columns in Φ.
Formally, spark(A) = minη6=0 kηk0 s.t. Φη = 0.
And it is bounded from above by the rank of the matrix
spark(A) ≤ rank(A) + 1.

(5)

Spark provides a necessary and sufficient condition for
uniqueness of sparse solutions.
Lemma 1: For any matrix Φ ∈ Rm×n , the s-sparse signal
x0 ∈ Rn is the unique solution to the optimization problem
min kxk0

Φx0 =Φx

preferable. Hence, one needs a theorem akin to Proposition 2,
but addressing the solutions of the optimization problem
min kxk1 .

This leads us to the study of NUP for incidence matrices.
In this paper, for the incidence matrix A ∈ Rv×e of a
simple, connected graph G with e edges and v vertices, and
an s-sparse vector x̄ ∈ Re , we would like to answer the
following questions:
1) Under which necessary and sufficient conditions A
satisfies NUP of order s? This would guarantee the
global recovery of the s-sparse signals x̄ as a solution
of (6).
2) If global recovery is not possible, can we characterize
the sparse signals that are recoverable via (6) in terms
of the support of the signal and the topology of the
graph G?
3) Can we utilize the support of the measurement Ax̄
to simplify equation (6) and successfully recover the
sparse signal x̄?
A. Topological Characterization of Nullspace Property for
Incidence Matrices
Before addressing the questions above in detail, we would
like to build a simple framework to study them. We will start
with a reformulation of NUP.
Lemma 2: A matrix Φ ∈ Rm×n satisfies NUP of order s
if and only if
max

|S|≤s

III. M AIN R ESULTS
It is not very hard to prove that spark(A) of an incidence
matrix and the girth of the underlying graph G are equal.
Hence, combining this fact with Lemma 1, one can immediately reach the following result.
Proposition 2: Let A ∈ Rv×e be the incidence matrix of
a simple, connected graph G with girth g. Then, for every
s-sparse vector x̄ ∈ Re , x̄ is the unique solution to the
optimization problem
min kxk0

Ax̄=Ax

if and only if s < g2 .
Even though as a uniqueness result Proposition 2 is useful,
it doesn’t come in handy when we would like to recover
the original signal x̄ from the measurements Ax̄. For this
purpose, `1 -relaxation of the optimization problem is more

max

x∈ΓS (Null(Φ)∩Bn
1)

kxk1 <

1
2

(7)

where ΓS : Rn → Rs denotes the projection onto the
coordinates indexed by S.
Proof: Since kηk1 = kηS k1 + kηS c k1 , Φ satisfies the
nullspace property of order s, if and only if
max

|S|≤s

if and only if spark(Φ) > 2s.

(6)

Ax̄=Ax

1
kηS k1
< .
2
η∈Null(Φ)\{0} kηk1
max

Without loss of generality, we could scale every vector η ∈
Null(Φ)\{0} to the unit `1 -sphere Sn−1
to get the equivalent
1
formulation
1
max
max
kηS k1 < .
2
|S|≤s
η∈Null(Φ)∩Sn
1
Since replacing Sn−1
with Bn1 does not change the result
1
of maximization, and ηS = ΓS η, we get the optimization
problem (7).
Remark 3: The maximum value on the left hand side of
(7) is the so-called nullspace constant in the literature [16].
The calculation of the nullspace constant for an arbitrary
matrix Φ and sparsity s is known to be NP-hard [16].
The reformulation of NUP in Lemma 2 has certain benefits. For a fixed index set S ⊆ {1, . . . , n}, it draws our
attention to the optimization problem
max

x∈ΓS (Null(Φ)∩Bn
1)

kxk1

(8)

which is nothing but the maximization of a continuous quasiconvex function k·k1 on a compact convex set ΓS (Null(Φ)∩
Bn1 ). Thanks to Proposition 1, we know that such a maximum
is attained at the extreme points of ΓS (Null(Φ) ∩ Bn1 ).
Therefore, understanding the extreme points of this set is of
utmost importance. Naturally, it can be a hard task to carry
out for arbitrary matrices Φ. However, one can still set a
bound on the sparsity of the extreme points of Null(Φ)∩Bn1 .
Lemma 3: Let Φ ∈ Rm×n be an m × n matrix and let r
denote the rank of Φ. Then each extreme point of Null(Φ) ∩
Bn1 is at most (r + 1)-sparse.
Proof: If dim(Null(Φ)) = n − r ≤ 1, the theorem
holds trivially.
The unit `1 -sphere in Rn is a union of (n−1)-dimensional
simplices. Hence, if dim(Null(Φ)) = n − r ≥ 1, each
extreme point is contained in an (n−1)-dimensional simplex.
In particular, if dim(Null(Φ)) = n − r > 1, we argue
that, no extreme point of Null(Φ) ∩ Bn1 lies in the interior
of these (n − 1)-dimensional simplices. This is because in
this case the intersection of Null(Φ) and the interior of
the (n − 1)-dimensional simplex is either empty, or a nonsingleton open convex subset of Rn , where every point is
a convex combination of two distinct points. Hence, no
extreme point can live there. So, the extreme points must
lie in the boundary of (n − 1)-dimensional simplices, which
are (n − 2)-dimensional simplices. Moreover, these (n − 1)dimensional simplices are where one coordinate becomes
zero. Hence, at least one coordinate of an extreme point
living in an (n − 2)-dimensional simplex is zero.
As long as the sum of the dimension of the simplex which
contains the extreme point, and the dimension of Null(Φ) is
strictly larger than n, we could repeat the argument in the
previous paragraph. This argument stops when the dimension
of the simplex containing the extreme point is r. This means
that at least n − r − 1 coordinates of the extreme point has to
be zero, and therefore each extreme point is at most (r + 1)sparse.
Lemma 3 is akin to (5), yet it is stronger in the sense that
the statement bounds the sparsity of all the extreme points,
not just the most sparse vectors in the nullspace of Φ. Once
we have Lemma 3, it turns out that for incidence matrices,
these extreme points have a nice characterization in terms of
the properties of the underlying graph.
Proposition 3: Let A ∈ Rv×e be the incidence matrix of
a simple connected graph G with Null(A) % {0}, and let
W1 denote the set of normalized simple cycles of G, i.e.


w
W1 :=
: w ∈ Re corresp. to a simple cycle . (9)
kwk1
Then, the extreme points of the convex set Null(A) ∩ Be1 are
contained in W1 .
Proof: Let z ∈ Null(A) ∩ Be1 be an extreme point. Suppose that kzk0 = ē. Let S := supp(z), and let Ḡ denote the
subgraph consisting of the edges in S. Suppose that Ḡ has v̄
vertices and k̄ connected components. Let Ā ∈ Rv̄×ē denote
the incidence matrix of Ḡ. We set zS := ΓS z. Obviously, zS
has only nonzero entries, and zS ∈ Null(Ā) ∩ Bē1 . We claim

that zS is an extreme point of Null(Ā) ∩ Bē1 . Because, if
one could write zS as a convex combination of two distinct
vectors in Null(Ā) ∩ Bē1 , then one could pad these vectors
with zeros at the coordinates in S c to come up with two
distinct vectors in Null(A) ∩ Be1 , whose convex combination
gives z, and this would contradict the fact that z is an extreme
point. Hence, zS is an extreme point of Null(Ā) ∩ Bē1 and,
by Lemma 3, ē = kzS k0 ≤ rank(Ā)+1 = v̄ − k̄ +1. That is,
dim(Null(Ā)) = ē − v̄ + k̄ ≤ 1. On the other hand, since we
have 0 6= zS ∈ Null(Ā), we conclude that dim(Null(Ā)) =
1, and so Null(Ā) is spanned by zS . Then, obviously, zS
corresponds to the unique simple cycle in Ḡ. In addition,
since zS has no zero entries, the corresponding simple cycle
leaves no edges of Ḡ out. Therefore, Ḡ corresponds to a
simple cycle in G, and so, z is contained in W1 .
It is easy to see that each extreme point of ΓS (Null(A) ∩
Be1 ) is the image of an extreme point of Null(A) ∩ Be1 under
ΓS . Therefore, Proposition 3 provides a way to study the
maximization problem (8).
Theorem 1: Let A ∈ Rv×e be the incidence matrix of a
simple, connected graph G, and let W1 denote the set of
normalized simple cycles of G as in (9). Let S ⊆ {1, . . . , e}
be a nonempty index set. If we denote the projection onto
the coordinates in S by ΓS : Re → R|S| , then
max

x∈ΓS (Null(A)∩Be1 )

kxk1 =

max kΓS wk1

w∈W1

(10)

Proof: Since k · k1 is a continuous quasi-convex
function, and ΓS (Null(A) ∩ Be1 ) is a compact convex set,
the maximum on the left of equation (10) will be attained at
extreme points of ΓS (Null(A) ∩ Be1 ). These extreme points
are contained in ΓS W1 by Proposition 3. Therefore, it’s
enough to check the value of kΓS (·)k1 on W1 to get the
maximum.
Theorem 1 builds a connection between the algebraic
condition NUP and a topological property of the graph,
namely its simple cycles. This connection is what we will
mainly exploit in the rest of the paper.
B. Global Recovery Performance
The answer to the first question we posed above comes
immediately from Theorem 1.
Theorem 2: Let A ∈ Rv×e be the incidence matrix of
a simple, connected graph G with girth g. Then, for every
s-sparse vector x̄ ∈ Re , x̄ is the unique solution to the
optimization problem
min kxk1

Ax̄=Ax

if and only if s < g2 .
Proof: From Lemma 2 and Theorem 1, NUP of order
s is satisfied if and only if
1
max max kΓS wk1 <
2
|S|≤s w∈W1
It is easy to see that this maximum is attained at the smallest
cycle when S picks maximum number of edges of this cycle.
Therefore,
s
max max kΓS wk1 = min{ , 1}.
g
|S|≤s w∈W1

Hence we get the result.
Remark 4: As we mentioned in Remark 3, calculating the
nullspace constant is NP-hard in general. However, there are
algorithms which can calculate the girth of a graph exactly in
O(ev), or sufficiently accurately for our purposes in O(v 2 ),
[18]. Therefore, the proof of Theorem 2 reveals that the
nullspace constant can be calculated - Hence, NUP can be
verified - for incidence matrices of graphs in polynomial
time.
Being a global recovery result, Theorem 2 only regards
the cardinality s of the support of the unknown signal. For
a graph with small girth (e.g., g = 3), this means that in
terms of global recovery guarantees, the sparsity that can
be tolerated is very low. However, it’s natural to ask the
following question: Given a graph with relatively small girth,
could we still recover signals with sparsity larger than or
equal to g2 ? This leads us to the study of location dependent
recovery performance, where we not only focus on the
cardinality of the support of the unknown signal x̄ anymore,
but also take the location of the support in the graph into
account.

Remark 5: The graph in Fig. 1 has girth g = 4. Thus, by
Theorem 2, we can recover any 1-sparse signal. However, in
reality, signals which are supported on more than one edge
could also be recovered. For instance, a signal supported on
edges {2, 7} or {4, 6, 8} could be recovered as a solution of
the `1 -relaxation problem, since in each of the three simple
cycles, the number of edges selected by the support of the
unknown vector is less than a half of the length of the simple
cycle. This also reveals that different sparsity patterns will
have different recovery performance.
Remark 6: Theorem 3 states that given the support of
the signal, one can check all simple cycles in the graph
containing the support for local recovery guarantee. A number of algorithms with polynomial time bound for cycle
enumeration are summarized in [19].
In comparison to Theorem 2, Theorem 3 provides a
deeper insight on vectors x̄ which can be recovered from
the observations Ax̄ via `1 -minimization. More specifically,
any vector whose support picks strictly less than half of the
number of edges for every simple cycle in the graph can
successfully be recovered.

C. Location-dependent Recovery Performance

D. Recovery Using Sparsity of Measurement

v×e

Theorem 3: Let A ∈ R
be the incidence matrix of a
simple, connected graph G, and let W1 denote the set of
normalized simple cycles of G as in (9) and S ⊆ {1, . . . , e}
be a nonempty subset. Then, for every vector x̄ ∈ Re with
supp(x̄) ⊆ S, x̄ is the unique solution to the optimization
problem
min kxk1
(11)
Ax̄=Ax

if and only if
|S ∩ supp(w)|
1
< .
| supp(w)|
2
Proof: First we note that for a given w ∈ W1
max

w∈W1

(12)

|S ∩ supp(w)|
= kΓS wk1 .
| supp(w)|
Hence, (12) is equivalent to requiring that for all η ∈
Null(A) \ {0},
kηS k1 < kηS c k1 ,
(13)

Theorem 3 gives a necessary and sufficient condition for
exact recovery given supp(x). In practice, this information
is usually missing. However, the special structure of the
incidence matrix and its connection to the graph could help
us circumvent this problem. Notice that the columns of
the incidence matrix is always 2-sparse and therefore, the
measurement y := Ax will be 2s-sparse for any s-sparse
signal x. This gives us an additional information about
the support of the unknown signal x. In principle, with
probability 1 on the sparse signal x, we immediately know
a superset of supp(x) by observing supp(y), i.e. the nodes
with nonzero measurements. This observation gives rise to
Algorithm 1, which reduces the size of the problem.
Remark 7: There are cases where Algorithm 1 may fail.
Consider two signals x1 and x2 = x1 + wα where wα ∈
Null(A). Then, the support of the two signals x1 and
x2 can differ significantly, although the two signals yield

Algorithm 1 Recovery of unknown signal utilizing sparse
vertex measurements
1: INPUT: y ∈ Rv , A ∈ Rv×e
2: Set x̂ = 0.
3: Take Ṽ = supp(y) corresponding to the set of vertices
By triangle inequality
with nonzero measurements in graph G. Let ỹ = yṼ .
4: Select Ẽ = {(vi , vj ) : vi , vj ∈ Ṽ } ∩ E and form the
Since supp(x) ⊆ S
subgraph G̃(Ṽ , Ẽ).
By (13)
5: Construct the incidence matrix Ã of the subgraph G̃.
Since supp(x) ⊆ S
6: Solve the `1 minimization problem

by Theorem 1 and Lemma 2. Once we have (13), we argue
in a familiar way.
Sufficiency: Let z ∈ Re \ {x̄} such that Ax̄ = Az. We set
θ := x̄ − z ∈ Null(A) \ {0}. Then,
kx̄k1 ≤ kx̄S − zS k1 + kzS k1
= kθS k1 + kzS k1
< kθS c k1 + kzS k1
= k − zS c k1 + kzS k1 = kzk1

Hence, x̄ is the unique solution to (11).
Necessity: Let η ∈ Null(A)\{0}. Then 0 = Aη = A(ηS +
ηS c ). That is, AηS = A(−ηS c ). Since, supp(ηS ) ⊆ S, by
uniqueness we get kηS k1 < kηS c k1 . Then by the arguments
in the first paragraph of this proof, we get the result.

x̃ = arg min kxk1
ỹ=Ãx

7:
8:

Set x̂Ẽ = x̃.
return x̂ ∈ Re

8
8



1

7
O
4


o
4

7

3

3

/

5

5

6

/

o

6

10

9

Fig. 2: Acyclic subgraph G̃ induced by an unknown signal
with support S = {3, 4, 5, 6, 7, 8, 10}.

the same measurement. Hence, Algorithm 1 may wrongly
exclude some nodes. However, this case will happen with
zero measure given that the signal has random support and
random values.
Corollary 1: Let A ∈ Rv×e be the incidence matrix of
a simple, connected graph G. Given a random signal x̄, let
y := Ax̄, and let G̃ be the subgraph associated with y in
Algorithm 1. Then, Algorithm 1 will almost surely recover
signal x̄ if and only if supp(x̄) picks strictly less than half
of the edges from each simple cycle of G̃.
The proof of this corollary follows directly from Theorem
3.
In comparison to `1 -minimization on the original graph,
Algorithm 1 will have improved local recovery performance,
since the formation of the subgraph will eliminate many
cycles, especially in large scale networks. A simple example
is shown below.
Remark 8: Consider the graph in Fig. 1. Let x be
a random signal which is supported on the edges
{3, 4, 5, 6, 7, 8, 10}, so that there are nonzero measurements
on nodes {1, 3, 4, 5, 6, 7, 8, 9}. This is a case where x cannot
be recovered using the incidence matrix of the original graph.
However, the subgraph G̃ is acyclic, as shown in Fig. 2,
which allows perfect recovery via Algorithm 1.
IV. S IMULATIONS
In this section we provide numerical simulation results
on the recovery performance of the incidence matrix. In

Fig. 4: Probability of perfect recovery for graph in Fig. 3.

all experiments, the signal x has random support with each
nonzero entry drawn i.i.d. from normal distribution. We used
the CVX software package [20] to solve the optimization
problems. A vector is declared to be recovered successfully
if the error is less than or equal to 10−5 in `2 norm.
Experiment 1: Fig. 4 shows the probability of perfect
recovery of signals via `1 -relaxation over a series of graphs
consisting of two cycles (Fig. 3). Each of these graphs has
a smaller cycle of fixed length 3 and a larger one of varying
length 3, 5, 7, 9, and 11, respectively. For each sparsity level,
1000 trials were done. According to Theorem 2, for all
graphs we can recover 1-sparse signals for sure since the
girth is 3 for each graph in the series. When sparsity level is
increased, we expect that the graphs with a larger cycle will
provide better recovery performances, since it becomes less
likely that the support of the random signal will pick more
than half of the edges for one of the simple cycles in the
graph. This is in accordance with our observation in Fig. 4.
Experiment 2: In this experiment we evaluate the performance of Algorithm 1 and direct `1 -minimization on a
graph with 20 nodes. Fig. 6 shows the performance of both
algorithms on a simple cycle connecting node 1 to node
20 in order (shown in Fig. 5 blue edges). Fig. 7 shows
the performance of both methods on graph with additional

2 g

3
$

E

1


l+1

Fig. 3: The graph in Experiment 1 which consists of a small
cycle of length 3 and a larger cycle of varying length l ∈
{3, 5, 7, 9, 11}.

Fig. 5: An example network in Experiment 2

R EFERENCES

Fig. 6: Comparison of Algorithm 1 and direct `1 minimization on cycle with 20 nodes.

Fig. 7: Comparison of Algorithm 1 and direct `1 minimization on network in Fig. 5.

edges (Fig. 5 red edges) connecting each node to its third
neighbor, i.e., (1, 4), (2, 5) · · · (17, 20) · · · (20, 3). For each
sparsity, the experiments are repeated for 100 times to
compute recovery probability. For a single cycle, Algorithm
1 outperforms direct `1 -minimization since it will lead to an
acyclic subgraph in some cases. For graph with small cycles
in Fig. 5, Algorithm 1 will eliminate small cycles and thus
lead to higher recovery probability for fixed s. It is easy to
see that the two methods will have same performance for
complete graphs, which we will not show here.
V. C ONCLUSION
In brief, in this paper we studied sparse recovery for graph
incidence matrices. For these matrices we provided a characterization of NUP in terms of the topological properties of the
underlying graph. This characterization allowed us to verify
global recovery guarantees in polynomial time. Moreover,
we showed that the location-dependent recovery performance
can also be analyzed in terms of the simple cycles of the
graph. Finally, using the special structure of the incidence
matrix, an efficient algorithm which exploits the structure
of the graph is proposed and its performance is evaluated
numerically.

[1] D. L. Donoho, “Compressed sensing,” IEEE Transactions on information theory, vol. 52, no. 4, pp. 1289–1306, 2006.
[2] S. Mallat, A wavelet tour of signal processing: the sparse way.
Academic press, 2008.
[3] E. J. Candès and M. B. Wakin, “An introduction to compressive
sampling,” IEEE signal processing magazine, vol. 25, no. 2, pp. 21–30,
2008.
[4] E. Elhamifar and R. Vidal, “Sparse subspace clustering,” in Computer
Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference
on, pp. 2790–2797, IEEE, 2009.
[5] J. Wright, A. Y. Yang, A. Ganesh, S. S. Sastry, and Y. Ma, “Robust face
recognition via sparse representation,” IEEE transactions on pattern
analysis and machine intelligence, vol. 31, no. 2, pp. 210–227, 2009.
[6] M. Lustig, D. Donoho, and J. Pauly, “Rapid mr imaging with compressed sensing and randomly under-sampled 3dft trajectories,” in
Proc. 14th Ann. Meeting ISMRM, Citeseer, 2006.
[7] M. Lustig, D. Donoho, and J. M. Pauly, “Sparse mri: The application
of compressed sensing for rapid mr imaging,” Magnetic resonance in
medicine, vol. 58, no. 6, pp. 1182–1195, 2007.
[8] E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles:
Exact signal reconstruction from highly incomplete frequency information,” IEEE Transactions on information theory, vol. 52, no. 2,
pp. 489–509, 2006.
[9] M. Coates, Y. Pointurier, and M. Rabbat, “Compressed network
monitoring,” in Statistical Signal Processing, 2007. SSP’07. IEEE/SP
14th Workshop on, pp. 418–422, IEEE, 2007.
[10] J. Haupt, W. U. Bajwa, M. Rabbat, and R. Nowak, “Compressed
sensing for networked data,” IEEE Signal Processing Magazine,
vol. 25, no. 2, pp. 92–101, 2008.
[11] W. Xu, E. Mallada, and A. Tang, “Compressive sensing over graphs,”
in INFOCOM, 2011 Proceedings IEEE, pp. 2087–2095, IEEE, 2011.
[12] R. G. Michael and S. J. David, “Computers and intractability: a guide
to the theory of np-completeness,” WH Free. Co., San Fr, pp. 90–91,
1979.
[13] A. Cohen, W. Dahmen, and R. DeVore, “Compressed sensing and best
k-term approximation,” Journal of the American mathematical society,
vol. 22, no. 1, pp. 211–231, 2009.
[14] E. J. Candes and T. Tao, “Decoding by linear programming,” IEEE
transactions on information theory, vol. 51, no. 12, pp. 4203–4215,
2005.
[15] R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, “A simple
proof of the restricted isometry property for random matrices,” Constructive Approximation, vol. 28, no. 3, pp. 253–263, 2008.
[16] A. M. Tillmann and M. E. Pfetsch, “The computational complexity
of the restricted isometry property, the nullspace property, and related
concepts in compressed sensing,” IEEE Transactions on Information
Theory, vol. 60, no. 2, pp. 1248–1259, 2014.
[17] D. L. Donoho and X. Huo, “Uncertainty principles and ideal atomic
decomposition,” IEEE transactions on information theory, vol. 47,
no. 7, pp. 2845–2862, 2001.
[18] A. Itai and M. Rodeh, “Finding a minimum circuit in a graph,” SIAM
Journal on Computing, vol. 7, no. 4, pp. 413–423, 1978.
[19] P. Mateti and N. Deo, “On algorithms for enumerating all circuits of
a graph,” SIAM Journal on Computing, vol. 5, no. 1, pp. 90–99, 1976.
[20] M. Grant, S. Boyd, and Y. Ye, “Cvx: Matlab software for disciplined
convex programming,” 2008.

