# On the Null Space Property oflq-Minimization for 0<q≤1 in Compressed Sensing

Authors: Yi Gao; Jigen Peng; Shigang Yue; Yuan Zhao
Journal: Journal of Function Spaces
 (2015)

---

## Abstract

The paper discusses the relationship between the null space property (NSP) and thelq-minimization in compressed sensing.
Several versions of the null space property, that is, the lq stable NSP, the lq robust NSP, and the lq,p robust NSP
for 0<p≤q<1 based on the standard lq NSP, are proposed, and their equivalent forms are derived.
Consequently, reconstruction results for the lq-minimization can be derived easily under the NSP condition and its equivalent form.
Finally, the lq NSP is extended to the lq-synthesis modeling and the mixed l2/lq-minimization,
which deals with the dictionary-based sparse signals and the block sparse signals, respectively.


---

## Body

## 1. Introduction

Compressed sensing has been drawing extensive and hot attention as soon as it was proposed since 2006 [1–4]. It is known as a new revolution in signal processing because it can realize sampling and compression of signal at the same time. Its fundamental idea is to recover a high-dimensional signal from remarkably small number of measurements using the sparsity of signals. N-dimensional real-world signal is called sparse if the number of its nonzero coefficients under some representation is absolutely smaller than the signal length N. Suppose that x0 denotes the number of nonzero representation coefficients of the signal x; if x0≤s, then we say the signal x is s-sparse. Here, we call tentatively x0l0 norm (in fact, it is not a norm, because it does not satisfy the positive homogeneity of norm obviously). Using Σs denotes the set of all s-sparse signals: Σs={x∈RN:x0≤s}. Suppose the observed data y∈Rn; we will recover the signal x∈RN via a linear system (1)y=Ax,where A is an n×N(n<N) real matrix, known as measurement matrix. Generally speaking, when n<N, the underdetermined function y=Ax has infinitely many solutions. In other words, without additional information, it is impossible to recover the signal under this condition. However, compressed sensing focuses on the sparsest solution, and its mathematical modeling is as follows:(2)min⁡x∈RNx0s.t.y=Ax.We call the minimization (2) l0 modeling. Unfortunately, the l0-minimization (2) is a nonconvex and NP-hard optimization problem [5]. To conquer the hardness, one seeks another tractable mathematical modeling to replace the l0-minimization. This is called lq(q>0) modeling. Consider(3)min⁡x∈RNxqs.t.y=Ax,where (4)xq=∑i=1N‍xiq1/q,0<q<∞;max⁡i=1,…,Nxi,q=∞.For 1≤q≤∞, xq is a norm, while for 0<q<1, it is a quasinorm because it does not satisfy the triangle inequality, and it only satisfies the q-triangle inequality:(5)x+yqq≤xqq+yqq,x,y∈RN.It is natural that the l2 modeling is to be considered:(6)min⁡x∈RNx2s.t.y=Ax.To one’s disappointment, the l2 modeling is unable to exactly recover the sparse signals, even 1-sparse vectors. For example, supposing measurement matrix such as (7)A=100-1010-1001-1,we will recover the signal x from the measurement vector y=Ax=[1,0,0]T. Obviously, the solutions of this function are η=[1+t,t,t,t]T, t∈R. Let f(t)=(1+t)2+3t2; then min⁡t∈Rf(t)=f(-1/4)=3/4<1. But η=[3/4,-1/4,-1/4,-1/4]T is not sparse. In fact, [1,0,0,0]T is the sparsest solution of the above function. Moreover, for any q>1, although the lq modeling is also a convex optimization problem, it cannot guarantee the sparsest solution; that is, the lq modeling for q>1 is unable to exactly recover the sparse signals. Here, sparsity plays a key role in such recovery of signal. The problem is which q we can select to get the sparsest solution exactly.Candès et al. gave the followingl1 modeling [2, 3, 6–8]:(8)min⁡x∈RNx1s.t.y=Ax.The l1-minimization (8) is a convex optimization problem and can be transformed into a linear programming problem to be solved tractably. A natural question is whether the solutions of (8) are equivalent to those of (2), or what kind of measurement matrices can be constructed to guarantee the equivalence of the solutions of the two problems. Candès and Tao [2] proposed the Restricted Isometry Property (RIP), which is a milestone work in sparse information processing. We say that a matrix A satisfies the Restricted Isometry Property of order s, if there exists a constant δs∈[0,1), for any x∈Σs, such that(9)(1-δs)x22≤Ax22≤(1+δs)x22.We call the smallest constant δs satisfying the above inequality the Restricted Isometry Constant (RIC). Candès and Tao showed, for instance, that any s-sparse vector is exactly recovered as soon as the measurement matrix A satisfies the RIP with δ2s≤0.4142 [9], and the solution of (8) is equivalent to that of (2). Later, the RIC has been improved; for example, δ2s≤0.4531 by Foucart and Lai [10], δ2s≤0.4721 by Cai et al. [11], δ2s≤0.4931 by Mo and Li [12], and especially δ2s≤0.5746 by Zhou et al. [13].We see that thel1 modeling is seemingly perfect selection because it not only is convex but also can exactly recover sparse signals. Then, what about the lq-minimization under 0<q<1? It is amazing that xq can also obtain the sparse solutions via hyperplane y=Ax, and more and more sparsity is being required as q decreases below 1 [4]. This is natural to induce one's strong interest, and some important results have been obtained. Compared with the l1 modeling, a sufficiently sparse signal can be recovered perfectly with the lq(0<q<1) modeling under less restrictive RIP requirements than those needed to guarantee perfect recovery with q=1 [14]. Compared with the l0 modeling, empirical evidence strongly indicates that solving the lq(0<q<1) modeling takes much less time than that with q=0 [15]. These surprising phenomena undoubtedly inspire more people to research the lq(0<q<1) modeling although the lq-minimization problem for 0<q<1 is also NP-hard in general [16]. Reconstruction sparse signals via lq(0<q<1) modeling have been considered in the literature in a series of papers [10, 17–20]. However, it is not clear if there exists any hidden relationship between the lq(0<q<1) modeling and the l0 modeling. Recently, [21] showed that the solution of the lq(0<q<1) problem (3) is also equivalent to that of the l0 problem (2) when q is smaller than a definitive constant CA,y, where the definitive constant CA,y depends only on A and y, which revealed the relationship behind these interesting phenomena.The null space property (NSP) was introduced when one checked the equivalence of the solutions between thel0 modeling and the l1 modeling. When we inspect the existence of the solutions of the function y=Ax, x∈RN, we often make judgement via the null space of matrix A with linear algebra knowledge. Therefore, it is absolutely important to propose the null space property. Now, we introduce the definition of the null space property [6, 8, 22]. Given a subset S of [N]:={1,2,…,N} and a vector v∈RN, we denote by vS the vector that coincides with v on S and that vanishes on the complementary set SC=:[N]∖S.Definition 1.
For any setS⊂[N] with card(S)≤s, a matrix A∈Rn×N is said to satisfy the null space property of order s if(10)vS1<vSC1,for all v∈Ker⁡A∖{0}.The thoughts of the null space have appeared since one researched the best approximation ofL1 [23], but the name was first used by Cohen et al. in [22], and Donoho and Huo [6] and Gribonval and Nielsen [8] developed the thoughts and gave the following theorem.Theorem 2.
Given a matrixA∈Rn×N, every s-sparse vector x∈RN is the unique solution of the l1-minimization with y=Ax if and only if A satisfies the null space property of order s.This theorem not only gives an existence condition of the solution of thel1 modeling but also demonstrates that the solution is right to that of the l0 modeling. That is, it implies that for every y=Ax with s-sparse x, the solution of the l1-minimization problem (8) actually solves the l0-minimization problem (2) when the measurement matrix A satisfies the null space property of order s. Indeed, assume that every s-sparse vector x is recovered via l1-minimization from y=Ax. Let z be the minimizer of the l0-minimization with y=Ax; then z0≤x0, so that also z is s-sparse. But since every s-sparse vector is the unique l1-minimizer, it follows that z=x [16].As for RIP, the null space property is a necessary and sufficient condition to exactly reconstruct the signal using thel1-minimization, which is very important in theory. We see that many works [7, 8, 16, 24–26], especially [16], focused on the null space property on the l1-minimization and gave the stable null space property, the robust null space property, and characterization of the solutions of the l1-minimization problem (8) under these properties. But, as for the null space property on the lq-minimization for 0<q<1, there are few papers [18, 27] touched upon it.This paper focuses on the different types of null space property on thelq-minimization for 0<q<1. The remainder of the paper is organized as follows. In Section 2, based on the standard lq null space property, we give the definition of the lq stable null space property and derive its equivalent form. Then we discuss the approximation of the solutions of the lq-minimization with Ax=Az. In Section 3, we further consider the lq robust null space property and the lq,p robust null space property for 0<p≤q<1, respectively. Using these properties, we effectively characterize reconstruction results for the lq-minimization when the observations are corrupted by noise. In Section 4, according to many practical scenarios, we extend the lq null space property to the lq-synthesis modeling and the mixed l2/lq-minimization, which deals with the dictionary-based sparse signals and the block sparse signals, respectively. Finally, we relegate the proofs of the main results, that is, Theorems 7, 13, 18, and 26 to Appendix.


## 2.lq Stable Null Space Property

In this section, we will discuss thelq stable null space property; for this purpose, we first introduce the lq null space property [8, 16].Definition 3.
For any setS⊂[N] with card(S)≤s, a matrix A∈Rn×N is said to satisfy the lq null space property of order s if(11)vSq<vSCq,for all v∈Ker⁡A∖{0}; here 0<q<1, if one does not make the special statement, then one always supposes that 0<q<1 in what follows.Definition3 generalizes Definition 1. This definition is so important that it can characterize the existence and uniqueness of the solution of the lq-minimization (3) for 0<q<1.Theorem 4.
Given a matrixA∈Rn×N, every s-sparse vector x∈RN is the unique solution of the lq-minimization with y=Ax if and only if A satisfies the lq null space property of order s.The proof of Theorem4 is implied in [8] and easily found in [18].However, in more realistic scenarios, we can only claim that the vectors are close to sparse vectors but no absolutely sparse ones. In such cases, we would like to recover a vectorx∈RN with an error controlled by its distance to s-sparse vectors. This property is usually referred to as the stability of the reconstruction scheme with respect to sparsity defect [16]. To better discuss this property, we give the definition of the lq stable null space property.Definition 5.
For any setS⊂[N] with card(S)≤s, a matrix A∈Rn×N is said to satisfy the lq stable null space property of order s with constant 0<τ<1 if(12)vSq≤τ1/qvSCq,for all v∈Ker⁡A.Remark 6.
Formula (12) is often replaced by vSqq≤τvSCqq with constant 0<τ<1.Obviously, Definition5 is stronger than Definition 3 if v∈Ker⁡A∖{0}. But the following theorem demonstrates that it is also important to introduce Definition 5, because the lq stable null space property characterizes the distance between two vectors x∈RN and z∈RN satisfying Az=Ax.Theorem 7.
For any setS⊂[N] with card(S)≤s, the matrix A∈Rn×N satisfies the lq stable null space property of order s with constant 0<τ<1 if and only if(13)z-xqq≤1+τ1-τzqq-xqq+2xSCqq,for all vectors x,z∈RN with Az=Ax.We defer the proof of this theorem to Appendix. Under this theorem, we give the main stability result as follows.Corollary 8.
Suppose that a matrixA∈Rn×N satisfies the lq stable null space property of order s with constant 0<τ<1; then for any x∈RN, a solution x* of the lq-minimization with y=Ax approximates the vector x with lq-error:(14)x-x*q≤21+τ1-τ1/qσsxq,where(15)σsxq:=inf⁡z∈Σsx-zq,which denotes the error of best s-term approximation to x with respect to the lq-quasinorm. Obviously, if x∈Σs, then σs(x)q=0.Proof.
TakeS to be a set of s largest absolute coefficients of x, so that σs(x)q=xSCq. If x* is a minimizer of the lq-minimization, then x*q≤xq with Ax*=Ax. So we take z=x* in inequality (13); then (16)x-x*qq≤1+τ1-τx*qq-xqq+2σsxq≤2(1+τ)1-τσsxqq,which is the desired inequality.By Corollary8, using σs(x)q=0 for x∈Σs, we have the following corollary.Corollary 9.
Suppose that a matrixA∈Rn×N satisfies the lq stable null space property of order s with constant 0<τ<1; then every s-sparse vector x∈RN can be exactly recovered from the lq-minimization with y=Ax.Compared with Theorem4, the lq stable null space property is only a sufficient condition to exactly recover sparse vector via lq-minimization.Corollary 10.
Suppose that a matrixA∈Rn×N satisfies the lq stable null space property of order s with constant 0<τ<1; then for any 0<p<q<1 and any x∈BpN:={x∈RN:xp≤1}, a solution x* of the lq-minimization with y=Ax approximates the vector x with lq-error: (17)x-x*q≤2(1+τ)1-τ1/qCp,qs1/p-1/qxp,where Cp,q=αα(1-α)1-α1/p≤1, α=p/q.Proof.
This result can be derived from the following inequality [16]:(18)σsxq≤Cp,qs1/p-1/qxp,for any 0<p<q and x∈RN.Remark 11.
Under the condition of Corollary10, we choose p=1/3, q=1/2, and τ=1/2; let xp≤9/48; then (19)x-x*1/2≤1s.Let us choose p=1/4, q=1/2, and τ=1/2; let xp≤4/9; then (20)x-x*1/2≤1s2.


## 3.lq Robust Null Space Property

In realistic situations, it is also inconceivable to measure a signalx∈RN with infinite precision. This means that the measurement vector y∈Rn is only an approximation of the vector Ax∈Rn, with (21)y-Ax2≤ϵ,for some ϵ≥0. In this case, the reconstruction scheme should be required to output a vector x*∈RN whose distance to the original vector x∈RN is controlled by the measurement error ϵ≥0. This property is usually referred to as the robustness of the reconstruction scheme with respect to measurement error [16]. We are going to investigate the following modeling:(22)min⁡x∈RNxqs.t.y-Ax2≤ϵ.Definition 12.
For any setS⊂[N] with card(S)≤s, a matrix A∈Rn×N is said to satisfy the lq robust null space property of order s with constant 0<τ<1 and γ>0, if(23)vSqq<τvSCqq+γAv2,for all v∈RN.We see that Definition12 is broader than Definition 5, because it does not require that v∈Ker⁡A. Obviously, if v∈Ker⁡A, the lq robust null space property implies the lq stable null space property. Similar to Theorem 7, we also give an equivalent form of the lq robust null space property.Theorem 13.
For any setS⊂[N] with card(S)≤s, the matrix A∈Rn×N satisfies the lq robust null space property of order s with constant 0<τ<1 and γ>0 if and only if(24)z-xqq≤1+τ1-τzqq-xqq+2xSCqq+2γ1-τAz-x2,for all vectors x,z∈RN.The proof of Theorem13 is deferred to Appendix, and spirit of this theorem is the following corollary.Corollary 14.
Suppose that a matrixA∈Rn×N satisfies the lq robust null space property of order s with constant 0<τ<1 and γ>0; then for any x∈RN, a solution x* of the lq-minimization with y=Ax+e and e2≤ϵ approximates the vector x with lq-error:(25)x-x*qq≤2(1+τ)1-τσsxqq+4γ1-τϵ.Proof.
Noting thatA(z-x)2≤2ϵ, the rest of proof is similar to that of Corollary 8.Remark 15.
Whenϵ=0, inequality (25) is the conclusion of Corollary 8.Remark 16.
Using inequality(aq+bq)1/q≤21/q-1(a+b) for a,b≥0 and 0<q≤1, inequality (25) can be modified such that (26)x-x*q≤21/q-121+τ1-τ1/qσsxq+4γ1-τϵ1/q=22/q-11+τ1-τ1/qσsxq+23/q-1γ1-τϵ1/q,and if we set e2≤ϵq, 0<q≤1, then we can get the following inequality:(27)x-x*q≤Cq,τσsxq+Cq,τ,γϵ,where Cq,τ=22/q-1(1+τ/1-τ)1/q and Cq,τ,γ=23/q-1(γ/1-τ)1/q.Inequality (27) or (14) is the same as that of Theorem 3.1 in [10] except for the constant when we only consider y=Ax, but we used the different approach; the latter is based on the measurement matrix A satisfying the following inequality: (28)γ2t-1<4(2-1)ts1/q-1/2,for some integer t≥s, where γ2s:=β2s2/α2s2, while αs and βs are the best constants such that the measurement matrix A satisfies the following inequality: (29)αsx2≤Ax2≤βsx2,x∈Σs.If we add the robust term, inequality (27) is better than that of Theorem 3.1 in [10].The rest of this section will focus on another robust null space property, that is, thelq,p robust null space property for 0<p≤q≤1. In the following definition, we will use two quasinorms lq and lp rather than the same quasinorm.Definition 17.
Given0<p≤q≤1, for any set S⊂[N] with card(S)≤s, a matrix A∈Rn×N is said to satisfy the lq,p robust null space property of order s with constant 0<τ<1 and γ>0, if(30)vSqq<τsq/p-1vSCpp+γsq/p-1Av2,for all v∈RN.Obviously, whenp=q<1, Definition 17 reduces to Definition 12, so we will consider the case p<q<1.Theorem 18.
Given0<p<q≤1, for any set S⊂[N] with card(S)≤s, suppose that the matrix A∈Rn×N satisfies the lq,p robust null space property of order s with constant 0<τ<1 and γ>0; then, for any x,z∈RN and z-xp≤1, one has(31)z-xqq≤C1sq/p-1zpp-xpp+2xSCpp+C2sq/p-1A(z-x)2,where C1=(1+τ)2/1-τ and C2=(3+τ)γ/1-τ.We defer the proof of this theorem to Appendix. In the proof, we will see that the conditionz-xp≤1, x,z∈RN, is necessary in Theorem 18.Corollary 19.
Given0<p<q≤1, suppose that a matrix A∈Rn×N satisfies the lq,p robust null space property of order s with constant 0<τ<1 and γ>0; then for any x∈RN, a solution x* of the lq-minimization with y=Ax+e and e2≤ϵ approximates the vector x with lq-error:(32)x-x*qq≤2C1sq/p-1σsxpp+2C2sq/p-1ϵ,where C1 and C2 are the same as those of Theorem 18.Remark 20.
In Corollary19, if we set ϵ=0, then lq-error is controlled by 1/sq/p-1σs(x)pp; that is,(33)x-x*qq≤Csq/p-1σsxpp.Although the quasinorm also satisfies ·q≤·p for 0<p<q<1, the term 1/sq/p-1σs(x)pp is not worse than σs(x)qq, because the reconstruction lq-error decays in rate sq/p-1.


## 4. Extensions

In this section, we will discuss two extensions of thelq null space property; one is on the null space property of the lq-synthesis modeling and the other is on the lq block null space property of the mixed l2/lq-minimization.


### 4.1. Null Space Property of thelq-Synthesis Modeling

The techniques above hold for signals which are sparse in the standard coordinate basis or sparse with respect to some other orthonormal basis. However, in practical examples, there are numerous signals which are sparse in an overcomplete dictionaryD rather than an orthonormal basis; see [27–32]. Here D is N×m(N<m) matrix that is often rather coherent in applications. We also call D a frame in the sense that the columns of D form a finite frame. In this setting, the signal x∈RN can be represented as x=Df, where f is an s-sparse vector in Rm. Such signal is called dictionary-sparse signals or frame-sparse signals [33]. When the dictionary D is specified, the signals are also called D-sparse signals. Many signals naturally possess frame-sparse coefficients, such as radar images (Gabor frames), cartoon-like images (curvelets), and images with directional features (shearlets) [32–35].Thel1-synthesis modeling [34] is defined by(34)f^=argmin⁡f∈Rmf1s.t.y=ADf,x^=Df^.The above method is called l1-synthesis modeling due to the second synthesizing step. It is relative to the l1-analysis modeling, which finds the solution x^ directly by solving the problem [32](35)x^=argmin⁡x∈RND*x1s.t.y=Ax,where D* denotes the transpose of the D.Empirical studies show that thel1-synthesis modeling often provides good recovery; however, it is fundamentally distinct from the l1-analysis modeling. The geometry of two problems was analyzed in [28], and there it was shown that because these geometrical structures exhibit substantially different properties, there was a large gap between the two formulations. This theoretical gap was also demonstrated by numerical simulations in [28], which showed that the two methods perform very differently on large families of signals. Recently, [33] elaborated why the authors introduced the l1-synthesis and the relationship of the two methods, and it appeared that the l1-synthesis is a more thorough method than the l1-analysis, and the l1-analysis is a subproblem of the l1-synthesis via sparse duals. Besides, [33] built up a framework for the l1-synthesis method and proposed a dictionary-based null space property which is the first sufficient and necessary condition for the success of the l1-synthesis method.In this subsection, we only propose thelq-synthesis modeling and give the null space property of the minimization but did not elaborate the relationship between the lq-synthesis modeling and the lq-analysis modeling. The lq-synthesis modeling is as follows:(36)f^=argmin⁡f∈Rmfqs.t.y=ADf,x^=Df^.Given a frameD∈RN×m, D-1(B) denotes the preimage of the set B under the frame D. We introduce the following notation [33]: (37)DΣs={x∈RN:∃f,suchthatx=Df,f0≤s}.Definition 21.
Fix a dictionaryD∈RN×m, for any set S⊂[N] with card(S)≤s; a matrix A∈Rn×N is said to satisfy the lq null space property of frame D of order s if for any v∈D-1(kerA∖{0}) there exists u∈kerD, such that(38)vS+uq<vSCq.This null space property is abbreviated toD-NSP. Here, a natural question is proposed which is why does not AD directly satisfy the lq null space property? The major difference is that D-NSP is essentially the minimum of vS+uq over all u∈kerD, where u=0, and the D-NSP degenerates into AD having the lq null space property. Therefore this new condition about the lq-synthesis modeling is weaker than AD having the lq null space property.The following theorem asserts that the null space property of a frameD of order s is a sufficient and necessary condition for the lq-synthesis modeling (36) to successfully recover all the D-sparse signals with sparsity s.Theorem 22.
Fix a dictionaryD∈RN×m; let A∈Rn×N; for any x0∈DΣs, one has x^=x0, where x^ is the reconstructed signal from y=Ax0 using the lq-synthesis modeling if only if A satisfies the lq null space property of frame D of order s.Proof.
Combining the proof of Theorem 4.2 in [33] with the proof of Theorem 4 (Lemma 2.2 in [18]), the content adds very little to the work. Here, the proof is omitted.Remark 23.
On the null space property of thelq-analysis modeling is implied in [27].


### 4.2. Block Null Space Property of the Mixedl2/lq-Minimization

The conventional compressed sensing only considers the sparsity that the signalx has at most s nonzero elements, which can appear anywhere in the vector, and it does not take into account any further structure. However, in many practical scenarios, the unknown signal x not only is sparse but also exhibits additional structure in the form that the nonzero elements are aligned to blocks rather than being arbitrarily spread throughout the vector. These signals are referred to as the block sparse signals and arise in various applications, for example, DNA microarrays [36], equalization of sparse communication channels [37], and color imaging [38]. To define the block sparsity, it is necessary to introduce some further notations. Suppose that x∈RN is split into m blocks, x[1],x[2],…,x[m], which are of length d1,d2,…,dm, respectively; that is,(39)x=x1,…,xd1︸x1,xd1+1,…,xd1+d2︸x2,…,xN-dm+1,…,xN︸xmT,and N=∑i=1m‍di. A vector x∈RN is called block s-sparse over I={d1,d2,…,dm} if x[i] is nonzero for at most s indices i. When di=1 for each i, the block sparsity reduces to the conventional definition of a sparse vector. Denote (40)x2,0=∑i=1m‍I(x[i]2>0),where I(x[i]2>0) is an indicator function that obtains the value 1 if x[i]2>0 and 0 otherwise. So a block s-sparse vector x can be defined by x2,0≤s, and x0=∑i=1m‍x[i]0. Here, to avoid confusion with the above notations, we especially emphasize that s denotes s blocks of the signal out of m which are nonzero but not s entries out of N which are nonzero outlined in the above sections.To recover a block sparse signal, similar to the standardl0-minimization, one will pursue the sparsest block sparse vector with the following mixed l2/l0 modeling [39–41]:(41)min⁡x∈RNx2,0s.t.y=Ax.But the mixed l2/l0-minimization problem is also NP-hard. It is natural that one uses the mixed l2/l1-minimization to replace the mixed l2/l0 model [39–42]:(42)min⁡x∈RNx2,1s.t.y=Ax,where (43)x2,1=∑i=1m‍x[i]2.To investigate the performance of this method, Eldar and Mishali [40] proposed the definition of the block Restricted Isometry Property (block RIP) of a measurement matrix A∈Rn×N. We say that a matrix A satisfies the block RIP over I={d1,d2,…,dm} of order s with positive constant δs∣I if for every block s-sparse vector x∈RN over I, such that(44)(1-δs∣I)x22≤Ax22≤(1+δs∣I)x22.Obviously, the block RIP is a natural extension of the standard RIP, but it is a less stringent requirement comparing with the standard RIP. Besides, the required number of measurements of satisfying the block RIP is less than that of satisfying the standard RIP [43]. Eldar and Mishali [40] proved that the mixed l2/l1-minimization can exactly recover any block s-sparse signal when the measurement matrix A satisfies the block RIP with δ2s∣I<0.414. Recently, Lin and Li [43] improved the sufficient condition to δ2s∣I<0.4931 and established another sufficient condition δs∣I<0.307 for exact recovery. There are also a number of works based on non-RIP-analysis to characterize the theoretical performance of the mixed l2/l1-minimization, such as block coherence [39], strong group sparsity [44], and null space characterization [42].Based on the previous discussion of the performance of thelq-minimization, it is also natural that one would be interested to make an ongoing effort to extend the lq-minimization to the setting of block sparse signal recovery. Therefore, the l2/lq-minimization was proposed in [38, 45, 46]. Consider(45)min⁡x∈RNx2,qs.t.y=Ax,where (46)x2,q=∑i=1m‍xi2q1/q.In [38, 45, 46], some numerical experiments demonstrated that fewer measurements are needed for exact recovery when 0<q<1 than when q=1. Moreover, exact recovery conditions based on block restricted q-isometry property have also been studied [46].In this subsection, we will extend thelq null space property to the block sparse signals. As for m-block signal x∈RN, whose structure is like (39), we set S⊂{1,2,…,m} and by SC we mean the complement of the set S with respect to {1,2,…,m}; that is, SC={1,2,…,m}∖S.Definition 24.
For any setS⊂{1,2,…,m} with card(S)≤s, a matrix A∈Rn×N is said to satisfy the lq block null space property over I={d1,d2,…,dm} of order s, if(47)vS2,q<vSC2,q,for all v∈Ker⁡A∖{0}, where vS denotes the vector equal to v on a block index set S and zero elsewhere.Remark 25.
Inequality (47) can be replaced by vS2,qq<vSC2,qq or vS2,qq<1/2v2,qq for every set S⊂{1,2,…,m} with card(S)≤s.Using Definition24, we can easily characterize the existence and uniqueness of the solution of the mixed l2/lq-minimization (45).Theorem 26.
Given a matrixA∈Rn×N, every block s-sparse vector x∈RN is the unique solution of the mixed l2/lq-minimization with y=Ax if and only if A satisfies the lq block null space property of order s.We defer the proof of Theorem26 to Appendix.So far, we only extend the standardlq NSP to the lq-synthesis modeling and the mixed l2/lq-minimization, respectively. As for extension of the stable lq NSP and the robust lq NSP, we will leave it for our next works, especially, for discussion of the block sparse signals via mixed l2/lq-minimization.


## 4.1. Null Space Property of thelq-Synthesis Modeling

The techniques above hold for signals which are sparse in the standard coordinate basis or sparse with respect to some other orthonormal basis. However, in practical examples, there are numerous signals which are sparse in an overcomplete dictionaryD rather than an orthonormal basis; see [27–32]. Here D is N×m(N<m) matrix that is often rather coherent in applications. We also call D a frame in the sense that the columns of D form a finite frame. In this setting, the signal x∈RN can be represented as x=Df, where f is an s-sparse vector in Rm. Such signal is called dictionary-sparse signals or frame-sparse signals [33]. When the dictionary D is specified, the signals are also called D-sparse signals. Many signals naturally possess frame-sparse coefficients, such as radar images (Gabor frames), cartoon-like images (curvelets), and images with directional features (shearlets) [32–35].Thel1-synthesis modeling [34] is defined by(34)f^=argmin⁡f∈Rmf1s.t.y=ADf,x^=Df^.The above method is called l1-synthesis modeling due to the second synthesizing step. It is relative to the l1-analysis modeling, which finds the solution x^ directly by solving the problem [32](35)x^=argmin⁡x∈RND*x1s.t.y=Ax,where D* denotes the transpose of the D.Empirical studies show that thel1-synthesis modeling often provides good recovery; however, it is fundamentally distinct from the l1-analysis modeling. The geometry of two problems was analyzed in [28], and there it was shown that because these geometrical structures exhibit substantially different properties, there was a large gap between the two formulations. This theoretical gap was also demonstrated by numerical simulations in [28], which showed that the two methods perform very differently on large families of signals. Recently, [33] elaborated why the authors introduced the l1-synthesis and the relationship of the two methods, and it appeared that the l1-synthesis is a more thorough method than the l1-analysis, and the l1-analysis is a subproblem of the l1-synthesis via sparse duals. Besides, [33] built up a framework for the l1-synthesis method and proposed a dictionary-based null space property which is the first sufficient and necessary condition for the success of the l1-synthesis method.In this subsection, we only propose thelq-synthesis modeling and give the null space property of the minimization but did not elaborate the relationship between the lq-synthesis modeling and the lq-analysis modeling. The lq-synthesis modeling is as follows:(36)f^=argmin⁡f∈Rmfqs.t.y=ADf,x^=Df^.Given a frameD∈RN×m, D-1(B) denotes the preimage of the set B under the frame D. We introduce the following notation [33]: (37)DΣs={x∈RN:∃f,suchthatx=Df,f0≤s}.Definition 21.
Fix a dictionaryD∈RN×m, for any set S⊂[N] with card(S)≤s; a matrix A∈Rn×N is said to satisfy the lq null space property of frame D of order s if for any v∈D-1(kerA∖{0}) there exists u∈kerD, such that(38)vS+uq<vSCq.This null space property is abbreviated toD-NSP. Here, a natural question is proposed which is why does not AD directly satisfy the lq null space property? The major difference is that D-NSP is essentially the minimum of vS+uq over all u∈kerD, where u=0, and the D-NSP degenerates into AD having the lq null space property. Therefore this new condition about the lq-synthesis modeling is weaker than AD having the lq null space property.The following theorem asserts that the null space property of a frameD of order s is a sufficient and necessary condition for the lq-synthesis modeling (36) to successfully recover all the D-sparse signals with sparsity s.Theorem 22.
Fix a dictionaryD∈RN×m; let A∈Rn×N; for any x0∈DΣs, one has x^=x0, where x^ is the reconstructed signal from y=Ax0 using the lq-synthesis modeling if only if A satisfies the lq null space property of frame D of order s.Proof.
Combining the proof of Theorem 4.2 in [33] with the proof of Theorem 4 (Lemma 2.2 in [18]), the content adds very little to the work. Here, the proof is omitted.Remark 23.
On the null space property of thelq-analysis modeling is implied in [27].


## 4.2. Block Null Space Property of the Mixedl2/lq-Minimization

The conventional compressed sensing only considers the sparsity that the signalx has at most s nonzero elements, which can appear anywhere in the vector, and it does not take into account any further structure. However, in many practical scenarios, the unknown signal x not only is sparse but also exhibits additional structure in the form that the nonzero elements are aligned to blocks rather than being arbitrarily spread throughout the vector. These signals are referred to as the block sparse signals and arise in various applications, for example, DNA microarrays [36], equalization of sparse communication channels [37], and color imaging [38]. To define the block sparsity, it is necessary to introduce some further notations. Suppose that x∈RN is split into m blocks, x[1],x[2],…,x[m], which are of length d1,d2,…,dm, respectively; that is,(39)x=x1,…,xd1︸x1,xd1+1,…,xd1+d2︸x2,…,xN-dm+1,…,xN︸xmT,and N=∑i=1m‍di. A vector x∈RN is called block s-sparse over I={d1,d2,…,dm} if x[i] is nonzero for at most s indices i. When di=1 for each i, the block sparsity reduces to the conventional definition of a sparse vector. Denote (40)x2,0=∑i=1m‍I(x[i]2>0),where I(x[i]2>0) is an indicator function that obtains the value 1 if x[i]2>0 and 0 otherwise. So a block s-sparse vector x can be defined by x2,0≤s, and x0=∑i=1m‍x[i]0. Here, to avoid confusion with the above notations, we especially emphasize that s denotes s blocks of the signal out of m which are nonzero but not s entries out of N which are nonzero outlined in the above sections.To recover a block sparse signal, similar to the standardl0-minimization, one will pursue the sparsest block sparse vector with the following mixed l2/l0 modeling [39–41]:(41)min⁡x∈RNx2,0s.t.y=Ax.But the mixed l2/l0-minimization problem is also NP-hard. It is natural that one uses the mixed l2/l1-minimization to replace the mixed l2/l0 model [39–42]:(42)min⁡x∈RNx2,1s.t.y=Ax,where (43)x2,1=∑i=1m‍x[i]2.To investigate the performance of this method, Eldar and Mishali [40] proposed the definition of the block Restricted Isometry Property (block RIP) of a measurement matrix A∈Rn×N. We say that a matrix A satisfies the block RIP over I={d1,d2,…,dm} of order s with positive constant δs∣I if for every block s-sparse vector x∈RN over I, such that(44)(1-δs∣I)x22≤Ax22≤(1+δs∣I)x22.Obviously, the block RIP is a natural extension of the standard RIP, but it is a less stringent requirement comparing with the standard RIP. Besides, the required number of measurements of satisfying the block RIP is less than that of satisfying the standard RIP [43]. Eldar and Mishali [40] proved that the mixed l2/l1-minimization can exactly recover any block s-sparse signal when the measurement matrix A satisfies the block RIP with δ2s∣I<0.414. Recently, Lin and Li [43] improved the sufficient condition to δ2s∣I<0.4931 and established another sufficient condition δs∣I<0.307 for exact recovery. There are also a number of works based on non-RIP-analysis to characterize the theoretical performance of the mixed l2/l1-minimization, such as block coherence [39], strong group sparsity [44], and null space characterization [42].Based on the previous discussion of the performance of thelq-minimization, it is also natural that one would be interested to make an ongoing effort to extend the lq-minimization to the setting of block sparse signal recovery. Therefore, the l2/lq-minimization was proposed in [38, 45, 46]. Consider(45)min⁡x∈RNx2,qs.t.y=Ax,where (46)x2,q=∑i=1m‍xi2q1/q.In [38, 45, 46], some numerical experiments demonstrated that fewer measurements are needed for exact recovery when 0<q<1 than when q=1. Moreover, exact recovery conditions based on block restricted q-isometry property have also been studied [46].In this subsection, we will extend thelq null space property to the block sparse signals. As for m-block signal x∈RN, whose structure is like (39), we set S⊂{1,2,…,m} and by SC we mean the complement of the set S with respect to {1,2,…,m}; that is, SC={1,2,…,m}∖S.Definition 24.
For any setS⊂{1,2,…,m} with card(S)≤s, a matrix A∈Rn×N is said to satisfy the lq block null space property over I={d1,d2,…,dm} of order s, if(47)vS2,q<vSC2,q,for all v∈Ker⁡A∖{0}, where vS denotes the vector equal to v on a block index set S and zero elsewhere.Remark 25.
Inequality (47) can be replaced by vS2,qq<vSC2,qq or vS2,qq<1/2v2,qq for every set S⊂{1,2,…,m} with card(S)≤s.Using Definition24, we can easily characterize the existence and uniqueness of the solution of the mixed l2/lq-minimization (45).Theorem 26.
Given a matrixA∈Rn×N, every block s-sparse vector x∈RN is the unique solution of the mixed l2/lq-minimization with y=Ax if and only if A satisfies the lq block null space property of order s.We defer the proof of Theorem26 to Appendix.So far, we only extend the standardlq NSP to the lq-synthesis modeling and the mixed l2/lq-minimization, respectively. As for extension of the stable lq NSP and the robust lq NSP, we will leave it for our next works, especially, for discussion of the block sparse signals via mixed l2/lq-minimization.



---

*Source: 579853-2015-03-16.xml*