Sparse Recovery over Graph Incidence Matrices
Mengnan Zhao M. Devrim Kaba René Vidal Daniel P. Robinson Enrique Mallada




Influence of stellar structure, evolution and rotation 
 on the tidal damping of exoplanetary spin-orbit angles
    C. Damiani
          1,2
          S. Mathis 3,4
          
    Received xxx, 2017; accepted xxx
===============================================================================================================









Classical results in sparse recovery guarantee the exact reconstruction of s-sparse signals under assumptions on the dictionary that are either too strong or NP-hard to check. Moreover, such results may be 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 derive necessary and sufficient conditions for sparse recovery, which depend on properties of the cycles of the graph that can be checked in polynomial time. We also derive support-dependent conditions for sparse recovery that depend only on the intersection of the cycles of the graph with the support of the signal. Finally, we exploit sparsity properties on the measurements and the structure of incidence matrices to propose a specialized sub-graph-based recovery algorithm that outperforms the standard ℓ_1-minimization approach.






§ INTRODUCTION

Recently, sparse recovery methods (e.g. see <cit.>) have become very popular for compressing and processing high-dimensional data. In particular, they have found widespread applications in data acquisition <cit.>, machine learning <cit.>, medical imaging <cit.>, and networking <cit.>. 

The goal of sparse recovery is to reconstruct a signal x̅∈ℝ^n from m<n linear measurements y=Φx̅∈ℝ^m, where Φ∈ℝ^m× n is the measurement matrix (also known as dictionary or sparsifying basis). In general, the recovery problem is ill-posed unless x̅ is assumed to satisfy additional assumptions. For example, if we assume that x̅ is s-sparse[The vector x̅ is s-sparse if and only if at most s of its entries are nonzero.], where s ≪ n, then mild conditions on the measurement matrix Φ (see Lemma <ref>) allow for the recovery x̅ from y using the ℓ_0-minimization problem

    min_x x_0   s.t.   y=Φ x,

where x_0 denotes the number of nonzero entries in x. However, problem (<ref>) is known to be NP-hard <cit.>. To address this challenge, a common strategy is to solve a convex relaxation of (<ref>) based on ℓ_1-minimization given by

    min_x x_1   s.t.  y=Φ x,

which can be written equivalently as a linear program.  It is known that the sparse signal can be recovered from (<ref>) if the measurement matrix Φ satisfies certain conditions. In general, these conditions are either computationally hard to verify, or too conservative so that false negative certificates are often encountered. For example, the Nullspace Property (NUP)<cit.>, which provides necessary and sufficient conditions for sparse recovery, and the Restricted Isometry Property (RIP) <cit.>, which is only a  sufficient condition for sparse recovery, are both NP-hard <cit.> to check. On the other hand, the Mutual Coherence <cit.> property is a sufficient condition that can be efficiently verified<cit.>, but is conservative in that it fails to certify that sparse recovery is possible for many measurement matrices seen in practice. 

Another major limitation of these recovery guarantees and their associated computational complexity arises because they must allow for the worst case problem in their derivation. For example, the fact that the NUP and RIP are NP-hard to check does not prohibit efficient verification for particular subclasses of matrices. Similarly, even when the NUP is not satisfied for a sparsity level s, it may still be possible to recover certain subsets of s-sparse signals by exploiting additional knowledge about their support. These observations suggest studying the sparse recovery problem for subclasses of matrices and signals to obtain conditions that are easier to verify as well as specialized algorithms with improved recovery performance.










The goal of this paper is to study sparse recovery of signals that are defined over graphs when the measurement matrix is the graph's incidence matrix. 
Our interest in incidence matrices stems from the fact that they are a fundamental representation of graphs, and thus a natural choice for the dictionary when analyzing network flows. In various application areas like communication networks, social networks, and transportation networks, the incidence matrices naturally appear when modeling the flow of information, disease, and goods (e.g., the detection of sparse structural network changes via observations at the nodes can be modeled as (1), where the incidence matrix serves as a measurement matrix).


The main contributions of this paper are as follows:


  * We derive a topological characterization of the NUP for incidence matrices. Specifically, we show that the NUP for these matrices is equivalent to a condition on simple cycles of the graph, which is a finite subset of the nullspace of the incidence matrix. As a consequence, we show that for incidence matrices the sparse recovery guarantee depends only on the girth[Girth: Size of the smallest cycle.] of the underlying graph. This overcomes NP-hardness, as the girth of a graph can be calculated in polynomial time.


  * Using the above topological characterization, we further derive necessary and sufficient conditions on the support of the sparse signal that enable its recovery. Specifically, for incidence matrices we show that all signals with a given support can be recovered via (<ref>) if and only if the support consists of strictly less than half of the edges in every simple cycle of the graph. Since our conditions on x̅ depend on its support, we will refer to them as support-dependent conditions.


  * We propose a specialized algorithm that utilizes the knowledge of the support of the measurements and the structure of incidence matrices to constrain the support of the signal x̅, and consequently can guarantee sparse recovery of x̅ under even weaker conditions.


The remainder of this paper is organized as follows: In Section II we review basic concepts from convex analysis, graph theory, and sparse recovery. In Section III we formulate sparse recovery problem for incidence matrices, derive conditions for sparse and support-dependent recovery, and propose an efficient algorithm to solve the problem. In Section IV we present numerical experiments that illustrate our theoretical results, and in Section V we provide some conclusions.






 






§ PRELIMINARIES




 §.§ Notation

Given x∈^n, we let x_p for p≥ 1 denote the ℓ_p-norm, and denote the function that counts the number of nonzero entries in x by x_0. Although, the latter function is not a norm, we follow the common practice of calling it the ℓ_0-norm. 
For p≥ 1, we define the unit ℓ_p-sphere in ℝ^n as 𝕊_p^n-1 := {x∈ℝ^n : x_p=1}.
Similarly, the unit ℓ_p-ball in ^n is defined as 
𝔹_p^n := {x∈ℝ^n : x_p≤ 1}.

The nullspace of a matrix Φ will be denoted by (Φ). 


As usual, |S| denotes the cardinality of a set S. For a vector x∈ℝ^n and a nonempty index set S⊆{1,…, n}, we denote the subvector of x that corresponds to S by x_S, and the associated mapping by Γ_S : ℝ^n →ℝ^|S|, i.e., 

x_S:= Γ_S(x). The complement of S in {1,…, n} is denoted by S^c.



 §.§ Convex analysis


Critical to our analysis will be the notion of extreme points of a convex set and of quasi-convex functions.

An extreme point of a convex set C⊂ℝ^n is a point in C that cannot be written as a convex combination of two different points from C. The set of all extreme points of a convex set C ⊂ℝ^n is denoted by (C).  



Let C⊆ℝ^n be a convex set. A function f:C→ℝ is called quasi-convex if and only if for all x,y ∈ C and λ∈ [0,1] it holds that

    f(λ x + (1-λ)y) ≤max{f(x), f(y)}.



It is easy to show that a function f:C→ℝ is quasi-convex if and only if every sublevel set 
S_α:={x∈ C  |   f(x)≤α}
is a convex set. Every convex function is quasi-convex. In particular, ℓ_p-norm functions for p≥ 1 are quasi-convex. The next  result on quasi-convex functions <cit.> is included for completeness.


Let C⊂ℝ^n be a compact convex set and f:C→ℝ be a continuous quasi-convex function. Then f attains its maximum value at an extreme point of C. 




 §.§ Graph theory


A directed graph with vertex set V={v_1, …, v_m} and edge set E={e_1,…, e_n}⊆ V× V will be denoted by 𝒢(V,E).

When the edge and vertex sets are irrelevant to the discussion, we will drop them from the notation and denote the graph by 𝒢. Sometimes the vertex set and the edge set of 𝒢 will be denoted by V(𝒢) and E(𝒢) respectively. A graph 𝒢 is called simple if there is at most one edge connecting any two vertices and no edge starts and ends at the same vertex, i.e. 𝒢 has no self loops. Henceforth, 𝒢 will always denote a simple directed graph with a finite number of edges and vertices. 

Although we focus on directed graphs, our analysis only requires the undirected variants of the definitions for paths, cycles, and connectivity.

We say that two vertices {a,b}⊆ V are adjacent if either (a,b)∈ E or (b,a)∈ E. A sequence (u_1,…, u_r) of distinct vertices of a graph 𝒢 such that u_i and u_i+1 are adjacent for all i∈{1,…,r-1} is called a path. A connected component 𝒢̂ of 𝒢 is a subgraph of 𝒢 in which any two distinct vertices are connected to each other by a path and no edge exists between V(𝒢̂) and V(𝒢)∖ V(𝒢̂). We will say that the graph 𝒢 is connected (for directed graphs this is often referred to as weakly connected) if 𝒢 has a unique connected component.



A sequence (u_1,…, u_r, u_1) of adjacent vertices of a graph 𝒢 is called a (simple) cycle if r≥ 3 and u_i≠ u_j whenever i≠ j; the  length of such a cycle is r. 


The length of the shortest simple cycle of a graph 𝒢 is called the girth of 𝒢. For an acyclic graph (i.e., a graph with no cycles), the girth is defined to be +∞. Since acyclic graphs are not interesting for our purposes, we will assume that the girth is finite. That is, the graph has at least one simple cycle.


Associated with a directed graph 𝒢 = 𝒢(V,E), we can define the incidence matrix A=A(𝒢) ∈ℝ^m × n as

    a_ij=
    
    -1,     if  v_i  is the initial vertex of edge  e_j, 
    -1,     if  v_i  is the terminal vertex of edge  e_j,
    -0,     otherwise.



For a nonempty index set S⊆{1, …, n}, the subgraph of 𝒢 consisting of edges {e_j| j∈ S} is denoted by 𝒢_S. The incidence matrix of 𝒢_S is denoted by A_S.
Let 𝒞 = (u_1,…, u_r, u_r+1=u_1) be a simple cycle of a simple directed graph 𝒢. Then, 𝒞 can be associated with a vector w(𝒞)∈ℝ^n, where each coordinate w_j of w(𝒞) is defined as

    w_j=
    -1,     if  e_j = (u_i,u_i+1) for some i∈{1,…, r}
    
    -1,     if  e_j= (u_i+1, u_i) for some i∈{1,…, r}
    -0,     otherwise.










We now define the cycle space of 𝒢 as the subspace spanned by {w(𝒞) |𝒞 is a simple cycle of 𝒢}.[Sometimes this subspace is called the Flow Space <cit.>.]



The cycle space of 𝒢 is exactly the nullspace of the incidence matrix A(𝒢) <cit.>.

 
The dimension of the nullspace of A(𝒢) is n-m+k, where k is the number of connected components of 𝒢. Hence, the rank of A(𝒢) is m-k <cit.>.















 





The incidence matrix of the graph in Fig. <ref> is given by

    A=
    [ -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;  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 ],



















and the vectors from (<ref>) associated with the simple cycles

    𝒞_1    = (1,2,3,4,1), 
    𝒞_2    = (2,3,5,6,7,8,2), 
    𝒞_3    = (1,2,8,7,6,5,3,4,1)

are given by 

    w_1   =[  1  1  1 -1  0  0  0  0  0  0 ]^T
    
    w_2   =[  0  1  0  0  1  1  1 -1  1  0 ]^T
    
    w_3   =[  1  0  1 -1 -1 -1 -1  1 -1  0 ]^T.

Note that w_3=w_1-w_2, so that (A(𝒢)) must be of dimension 2. The addition/subtraction operations on w_j's correspond to “addition/subtraction" operations on edges.





 §.§ Sparse Recovery




It is known <cit.> that every vector x̅∈ℝ^n with (x̅)⊆ S is the unique solution to (<ref>)
if and only if 

    η_S_1 < η_S^c_1
     for all η∈(Φ)∖{0}.

This leads us to the definition of the Nullspace Property.
 
A matrix Φ∈ℝ^m× n is said to satisfy the nullspace property (NUP) of order s, if for any η∈(Φ) ∖{0}, and any nonempty index set S⊆{1,…,n} with |S|≤ s, we have

    η_S_1 < η_S^c_1.




Another needed concept is the spark of a matrix.


The spark of a matrix Φ∈ℝ^m× n is the smallest number of linearly dependent columns in Φ. Formally, we have
(Φ):=min_η≠ 0η_0 s.t. Φη=0.


We note that the rank of a matrix may be used to bound its spark.  Specifically, it holds that


    (Φ) ≤(Φ)+1.

The spark may be used to provide a necessary and sufficient condition for uniqueness of sparse solutions <cit.>.

For any matrix Φ∈ℝ^m× n, the s-sparse signal x̅∈ℝ^n is the unique solution to the optimization problem

    min_Φx̅ = Φ xx_0

if and only if (Φ)>2s.




§ MAIN RESULTS

It is not difficult to prove that the spark of an incidence matrix A is equal to the girth of the underlying graph 𝒢. By combining this fact with Lemma <ref>, we obtain the following.

Let A = A(𝒢) ∈ℝ^m× n be the incidence matrix of a simple, connected graph 𝒢 with girth g. Then, for every s-sparse vector x̅∈ℝ^n, x̅ is the unique solution to 


    min_Ax̅=Axx_0

if and only if s < g/2.




Even though Proposition <ref> is useful as a uniqueness result, it does not come in handy when one would like to recover the original signal x̅ from the measurements Ax̅. For this purpose, an ℓ_1-relaxation of the optimization problem is preferable. Hence, one needs a theorem akin to Proposition <ref> that addresses the solutions of the optimization problem

    min_Ax̅=Axx_1.

This leads us to study the NUP for incidence matrices. Specifically, in this section we answer the following questions about the incidence matrix A∈ℝ^m × n of a simple connected graph 𝒢 with n edges and m vertices, and an s-sparse vector x̅∈ℝ^n:













  * What are necessary and sufficient conditions for A to satisfy the NUP of order s? Such conditions would guarantee sparse recovery, i.e., that any s-sparse signal x̅ can be recovered as the unique solution to (<ref>).

  * If traditional sparse recovery is not possible, can we characterize subclasses of sparse signals that are recoverable via (<ref>) in terms of the support of the signal and the topology of the graph 𝒢(V,E)?

  * Can we use the support of the measurement Ax̅ and the structure of A to derive constraints on the support of x̅ that allow us to modify (<ref>) and successfully recover the sparse signal x̅? 




 §.§ Topological Characterization of the Nullspace Property for the Class of 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 the NUP.


A matrix Φ∈ℝ^m× n satisfies the NUP of order s if and only if

    max_|S|≤ s  max_η∈(Φ)∩𝔹^n_1η_S_1 < 1/2.



For η∈(Φ)∖{0}, using η_1=η_S_1+η_S^c_1, we get

    η_S_1 < η_S^c_1
     if and only if η_S_1/η_1 < 1/2.

Using this inequality and Definition <ref>, it follows that 
Φ satisfies NUP of order s if and only if

    max_|S|≤ s  sup_η∈(Φ)∖{0}η_S_1/η_1 < 1/2.

Since the objective function in (<ref>) is independent of the scale of η, the condition in (<ref>) is equivalent to 


    max_|S|≤ s  max_η∈(Φ)∩𝕊^n-1_1η_S_1 < 1/2.

Since we can replace 𝕊^n-1_1 with 𝔹^n_1 (this does not change the result of the maximization problem), we find that (<ref>) is equivalent to (<ref>), as claimed.



The value of the left hand side of (<ref>) is called the nullspace constant in the literature <cit.>. The calculation of the nullspace constant for an arbitrary matrix Φ and sparsity s is known to be NP-hard <cit.>.


The reformulation of the NUP in Lemma <ref> has certain benefits. 
For a fixed index set S⊆{1,…, n}, it draws our attention to the optimization problem

    max_η∈(Φ)∩𝔹^n_1η_S_1

which is the maximization of a continuous convex function Γ_S(·)_1 over a compact convex set (Φ)∩𝔹^n_1. 

Thus, it follows from Proposition <ref> that the maximum is attained at an extreme point of (Φ)∩𝔹^n_1. This leads us to want to understand the extreme points of this set, which can be a computationally involved task for arbitrary matrices Φ. Nonetheless, one can still set a bound on the sparsity of the extreme points of (Φ)∩𝔹^n_1.


If Φ∈ℝ^m× n is an m× n matrix of rank r,

then extreme points of (Φ)∩𝔹_1^n are at most (r+1)-sparse. 


If ((Φ)) ≡ n-r≤ 1, then the result of the lemma holds trivially since r+1 ≥ n.

The unit ℓ_1-sphere in ^n, namely 𝕊_1^n-1, may be written as the union of (n-1)-dimensional simplices. Hence, if ((Φ)) ≡ n-r≥ 1, each extreme point is contained in an (n-1)-dimensional simplex. 

In particular, if ((Φ)) ≡ n-r>1, we argue that, no extreme point of (Φ)∩𝔹_1^n lies 
in the interior of these (n-1)-dimensional simplices. This is because in this case the intersection of (Φ) and the interior of the (n-1)-dimensional simplex is either empty, or a non-singleton open convex subset of ℝ^n, 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-2)-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 (Φ) 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. Thus, at least n-r-1 coordinates of the extreme point have to be zero, so that  each extreme point is at most (r+1)-sparse.


Although Lemma <ref> is analogous to (<ref>), it is stronger in the sense that the statement bounds the sparsity of all the extreme points of the convex set (Φ)∩𝔹_1^n, not just the sparsest vectors in the (Φ), as is implied by (<ref>). Armed with Lemma <ref>, it turns out that for incidence matrices, these extreme points have a nice characterization in terms of the properties of the underlying graph. 


Let A∈ℝ^m × n be the incidence matrix of a simple connected graph 𝒢 that has at least one simple cycle, and let W_1 denote the set of normalized simple cycles of 𝒢, i.e.

    W_1  :={w(𝒞)/ w(𝒞)_1| 𝒞 is a simple cycle of 𝒢}.

Then, we have
((A)∩𝔹_1^n) ⊆ W_1.


Let z be an extreme point of (A)∩𝔹_1^n with support S. We necessarily have z_1=1. Suppose that 𝒢_S has m̅ vertices and k̅ connected components. Note that z_S∈(A_S)∩𝔹_1^|S| has only nonzero entries. 
We claim that z_S is an extreme point of (A_S)∩𝔹_1^|S|. For a proof by contradiction, suppose that z_S could be written as a convex combination of two distinct vectors in (A_S)∩𝔹_1^|S|.  In this case, one could pad those vectors with zeros at the coordinates in S^c to get two distinct vectors in (A)∩𝔹_1^n, whose convex combination would give z.  Since this would contradict the fact that z is an extreme point, we must conclude that z_S is an extreme point of (A_S)∩𝔹_1^|S|. 

Using the  fact that z_S is an extreme point of (A_S)∩𝔹_1^|S|, Lemma <ref>, and Remark <ref>, it follows that 

    |S|≤(A_S)+1 = m̅-k̅+1.

Combining (<ref>) with the rank-nullity theorem yields

    ((A_S)) = |S|-m̅ +k̅≤ 1.

This may be combined with 0≠ z_S∈(A_S) to conclude that ((A_S)) = 1; thus (A_S) is spanned by z_S. It now follows from Remark <ref> that z_S corresponds to the unique simple cycle in 𝒢_S. In addition, since z_S has no zero entries, the corresponding simple cycle includes every edge of 𝒢_S. It follows that z corresponds to a simple cycle in 𝒢, which combined with z_1=1 proves z ∈ W_1.


Next we show that Proposition <ref> provides a way to study the maximization problem (<ref>).

 Let A ∈ℝ^m× n be the incidence matrix of a simple, connected graph 𝒢, and let W_1 denote the set of normalized simple cycles of 𝒢 as in (<ref>). Let S⊆{1,…, n} be a nonempty index set. Then  

    max_η∈(A)∩𝔹^n_1η_S_1=   max_z∈ W_1z_S_1.



Since W_1 ⊂(A)∩𝔹^n_1, we obviously have

    max_η∈(A)∩𝔹^n_1η_S_1 ≥  max_z∈ W_1z_S_1.

For the converse inequality we argue as follows: Since Γ_S(·) _1 is a continuous convex function (thus also quasi-convex), and (A)∩𝔹_1^n is a compact convex set, the maximum in the left hand side of (<ref>) will be attained at an extreme point of (A)∩𝔹_1^n (see Proposition <ref>). That is,

    max_η∈(A)∩𝔹^n_1η_S_1 =  max_ν∈((A)∩𝔹^n_1)ν_S_1.

But ((A)∩𝔹_1^n) ⊆ W_1 by Proposition <ref>. Hence,

    max_ν∈((A)∩𝔹_1^n) ν_S_1 ≤  max_z∈ W_1z_S _1.

Combining this with (<ref>) we get the converse inequality, and hence the result.


Theorem <ref> 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 primarily exploit in the rest of the paper. 


Let us make a simple but important observation.
 Let 𝒢 and  W_1 be as in Theorem <ref>. Then, for any index set S and z∈ W_1, it holds that

    z_S _1 = |S∩(z)|/z_0.



For any simple cycle 𝒞, the entries of w(𝒞) are in the set {0,-1,1}. Hence, entries of any z∈ W_1 are from the set {0,1/z_0,-1/z_0}, from which the result follows. 






 §.§ Polynomial Time Guarantees for Sparse Recovery

An answer to the first question posed at the beginning of Section <ref> is given by Theorem <ref>.



Let A ∈ℝ^m× n be the incidence matrix of a simple, connected graph 𝒢 with girth g. Then, every s-sparse vector x̅∈ℝ^n  is the unique solution to

    min_Ax̅=Axx_1

if and only if s < g/2.


From  Lemma <ref> and Theorem <ref> it follows that the NUP of order s is satisfied if and only if

    max_|S|≤ s max_z∈ W_1z_S_1<1/2.

From Lemma <ref>, the maximum on the left of (<ref>) is equal to

    max_|S|≤ s max_z∈ W_1|S∩(z)|/z_0.

If s≥ g, then (<ref>) is equal to 1. If s < g, the maximum is attained at the smallest simple cycle when S picks edges only from this cycle, and the maximum is equal to s/g. Hence,

    max_|S|≤ s max_z∈ W_1z_S_1= min{s/g,1}.






The desired result now follows from (<ref>) and (<ref>).





As was mentioned in Remark <ref>, calculating the nullspace constant is NP-hard in general. However, there are algorithms that can calculate the girth of a graph exactly in 𝒪(mn) or sufficiently accurately for our purposes in 𝒪(m^2) (see <cit.>). Therefore, Theorem <ref> reveals that the nullspace constant can be calculated—hence the NUP can be verified—for graph incidence matrices in polynomial time. 




 



 §.§ Guarantees for Support-dependent Sparse Recovery


The sparse recovery result given by Theorem <ref> depends on the cardinality s of the support of the unknown signal. For a graph with small girth (e.g., g=3), this result establishes sparse recovery guarantees only for signals with low sparsity levels (specifically, s < g/2). It is natural, therefore, to ask the following question: Given a graph with relatively small girth, can we identify a class of signals with sparsity s ≥ g/2 that can be recovered? This leads us to the study of support-dependent sparse recovery, where we not only focus on the cardinality of the support of the unknown signal x̅, but also take the location of the support into account.
More precisely, we have the following result.


Let A ∈ℝ^m× n be the incidence matrix of a simple, connected graph 𝒢, let W_1 denote the set of normalized simple cycles of 𝒢 as in (<ref>), and let ∅≠ S⊆{1,…, n}. Then,  every vector x̅∈ℝ^n with (x̅)⊆ S is the unique solution to the optimization problem

    min_Ax̅=Axx_1

if and only if

    max_z∈ W_1|S∩(z)|/z_0 < 1/2.




From arguments in the proof of Lemma <ref>, we know that (<ref>) is equivalent to

    max_η∈(A)∩𝔹^n_1η_S_1 < 1/2,

which with Theorem <ref> and Lemma <ref> gives the result.











































In comparison to Theorem <ref>, Theorem <ref> provides a deeper insight into the vectors x̅ that can be recovered from the observations Ax̅ via ℓ_1-minimization. Specifically, any vector whose support within each simple cycle has size strictly less than half the size of that cycle, can be successfully recovered.

As an example consider the graph in Fig. 1, which has girth g=4. Thus, it follows from Theorem <ref> that any 1-sparse signal can be recovered. However, in reality, some signals that are supported on more than one edge can also be recovered. For instance, Theorem <ref> guarantees that a signal x̅ supported on edges {2, 7} or { 4, 6, 8} can be recovered as the unique solution to the ℓ_1 problem (<ref>) since for each of the three simple cycles, its intersection with the support of the unknown vector x̅ is less than  half of the length of the simple cycle. This reveals that different sparsity patterns of the same sparsity level can have different recovery performances.




To use Theorem <ref> as a way of providing a support-dependent recovery guarantee, one needs to compute the intersection of the support of x̅ with all simple cycles in the graph. A number of algorithms with a polynomial time complexity bound for cycle enumeration are known <cit.>. 







 §.§ Using Measurement Sparsity to Aid Recovery


When there is additional information about the support of the unknown signal, Theorem <ref> gives a necessary and sufficient condition for exact recovery. In practice, this information is usually missing. However, the special structure of the incidence matrix and its connection to the graph can help us circumvent this difficulty. Notice that the columns of any incidence matrix are always 2-sparse, which means that the measurement y := Ax̅ will be 2s-sparse for any s-sparse signal x̅. 
Therefore, one can seek to obtain a superset of (x̅) by observing (y), i.e. the vertices with nonzero measurements. Typically, this observation reduces the size of the problem, and gives rise to Algorithm <ref>.































There are cases where Algorithm <ref> may fail. For instance, when the unknown nonzero signal x̅ is in the nullspace of one of the rows of A, say a_k, and (a_k)∩(x̅)≠∅ (i.e. when the non-zero values of the signal x̅ cancel each other at a vertex k), Algorithm <ref> would simply ignore the corresponding vertex, and hence, the edges connected to it. This leads to a wrong subgraph 𝒢_S and possibly an incorrect outcome x̂. Fortunately,  this case happens with zero probability when the signal has random support and random values.





Let A ∈ℝ^m× n be the incidence matrix of a simple, connected graph 𝒢. 
Given  a random signal x̅, let y:=Ax̅  and 𝒢_S be the subgraph associated with  y in Algorithm <ref>.
Then, Algorithm <ref> will almost surely recover the signal x̅ if and only if (x̅) picks strictly less than half of the edges from each simple cycle of 𝒢_S.



The proof of Corollary <ref> follows from Theorem <ref> and the fact that x̅ is assumed to be randomly generated.




















In comparison to ℓ_1-minimization on the original graph, Algorithm <ref> may have improved support-dependent recovery performance because the formation of the subgraph may eliminate  cycles; this is especially true for large-scale networks. For concreteness, let us  give a simple example.

Consider the graph depicted in Fig. <ref>. Let x̅ be a random signal that is supported on the edges {3,4,5,6,7,8,10}, so that (with probability one) there are nonzero measurements on nodes {1,3,4,5,6,7,8,9}. Then, x cannot be recovered using the incidence matrix of the original graph. However, the subgraph 𝒢_S is acyclic, as shown in Fig. <ref>, which allows exact recovery via Algorithm <ref>.






















§ SIMULATIONS








In this section we provide numerical simulation results on the recovery performance associated with incidence matrices. In all experiments, the signal x̅ has random support with each nonzero entry drawn i.i.d. from the standard normal distribution. We use the CVX software package <cit.> to solve the optimization problems. A vector is declared to be recovered if the 2-norm error is less than or equal to 10^-5.

Fig. <ref> shows the probability of exact recovery of signals via ℓ_1-relaxation over a sequence of graphs containing two cycles (see Fig. <ref>). Each graph has a cycle of length 3 and a larger one of varying lengths 3, 5, 7, 9, and 11, respectively.  For each sparsity level, 1000 trials were performed. According to Theorem <ref>, for all graphs we can recover 1-sparse signals since the girth is 3 for each graph in the sequence. When the sparsity level is increased, we expect that the probability of exact recovery will increase for graphs with larger cycles because it becomes less likely that the support of the random signal will consist of more than half of the edges for one of the simple cycles in the graph. Note that this agrees with our observation in Fig. <ref>.














































We now evaluate the performance of Algorithm 1 against the ℓ_1-minimization method in (<ref>) on two graphs with 20 nodes (see Fig. <ref>). The first graph, 𝒢_B, is a simple cycle connecting node 1 to node 20 in order (blue edges in Fig. <ref>). The second graph, 𝒢_BR, consists of both blue and red edges. The red edges connect each node to its third neighbor, i.e., (1,4), (2,5) ⋯ (17,20)⋯(20,3). Fig. <ref> and Fig. <ref> show the performance of both algorithms on 𝒢_B and 𝒢_BR respectively. For each sparsity level, the experiments are repeated 1000 times to compute recovery probabilities. For 𝒢_B, Algorithm 1 outperforms ℓ_1-minimization since the reduced graph in Algorithm 1 will be acyclic in some cases. For 𝒢_BR, Algorithm 1 will eliminate small cycles when forming the subgraph and lead to higher recovery probability for fixed s due to a larger girth. 










§ CONCLUSION

In this paper we studied sparse recovery for the class of graph incidence matrices. For  such matrices we provided a characterization of the NUP in terms of the topological properties of the underlying graph. This characterization allows one to verify sparse recovery guarantees in polynomial time for the class of incidence matrices. Moreover, we showed that support-dependent recovery performance can also be analyzed in terms of the simple cycles of the graph. Finally, by exploiting the structure of incidence matrices and sparsity of the measurements, we proposed an efficient algorithm for recovery and evaluated its performance numerically.



















-3cm   
                                  
                                  
                                  
                                  
                                  



ieeetr

















