# Linear Program Relaxation of Sparse Nonnegative Recovery in Compressive Sensing Microarrays

Authors: Linxia Qin; Naihua Xiu; Lingchen Kong; Yu Li
Journal: Computational and Mathematical Methods in Medicine
 (2012)

---

## Abstract

Compressive sensing microarrays (CSM) are DNA-based sensors that operate using group testing and compressive sensing principles. Mathematically, one can cast the CSM as sparse nonnegative recovery (SNR) which is to find the sparsest solutions subjected to an underdetermined system of linear equations and nonnegative restriction. In this paper, we discuss thel1 relaxation of the SNR. By defining nonnegative restricted isometry/orthogonality constants, we give a nonnegative restricted property condition which guarantees that the SNR and the l1 relaxation share the common unique solution. Besides, we show that any solution to the SNR must be one of the extreme points of the underlying feasible set.


---

## Body

## 1. Introduction

Nowadays, with the rapid development of molecular biology techniques, scientists use compressive sensing microarrays to collect the gene expression changes of patients suffer from specific diseases and test a lot of different drugs on cells genetically to look for medicine being able to change the abnormal gene expression [1, 2]. A DNA microarray is a collection of microscopic DNA spots attached to a solid surface. Each DNA spot contains a string of specific DNA sequences, known as probes. These can be a short section of a gene or other DNA element that are used to hybridize an organism's genetic sample under high-stringency conditions. Probe-target hybridization is usually detected and quantified by detection of chemiluminescence-labeled targets to infer the genetic makeup in the test sample.Although the number of DNA sequences is extremely large, not all agents are expected to be present in a significant concentration at a given time and location. In traditional microarrays, this results in many inactive probes during sensing. On the other hand, we are often interested in only a small quantity of certain harmful biological agents. Therefore, it is important to not just detect the presence of agents in a sample but also estimate the concentrations with which they are present.Assume that there arem spots and n labeled targets, and we have far fewer spots than target agents such that m≪n. Mathematically, one can represent the DNA concentration of each organism as an element in a vector x∈ℝn and the measurements as b∈ℝm. For 1≤i≤m and 1≤j≤n, the probe at spot i hybridizes to target j with probability aij. The target j occurs in the tested DNA sample with concentration xj, which is clearly nonnegative. Denoting by A:=(aij)m×n, the process of DNA microarrays leads to the sparse nonnegative recovery (SNR) which is to find the sparsest solutions subjected to an underdetermined system of linear equations and nonnegative constraints, with the mathematical model as follows:
(P0)min∥x∥0,s.t.Ax=b,x≥0,
where the variable vector x∈ℝn, ∥x∥0 denotes the number of the nonzero entries of x, A∈ℝm×n is the measurement matrix with full row rank, m≪n, and b∈ℝm.SNR can be regarded as a special case of the sparse recovery, which is related to programmin{∥x∥0∣Ax=b}. This program has sparked the significant concern and rapid development in recent years [3–5] owing to its wide applications. However, with the nonnegativity prior information about the object to be recovered in various applications such as CSM, solutions on (P0) tend to be closer to the actual situations and lead to substantial improvements in the image reconstruction. Moreover, with the nonnegative constraints, the feasible set becomes a polyhedral set instead of an affine subspace. This will bring us essential hardness in projecting on the feasible set. Thus, (P0) is more likely difficult to solve. Therefore, SNR deserves specific study.Problem(P0) has been shown to be NP-hard [6, 7] in general from the perspective of computational complexity. One popular approach is to reconstruct the vector via the l1 relaxation, which refers to
(P1)min∥x∥1,s.t.Ax=b,x≥0.
Since (P1) is a standard linear program, it is easy to solve. An important issue is how to guarantee the equivalence of (P0) and (P1) in the sense that they have the same unique k-sparse solution under some conditions. Here, we call a vector x  k-sparse if the number of its nonzero entries is no more than k. There has been some increasing interest and activity in this area; see, for example, [8–14]. Donoho and Tanner [9] firstly proposed that (P0) and (P1) share the common k-sparse unique solution if the polytope AT is outwardly k-neighborly, where T is the standard simplex in ℝn. Zhang [13] proved that (P0) and (P1)  share the common k-sparse unique solution if the null space of A is strictly half k-balance. Juditsky et al. [11] developed several different necessary and sufficient conditions for the (P0)-(P1) equivalence in the case of general type sign restrictions, including the nonnegative constraints as its special case. When the feasible set of (P0) is a singleton, the unknown can be recovered by optimizing any objective function over this constraint set, and  (P0) and (P1)  definitely get the same unique solution. In this case, Bruckstein et al. [8] got the uniqueness of the feasible solution under a sufficient condition that A has a rowspan intersecting the positive orthant. Furthermore, Wang et al. [14] proved that the above sufficient condition is also necessary to the uniqueness of the feasible solution. Donoho and Tanner [10] proved that the underlying feasible set is a singleton if and only if the polytope Aℝ+n and ℝ+n have the same number of k-faces. Khajehnejad et al. [12] gave another equivalent condition of the uniqueness property by characterizing the support size of vectors in the null space of A.For thel1 relaxation of sparse recovery, one of the most significant conditions is the restricted isometry property (RIP), named by Candès and Tao [15] with the groundbreaking work of Donoho et al. [16, 17]. However, to the best of our knowledge, the nonnegative case of RIP has not been investigated. This paper will deal with this issue. We begin with investigating the solution property of SNR and show that any solution to the SNR must be one extreme point of its feasible set in Section 2. We prove in Section 3 the nonemptiness and boundedness of the solution set of (P1) and show that any solution of (P1) could be stated as the convex combination of its optimal extreme points. In Section 4, by defining the nonnegative restricted isometry/orthogonality constants, we derive a sufficient condition for exact recovery of the sparsest nonnegative image/signal via the linear program relaxation.Now we give some notations used in the text. We usesol(·) and v(·) to denote the solution set and optimal value of problem (·). The ei∈ℝn would be the vector with only the ith entry 1 and the rest all 0. el∈ℝl is the vector with each entry equal to 1; we also use e to demonstrate that en∈ℝn for short. The ai∈ℝm for i=1,…,n denote the column vectors of the matrix A and AI=(ai)i∈I⊂{1,…,n}. For any x∈ℝn, xi is the ith component and I(x) is the support set of x; that is, I(x)={i∣xi≠0,i=1,…,n}. For any subset T⊂{1,…,n}, Tc denotes the complement set of T out of {1,…,n}.


## 2. Solution Property

Throughout the paper we assume that(1)𝒮:={x∈ℝn∣Ax=b,x≥0}≠∅.
Apparently, 𝒮 is a polyhedral set in ℝn. According to the representation theorem, any x∈𝒮 could be represented as follows:
(2)x=∑i=1t‍λix-(i)+∑j=1q‍μjd(j),
where ∑i=1t‍λi=1, λi≥0, i=1,…,t, and {x-(i)∈ℝn∣i=1,2,…,t} are the extreme point set of 𝒮; μj≥0, j=1,…,q, and {d(j)∈ℝn∣j=1,2,…,q} are the extreme direction set of 𝒮. Apparently, Ax-(i)=b, i=1,…,t; Ad(j)=0,  d(j)≥0, j=1,…,q.Define subsets ofℝn as follows:
(3)S0=sub{0},S1={⋃i=1n‍sub{ei}}∖S0,S2={⋃i1,i2=1n‍sub{ei1,ei2}}∖⋃j=01‍Sj,⋮Sr={⋃i1,…,ir=1n‍sub{ei1,…,eir}}∖⋃j=0r-1‍Sj,⋮Sn={sub{e1,…,en}}∖⋃j=0n-1‍Sj,
where sub{ei1,…,eik} denotes the subspace spanned by the vectors ei1,…,eik, k=1,…,n. Clearly, {S1,S2,…,Sn} forms a partition of ℝn; that is, ⋃j=1n‍Sj=ℝn and Si⋂‍Sj=∅, i≠j. Moreover, ∥x∥0=r for any x∈Sr. Along with the nonemptiness of 𝒮, it is easy to see that 𝒮 must intersect one of these sets, hence v(P0)=min{r∈ℝ∣𝒮⋂‍Sr≠∅} and sol(P0)≠∅. Furthermore, we have the following result for the optimal value of  (P0).Lemma 1.
Assume thatv(P0)=k, one must have k≤m.Proof.
Suppose that the conclusion is not true; that is, there isx*∈sol(P0) with ∥x*∥0=k>m. Without loss of generality, let xi*>0, i=1,…,k. We get
(4)x1*a1+⋯+xk*ak=b.
Meanwhile, rank(A)=m<k. Thus, {ai∈ℝm∣i=1,…,k} must be linearly dependent; that is, there exist d1,…,dk, not all zero, such that
(5)d1a1+⋯+dkak=0.
Assume that d1>0. By denoting d=(d1,…,dk,0,…,0)T∈ℝn, we get Ad=0. Taking δ=min{xi*/di∣di>0,i=1,…,k}, it holds that
(6)A(x*-δd)=Ax*-δAd=b,x*-δd≥0,∥x*-δd∥0≤k-1.
This is a contradiction with x*∈sol(P0). We complete the proof.To characterize property of the solution setsol(P0), we need the next lemma. In particular, this brand new result will play a key role in proposing the sufficient condition of the uniqueness of sol(P0) in Section 4.Lemma 2.
Any two distinct solutions of(P0) must have different support sets.Proof.
Assume for contradiction thatx* and x~ are two different solutions of (P0), x*≠x~. If I(x*)=I(x~), we have xi*>0, x~i>0, for all i∈I(x*). Set λ=min{mini∈I(x*){xi*/x~i},mini∈I(x*){x~i/xi*}}. Since x*≠x~, it must hold λ<1. When λ=xi0*/x~i0, take
(7)x^=11-λx*-λ1-λx~.
It is easy to see that
(8)x^i=11-λxi*-λ1-λx~i∈{{0},i=i0,ℝ+,i∈I(x*)∖{i0}.
Thus, we have Ax^=b, x^≥0 and ∥x^∥0≤∥x*∥0-1. This is a contradiction with the optimality of x*. When λ=x~j0/xj0*, just taking x^=(1/(1-λ))x~-(λ/(1-λ))x* instead, we get the contradiction by a similar way. The proof is completed.Now we are in a position to give the main theorem in this section.Theorem 3.
Any solution of(P0) must be one of the extreme points of 𝒮.Proof.
Given any solutionx*∈sol(P0) with representation
(9)x*=∑i=1t‍λi*x-(i)+∑j=1q‍μj*d(j),
where ∑i=1t‍λi*=1, λi*≥0, x-(i)≥0, Ax-(i)=b, for all i=1,…,t; μj*≥0, d(j)≥0, Ad(j)=0, for all j=1,…,q. We only need to prove that
(10)∑i=1p‍λi*=1,λi*∈{0,1},i=1,…,t,μj*=0,j=1,…,q,
in (9). To this end, we have the following three steps.
Firstly, we claim that in (9),
(11)I(x-(i))=I(x*),i∈{i∣λi*>0,i=1,…,t},I(d(j))⊂I(x*),j∈{j∣μj*>0,j=1,…,q}.
According to the fact that x-(i)≥0, i=1,…,t, and μj*≥0, d(j)≥0, j=1,…,q, one has for any l∈I(x-(i)), i∈{i∣λi*>0,i=1,2,…,t},
(12)xl*=∑i=1t‍λi*x-l(i)+∑j=1q‍μj*dl(j)>0,
which means that l∈I(x*). This implies I(x-(i))⊂I(x*). Similarly, we get I(d(j))⊂I(x*). On the contrary, from the optimality of x* and (9), we know that I(x*)⊂I(x-(i)).
Secondly, we will show thatμj*=0, j=1,…,q. If this is not true, there is an index j0 such that μj0*>0, then μj0*d(j0) has at least one positive component. Denote d=∑j=1q‍μj*d(j), so Ad=0 and {dl>0∣l=1,…,n}≠∅. Noting that x-(i)≥0, (11) implies the fact that I(∑i=1t‍λi*x-(i))=I(x*),I(d)⊂I(x*). Take δ=min{(∑i=1t‍λi*x-(i))l/dl∣dl>0,l=1,…,n}, and
(13)x~=∑i=1t‍λi*x-(i)-δd.
Without loss of generality, set δ=(∑i=1t‍λi*x-(i))l0/dl0. It is easy to verify that
(14)x~j=(∑i=1t‍λi*x-(i))j-δdj∈{{0},j=l0ℝ+,i∈I(x*)∖{l0},
hence
(15)Ax~=b,x~≥0,∥x~∥0≤∥x*∥0-1,
which is a contradiction with the optimality of x*.
Thirdly, we will prove that∑i=1t‍λi*=1, λi*∈{0,1}, i=1,…,t. Suppose that there exist λ1*>0, λ2*>0, and λ1*+λ2*=1 and two different extreme points of 𝒮, say x-(1),x-(2), such that
(16)x*=λ1*x-(1)+λ2*x-(2).
Based on (11), we have I(x-(1))=I(x-(2))=I(x*), hence x-(1)∈sol(P0), x-(2)∈sol(P0). Nevertheless, by Lemma 2, this is impossible. Hence, we show that
(17)x*∈{x-(1),x-(2),…,x-(t)}.
We complete the argument.Theorem3 tells us that each solution of  (P0)  lies in the extreme point set of 𝒮. Here is a concrete example.Example 4.
LetA=(11-3-102),b=(3-2). Obviously, the solution set and optimal value of (P0) are
(18)sol(P0)={(2,1,0)},v(P0)=2,
respectively. In this case, (2,1,0) is the only extreme point of 𝒮. While the solution set and optimal value of (P):=min{∥x∥0∣Ax=b} are
(19)sol(P)={(0,0,-1)},v(P)=1,
respectively.At the end of this section, we consider thelp(0<p<1) relaxation of (P0)(Pp)min∥x∥pp=∑i=1n‍xip,s.t.Ax=b,x≥0.
Clearly, (Pp) is a concave relaxation of  (P0). For the program (Pp), Ge et al. [7] derived the useful result as the following.Lemma 5.
The set of all extreme points of𝒮 is exactly the set of all local minimizers to (Pp).This lemma implies that any global solution oflp relaxation must be one of its extreme points. From Theorem 3 and Lemma 5, we immediately draw a new proposition.Proposition 6.
For anyp∈(0,1), there exists an extreme point of 𝒮 that is both an exact solution of (P0) and a local minimizer of (Pp).This is different from the result of Fung and Mangasarian in [18], where they showed that for sufficiently small p-∈(0,1), there exists an extreme point x- of the polyhedral set 𝒯, obtained by lifting the set 𝒮, such that x- is an exact solution of (P0) and a global solution of the lp- relaxation.


## 3. Linear Program Relaxation

Consider the linear program relaxation(P1). Since the linear objective function 〈e,x〉 is bounded below over the feasible set, based on the Frank-Wolfe theorem, the minimum of  (P1) is attainable. Among all the extreme points of 𝒮, {x-(i)∈Rn∣i=1,…,t}, we call x-(i) an optimal extreme point if it also meets 〈e,x-(i)〉=v(P1).Proposition 7.
Anyx*∈sol(P1) could be stated as the convex combination of optimal extreme points of (P1). Hence,sol(P1) is bounded.Proof.
Given anyx*∈sol(P0) with representation (9). If there is i0∈{1,…,t} such that x-(i0) is not an optimal extreme point of  (P1) and λi0*>0, we have 〈e,x-(i0)〉>v(P1), hence
(20)v(P1)=〈e,x*〉=∑i=1t‍λi*〈e,x-(i)〉+∑j=1q‍μj*〈e,d(j)〉≥∑i=1t‍λi*〈e,x-(i)〉>∑i=1t‍λi*v(P1)=v(P1),
which is a contradiction.
Similarly, if there isj0∈{1,…,q} such that μj0*>0, we have μj0*〈e,d(j0)〉>0, hence
(21)v(P1)=〈e,x*〉=∑i=1t‍λi*〈e,x-(i)〉+∑j=1q‍μj*〈e,d(j)〉>∑i=1t‍λi*〈e,x-(i)〉≥∑i=1t‍λi*v(P1)=v(P1),
which is a contradiction. This completes the proof.From the above proposition, we know that linear program(P1) has at least one optimal extreme point. Thus, we could use simplex method or interior point method to solve (P1).


## 4. Nonnegative Restricted Property

In the framework ofl1 relaxation, a significant problem is how to guarantee the exact recovery of sparse image/signal via the l1 relaxation. One of the most important qualifications is the restricted isometry property; see [15]. Recall that the k-restricted isometry constants (RIC) δk is the smallest scalar satisfying
(22)(1-δk)∥x∥22≤∥Ax∥22≤(1+δk)∥x∥22,∀∥x∥0≤k.
Similarly, the k,k′-restricted orthogonality constants (ROC) θk,k′ for k+k′≤n is defined as the smallest scalar satisfying
(23)|〈Ax,Ay〉|≤θk,k′∥x∥2∥y∥2,∀∥x∥0≤k;∀∥y∥0≤k′,
where x and y have disjoint support sets. The RIC δk and ROC θk,k′ measure how close each submatrix of A with certain cardinality is behaving like an orthonormal system. Under some restricted isometry property, one can get the sparse recovery via its l1 relaxation. Nevertheless, for the nonnegative case, the sparse recovery may maintain new characterizations. Above all, we define NRIC and NROC.Definition 8.
LetA∈ℝm×n. We define the nonnegative k-restricted isometry constants (NRIC) δk+ as the smallest number satisfying
(24)(1-δk+)∥x∥22≤∥Ax∥22≤(1+δk+)∥x∥22,∀x≥0,∥x∥0≤k.
Similarly, we define the nonnegative k,k′-restricted orthogonality constants (NROC) θk,k′+ for k+k′≤n as the smallest number satisfying
(25)|〈Ax,Ay〉|≤θk,k′+∥x∥2∥y∥2,∀x≥0,∥x∥0≤k,∀y≥0,∥y∥0≤k′,
with I(x) and I(y) being disjoint sets.Clearly,(26)δk+≤δk,θk,k′+≤θk,k′.
Moreover, the numbers δk+ and θk,k′+ are nondecreasing in k,k′.By employing the projections of vectors in the null space ofA to ℝ+n, we now provide a sufficient condition to determine a solution of (P0).Theorem 9.
Suppose thatk≥1 is such that δk++θk,k-1+<1 and x*∈𝒮 with ∥x*∥0=k. Then, x* is a solution of (P0).Proof.
We complete the proof by contradiction. If this is not true, there existsx- such that Ax-=b, x-≥0,∥x-∥0≤k-1. Set h=x*-x-. Clearly, Ah=0. Take h=h+-h- with h+ and h- being the projections of h and -h to ℝ+n, respectively. We have h+≥0, h-≥0, 〈h+,h-〉=0. In particular,
(27)(h+)i={(xi*-x-i)+,i∈I(x*),0,else,(h-)i={(xi*-x-i)-,i∈I(x-),0,else.
Therefore,
(28)1≤∥h∥0≤∥x*∥0+∥x-∥0≤2k-1,1≤∥h+∥0≤k,0≤∥h-∥0≤k-1.
Thus, we get
(29)0=∥Ah∥22=∥Ah+-Ah-∥22=∥Ah+∥22+∥Ah-∥22-2〈Ah+,Ah-〉≥(1-δk+)∥h+∥22+(1-δk-1+)∥h-∥22-θk,k-1+(∥h+∥22+∥h-∥22)≥(1-δk+-θk,k-1+)∥h+∥22+(1-δk-1+-θk,k-1+)∥h-∥22>0,
in which the first inequality is due to (24), (25), and the fact that 2ab≤a2+b2, and the last inequality is because of the assumption of δk++θk,k-1+<1 and the monotonicity of δk+ in k. This is a contradiction. Therefore, x*∈sol(P0).With the special result that any two solutions of(P0) have different support sets, we next derive a sufficient condition on the uniqueness of solution to (P0).Theorem 10.
Suppose thatk≥1 is such that δk++θk,k+<1 and x*∈𝒮 with ∥x*∥0=k. Then, x* is the unique solution of (P0).Proof.
Sinceδk++θk,k+<1 implies δk++θk,k-1+<1, we know that x*∈sol(P0). Now we just need to verify that x* is the unique solution of (P0). Assume that this is not true; that is, there is another solution x-≠x*. According to Lemma 2, it must hold I(x-)≠I(x*). Take h=x*-x-. By the argument similar to that in the proof of Theorem 9, we get
(30)2≤∥h∥0≤∥x*∥0+∥x-∥0≤2k,1≤∥h+∥0≤k,1≤∥h-∥0≤k,
and the contradiction. We conclude the proof.Now we are ready to give the main result of this paper, which is called the nonnegative restricted property.Theorem 11.
Assume thatk≥1 is such that
(31)δ2k++(2+1)θk,2k+<1,
and x*∈𝒮 with ∥x*∥0=k. Then x* is exactly the common unique minimizer of (P0) and  (P1).Proof.
Since (31) implies δk++θk,k+<1, sol(P0)={x*} by Theorem 10.
Suppose thatx- is a solution of (P1). Take h=x--x*. To get sol(P1)={x*}, it suffices to verify that h=0. The proof includes three steps, the first two steps are parallel to that in [19], in the third step, we utilize the technique of projecting the null space of A on ℝ+n; for details, see (42) and the argument around it.
Firstly, we introduce a partition of{1,…,n}. Let T0 be the support set of x*, T1 the index set including the first k large components of x- in T0c, T2 the index set including the next k large components of x- in T0c∖T1, and so on. Thus,
(32)|Tj|=k,j=0,1,…,[nk]-1,|Tj|≤k,j=[nk].
Moreover, for any j=0,1,…,[n/k], we define
(33)(hTj)i={hi,i∈Tj,0,else,
which is exactly that for any j=1,…,[n/k](34)(hTj)i={x-i-xi*,i∈T0,x-i,i∈Tj,0,else.
Therefore, Ah=0,h=∑j=0[n/k]‍hTj, and
(35)hTj≥0,j=1,…,[nk],∥hTj∥0≤k,j=0,1,…,[nk].
Next, we show that∥h(T0∪T1)c∥2 is bounded by ∥hT0∥1. Note that for each j≥2,
(36)∥hTj∥2≤k∥hTj∥∞≤1k∥hTj-1∥1,
where the second inequality is because of the monotonicity of hi on T0c, and
(37)∑j=2[n/k]‍∥hTj∥2≤1k∑j=1[n/k]-1‍∥hTj∥1≤1k∥hT0c∥1.
This gives
(38)∥h(T0∪T1)c∥2=∥∑j=2[n/k]‍hTj∥2≤∑j=2[n/k]‍∥hTj∥2≤1k∥hT0c∥1.
In fact,
(39)∥xT0*∥1=∥x*∥1≥∥x-∥1=∥x*+h∥1=∥xT0*+hT0∥1+∥xT0c*+hT0c∥1≥∥xT0*∥1-∥hT0∥1+∥hT0c∥1-∥xT0c*∥1=∥xT0*∥1-∥hT0∥1+∥hT0c∥1,
which implies
(40)∥hT0c∥1≤∥hT0∥1.
By applying (38) and (40), we have
(41)∥h(T0∪T1)c∥2≤1k∥hT0c∥1≤1k∥hT0∥1.
Finally, we show that∥hT0∪T1∥2=0. By utilizing the projection h=h+-h-, where h+ and h- are projections of h and -h on ℝ+n, we have h(T0∪T1)=h(T0∪T1)+-h(T0∪T1)-. Moreover,
(42)(h(T0∪T1)+)i={(x-i-xi*)+,i∈T0,x-i,i∈T1,0,else,(h(T0∪T1)-)i={(x-i-xi*)-,i∈T0,0,i∈T1,0,else.
It is easy to see
(43)∥h(T0∪T1)+∥0≤2k,∥h(T0∪T1)-∥0≤k.
From Ah=0, we compute
(44)∥Ah(T0∪T1)∥22=〈Ah(T0∪T1),Ah-Ah(T0∪T1)c〉=-∑j=2[n/k]‍〈Ah(T0∪T1),AhTj〉.
On one hand, based on the definition of NROC, (35), and (43), for j≥2,
(45)-〈Ah(T0∪T1),AhTj〉=-〈Ah(T0∪T1)+,AhTj〉+〈Ah(T0∪T1)-,AhTj〉≤|〈Ah(T0∪T1)+,AhTj〉|+|〈Ah(T0∪T1)-,AhTj〉|≤θk,2k+∥h(T0∪T1)+∥2·∥hTj∥2+θk,k+∥h(T0∪T1)-∥2·∥hTj∥2≤θk,2k+∥hTj∥2·(∥h(T0∪T1)+∥2+∥h(T0∪T1)-∥2)≤2θk,2k+∥hTj∥2·∥h(T0∪T1)∥2,
where the last inequality is by the fact that (a+b)2≤2(a2+b2). On the other hand, together with the definition of NRIC and (43), one has
(46)∥Ah(T0∪T1)∥22=∥Ah(T0∪T1)+-Ah(T0∪T1)-∥22=∥Ah(T0∪T1)+∥22+∥Ah(T0∪T1)-∥22-2〈Ah(T0∪T1)+,Ah(T0∪T1)-〉≥(1-δ2k+)∥h(T0∪T1)+∥22+(1-δk+)∥h(T0∪T1)-∥22-2θk,2k+∥h(T0∪T1)+∥2·∥h(T0∪T1)-∥2≥(1-δ2k+)∥h(T0∪T1)+∥22+(1-δk+)∥h(T0∪T1)-∥22-θk,2k+(∥h(T0∪T1)+∥22+∥h(T0∪T1)-∥22)=(1-δ2k+-θk,2k+)∥h(T0∪T1)+∥22+(1-δk+-θk,2k+)∥h(T0∪T1)-∥22≥(1-δ2k+-θk,2k+)∥h(T0∪T1)∥22.
Therefore, we compute
(47)(1-δ2k+-θk,2k+)∥h(T0∪T1)∥22≤2θk,2k+∥h(T0∪T1)∥2·∑j=2[n/k]‍∥hTj∥2(by(44),(45),and(46))≤2θk,2k+∥h(T0∪T1)∥2·1k∥hT0c∥1(by(37))≤2θk,2k+∥h(T0∪T1)∥2·1k∥hT0∥1(by(40))≤2θk,2k+∥h(T0∪T1)∥2·∥hT0∥2≤2θk,2k+∥h(T0∪T1)∥22,
where the forth inequality is from the fact that ∥hT0∥12≤k∥hT0∥22. Then the assumption δ2k++(2+1)θk,2k+<1 forces
(48)∥h(T0∪T1)∥22=0.
Thus,
(49)h(T0∪T1)=0.
Therefore, we get h(T0∪T1)c=0 by (41), hence ∥h∥=0. This is exactly what we want. We complete the proof.


## 5. Conclusion

In this paper, we have derived a nonnegative restricted property condition, which ensures the exact recovery of sparse nonnegative image/signal via the linear program relaxation. Since the NRIC and NROC are defined inℝ+n, there may be more types of measurement matrices satisfying the nonnegative restricted property than that in the case of RIP, regardless of random matrices or deterministic matrices. As a byproduct of the main result, we have investigated the solution property of the sparse nonnegative recovery and shown that any solution of (P0) must be one of the extreme points of its feasible set. However, it is not clear whether a given extreme point of the feasible set is a solution to (P0). This can serve as a target for future work.



---

*Source: 646045-2012-11-01.xml*