# Stability of 1-Bit Compressed Sensing in Sparse Data Reconstruction

Authors: Yuefang Lian; Jinchuan Zhou; Jingyong Tang; Zhongfeng Sun
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

1-bit compressing sensing (CS) is an important class of sparse optimization problems. This paper focuses on the stability theory for 1-bit CS with quadratic constraint. The model is rebuilt by reformulating sign measurements by linear equality and inequality constraints, and the quadratic constraint with noise is approximated by polytopes to any level of accuracy. A new concept called restricted weak RSP of a transposed sensing matrix with respect to the measurement vector is introduced. Our results show that this concept is a sufficient and necessary condition for the stability of 1-bit CS without noise and is a sufficient condition if the noise is available.


---

## Body

## 1. Introduction

The standard noiseless compressing sensing (CS) model is to solve the following optimization problem:(1)minx0,s.t.Ax=y,where A∈ℝm×n is a sensing (or measurement) matrix and x is a sparse signal requiring robust reconstruction from a given nonadaptive measurement vector y [1–4]. The l0-minimization problem is well known to be NP-hard. Hence, to overcome this difficulty, a typical treatment is resorting to use l1-norm. Along this approach, a great deal of algorithms is available, e.g., orthogonal matching pursuit algorithm [5], basis pursuit algorithm [6], iterative hard threshold algorithm [7], and iteratively reweighted least squares algorithm [8]. Moreover, some added assumptions have to be added on the measurement matrix A to ensure that a sparse solution/signal could be exactly recovered by l1 minimization. These conditions include restricted isometry property [9–11], coherence condition [12], null space property [8, 13, 14], and range space property [15, 16]. In recent research, some work has been done concerning the robust reconstruction condition (RRC) based on the above traditional properties and their variants, e.g., exact reconstruction condition [17], double null space property [18], and null space property [19].However, the above CS model cannot be adapted in some practical problems; for example, in brain signal processing and sigma-delta converters, only the sign or support of a signal is measured. This motivates one to consider sparse signal recovery through low bits of measurements. An extreme quantization is only one bit per measurement. It gives rise to the theory of 1-bit compressed sensing (see Boufounos and Baraniuk [20]).In this paper, we further consider a constrained 1-bit compressed sensing model involved by a noisy constraint. Precisely, letA∈ℝm×nandB∈ℝl×n be two given full-row rank matrices. Pick y∈1,−1,0m with, b∈ℝl is a given vector, and ε is a positive number. The constrained 1-bit compressed sensing model is described as follows:(2)Pminx0s.t. signAx=y,b−Bx2≤ε,where the last term b−Bx2≤ε stands for a noisy constraint. The corresponding convex relaxed problem via l1-norm is expressed as(3)minx1,s.t. signAx=y,b−Bx2≤ε.Compared with the recovery of a given signal, it is equally important to study whether the recovered signal is stable. The stability of recovery means that recovery errors stay under control even if the measurements are slightly inaccurate and the data are not exactly sparse. Recent stability study for CS can be found in [21–25]. However, few theoretical results are available on the stability of 1-bit CS. In general, it is impossible to exactly reconstruct a sparse signal by only using 1-bit information. For example, if signAx∗=1,1, then any sufficiently small perturbation x∗+v is also positive and hence satisfies the requirement. Hence, we turn our attention to recover part of the information in 1-bit CS, such as support set or sign of a target signal. Due to this reason, the following criterion,(4)xx2−x∗x∗22≤Δ,where x≠0 and x∗≠0 and Δ denotes a sufficient small positive scalar and has been widely used in the 1-bit CS literature. Inspired by this observation, the problem (1) is said to be stable for noisy reconstruction, if for any nonzero vector x∈ℜn, there is a nonzero solution x∗ of (3) such that(5)xx2−x∗x∗22≤τxC1σkx1+C2ε,where C1 and C2 are constant depending on the primal problem data A,y,ε,B,b. If ε=0 and x is k-sparse, then the right side of (5) is zero and hence x/‖x‖2=x∗/‖x∗‖2, which in turn implies that signx=signx∗; i.e., the sign of target signals can be exact recovery.The main target of this paper is to study the necessary and/or sufficient condition for (5). First, a new definition called restricted weak RSP with respect to y is introduced. Our results show that, for 1-bit CS, this condition is sufficient and necessary condition for stability if there is no noise, while it is sufficient if the noise is available. The analysis is based on the duality theory of linear programming and the fact that the ball constraint can be approximated by polytopes to any level of accuracy.The notations used in this paper are standard. Letℝ+n be the set of nonnegative vectors in ℝn. Given a set S, S denotes the cardinality of S. The l0-norm x0 counts the number of nonzero components of x, and the l1-norm of x is defined as x1≔∑i=1nxi. Let e stand for a vector of ones, i.e., e=1,…,1T. For a vector x, write x+≔maxx,0 and x−≔max−x,0. For any two norms ⋅p and ⋅q with p,q≥1, the induced matrix norm Ap⟶q is defined as Ap⟶q≔maxxp≤1Axq. A convex combination between the points x1 and x2 is written as x1,x2, i.e.,(6)x1,x2≔λx1+1−λx2λ∈0,1.Given a vectory=1,−1,0m, let(7)J+y≔i:yi=1,J−y≔i:yi=−1,J0y≔i:yi=0.The sign function is defined as(8)signt≔1,t>0,−1,t<0,0,t=0,and signxi≔signxi where x∈ℜn and i=1,…,n. The projection of x onto a convex set S is denoted by πSx, i.e., πSx≔argminz∈Sx−z2. Denote by S1∪S2c the complement of S1∪S2 in 1,2,…,n. The error of the best k-term approximation of a vector x is defined as(9)σkx1≔infux−u1:u0≤k.The Hausdorff metric of two setsM1,M2⊆ℜn is(10)dℋM1,M2≔maxsupx∈M1infz∈M2x−z2,supx∈M2infz∈M1x−z2.Robinson’s constant is defined as follows:(11)σα1,α2M′,M″≔maxN⊆1,…,mμα1,α2IN0−I0,M′M″T,where(12)μα1,α2P,Q≔maxb,dα2≤1,b,d∈Fminz∈ℝqzα1:Pz≤b,Qz=d,F≔b,dPz≤b,Qz=dfor somez∈ℝq.


## 2. Reformulation and Approximation of (3)

The 1-bit CS is NP-hard and hence is difficult to solve precisely. It motivates us to reformulate the 1-bit CS problem by removing the sign function. The advantage of such a reformulation is yielding a decoding method based on the theory of linear programming.Given sign measurementsy∈−1,1,0m, denote by A+,A−,andA0 the submatrices of A in which their rows are corresponding to index sets J+y, J−y, and J0y, respectively. For simplification of notations, we simply use J+, J0, and J− to denote J+y, J0y, and J−y, respectively. In the following analysis, we always assume that J+∪J−≠∅ because otherwise y=0, and nothing is measured in this case.The constraintsignAx=y can be rewritten equivalently as(13)signA+x=eJ+,signA−x=−eJ−,signA0x=0.By rearranging the order of the components ofy and the order of the associated rows of A if necessary, we may assume without loss of generality that(14)A=A+A−A0,y=eJ+−eJ−0.It is clear that(15)x|A+x>0,A−x<0,A0x=0=∪α>0xA+x≥αe,A−x≤−αe,A0x=0.In fact, the inclusion “⊇” is clear. For “⊆,” take x satisfying A+x>0,A−x<0,A0x=0. Define(16)α≔minAix,−Ajxi∈J+,j∈J−.Clearly,α>0. Thus, Aix≥α for all i∈J+ and −Ajx≥α for all j∈J−; i.e., A+x≥αe and A−x≤−αe. Therefore,(17)x∈∪α>0xA+x≥αe,A−x≤−αe,A0x=0.For any fixedα>0, define the following relaxed problem (denoted by α-problem for short),(18)minx1s.t.A+x≥αeJ+,A−x≤−αeJ−,A0x=0,b−Bx2≤ε.The formula (15) shows that ℱ=∪α>0ℱα, where ℱ and ℱα denote the feasible region of the primal problem and the relaxed problem, respectively. In addition, ℱβ⊆ℱα as long as β≥α. Thus,(19)ℱ=∪α>0ℱα⊆limα⟶0+ℱα=clℱ,where the limit is in the sense of the Painlevé–Kuratowski.Proposition 1.
A vectorx∗ is an optimal solution of primal problem (P) if and only if x∗ is an optimal solution of β-problem for all β∈0,α, where α≔minAix∗,−Ajx∗i∈J+,j∈J−.Proof.
“⇒.” The construction of α ensures that A+x∗≥αe,A−x∗≤−αe,andA0x∗=0. Hence, for ∀β≤α,(20)A+x∗≥αe≥βe,A−x∗≤−αe≤−βe,A0x∗=0,i.e., x∗ is a feasible solution of β-problem. Since x∗ is an optimal solution of the primal problem, x∗ is the optimal solution of β-problem due to ℱβ⊂ℱ by (15).
“⇐.” Let x˜∗ be an optimal solution of the primal problem. Take β∈0,α˜ where α˜≔minα,α′ and α′≔minAix˜∗,−Ajx˜∗i∈J+,j∈J−. Then, x˜∗,x∗∈ℱβ due to the monotonicity of ℱα with respect to α. By assumption, x∗ is an optimal solution of β-problem. Since x˜∗∈ℱβ and is an optimal solution of the primal problem, then x∗ is an optimal solution of the primal problem.
Denote byT∗ and Tα∗ the optimal solution set of (3) and (18), respectively. Following the similar argument as above, we can obtain the following result.Corollary 1.
There existsα>0 such that Tβ∗⊆T∗ for all β∈0,α.The problem (18) by introducing the slack variables r and s can be rewritten equivalently as(21)minx,r,sx1s.t.A+x≥αeJ+,A−x≤−αeJ−,A0x=0,s≤ε,r∈sB,r=b−Bx,s≥0,where B stands for the unit l2-ball, i.e., B≔z∈ℝm:z2≤1. According to the convex set separate theorem, the set B can be described as an intersection of an infinite number of half spaces, i.e.,(22)B=∩a2=1z∈ℝm:aTz≤1.Define(23)Eα≔x,s:s≤ε,A+x≥αeJ+,A−x≤−αeJ−,A0x=0,s≥0.Notice that(24)Tα∗=x:x1≤θα∗,r∈sB,r=b−Bx,x,s∈Eα,where θα∗ denotes the optimal value of (18). Replacing B in (24) by a polytope P⊇B yields a relaxation of Tα∗, called TαP, i.e.,(25)TαP≔x:x1≤θα∗,r∈sP,r=b−Bx,x,s∈Eα.The following lemma claims that the polytopeTP can approximate T∗ to any level of accuracy, as long as P is chosen suitably.Lemma 1.
(see [25], Corollary 6.5.2). For any ε>0, there exists a polytope approximation P of B satisfying P⊇B and(26)dℋTα∗,TαP≤ε.In the remainder of the paper, we fixε>0 and choose a polytope P such that TαP and Tα∗ satisfying (26). The polytope can be described as an interaction of a finite number of half spaces:(27)P≔z∈ℝl:aiT,z≤1,i∈1,…,L,where ai for i∈1,…,L are some unit vectors (i.e., ai2=1) and L is an integer number. For the convenience in the following analysis, we further add 2l half spaces(28)βjTz≤1,−βjTz≤1,j=1,…,l,to P, where βj is the j-th column of the l×l identity matrix. This yields the following polytope:(29)P0≔P∩z∈ℝl:βjTz≤1,−βjTz≤1,j=1,…,l=z∈ℝl:aiTz≤1,i∈1,…,L;βjTz≤1,j=1,…,l;−βjTz≤1,j=1,…,l.Denote byΩ the collection of the vectors ai and ±βj in P0, i.e.,(30)Ω≔ai:i∈1,…,L∪±βj:j∈1,…,l.Clearly,P0 still satisfies (26), i.e.,(31)dℋTα∗,TαP0≤ε.LetN≔Ω and let MP0 be the matrix with column vectors in Ω. Thus, P0 can be written as(32)P0=z∈ℝl:MP0Tz≤eN,where eN is the vector of one’s in ℝN.By replacingB by the above P0, we obtain the following approximation of (3):(33)minxx1:b−Bx∈εP0,A+x≥αeJ+,A−x≤−αeJ−,A0x=0,and the solution set of (33) is(34)TαP0∗=x:x1≤θαP0∗,b−Bx∈εP0,A+x≥αeJ+,A−x≤−αeJ−,A0x=0=x:x1≤θαP0∗,r∈sP0,r=b−Bx,x,s∈Eα,where θαP0∗ denotes the optimal value of (33). Since B⊆P0, then(35)θα∗≥θαP0∗,TαP0∗⊆TαP0,Tα∗⊆TαP0.


## 3. Stability Analysis

The concept of range space property (RSP for short) was first introduced in [15] to develop a necessary and sufficient condition for uniform recovery of sparse signals via l1-minimization. It was extended in [26] to weak RSP for developing stability theory of convex optimization algorithms. Recently, restricted RSP (RRSP) was introduced to develop sign recovery condition for sparse signals through 1-bit measurement in [16, 25].Definition 1.
(weak RSP). Given a matrixA∈ℝm×n, the transposed matrix AT is said to possess the weak RSP order k, if for any two disjoint sets S1,S2⊆1,…,n with S1+S2≤k, there exists a vector η∈ℛAT such that(36)ηi=1,fori∈S1,ηi=−1,fori∈S2,ηi≤1fori∉S1∪S2.
To investigate the stability of 1-bit compressed sensing involved noise constraints, the notion of weak RSP is needed to be extended to the following restricted weak RSP with respect toy.Definition 2.
(restricted weak RSP with respect toy). Given matrices A∈ℝm×n, B∈ℝl×n, and y∈−1,1,0m, the pair AT,BT is said to satisfy the restricted weak RSP of order k with respect to y, if for any disjoint subsets S1, S2 of 1,…,n with S1+S2≤k, there exists η∈ℛAT,BT such that(37)η=AT,BTwh,where w=w1,w2,w3T∈ℝ+J+×ℝ−J−×ℝJ0, h∈ℝl, and(38)ηi=1,fori∈S1,ηi=−1,fori∈S2,ηi≤1,fori∉S1∪S2.Theorem 1.
LetA∈ℜm×n and B∈ℜl×n be given matrices and b∈ℜl. Suppose that, for any given vector y∈signAxx0≤k, the following holds: for any x∈ℜn satisfying y=signAx, there is a solution x∗ of(39)minxx1,s.t.A+x≥αeJ+,A−x≤−αeJ−,A0x=0,Bx=b,where α>0 and A+,A0,andA− are submatrices of A in which their rows are corresponding to index sets J+y, J−y, and J0y, such that(40)xx2−x∗x∗22≤Cσkx1.Here,C is a constant dependent only on the problem data A,B,y,b. Then, AT,BT must satisfy the restricted weak RSP of order k with respect to y.Proof.
LetS1,S2 be any pair of disjoint subsets of 1,…,n with S1+S2≤k. To prove that AT,BT satisfies the restricted weak RSP of order k with respect to y, it is sufficient to show that there exists a vector η∈ℛAT,BT such that(41)η=AT,BTwh,where w≔w1,w2,w3T∈ℝ+J+×ℝ−J−×ℝJ0, h∈ℝl, and(42)ηi=1,fori∈S1;ηi=−1,fori∈S2;ηi≤1,fori∉S1∪S2.
Take ak-sparse vector x^ in ℝn. Define(43)S1≔i:x^i>0,S2≔i:x^i<0.
Lety≔signAx^. By assumption, there is a solution x∗ of (39) such that(44)x^x^2−x∗x∗22≤Cσkx^1.
Sincex^ is k-sparse, then σkx^1=0, which in turn implies x^/x^=x∗/x∗. So, signx^=signx∗. This, together with (43), implies that(45)i:xi∗>0=S1,i:xi∗<0=S2,i:xi∗=0=S1∪S2c.
Sincex∗ is a solution of linear programming (39), then KKT conditions hold; i.e., there exist w=w1,w2,w3T∈ℝJ+×ℝJ−×ℝJ0 and h∈ℝl such that(46)η≔A+A−A0Tw+BTh∈∂x∗1,where ∂x∗1 is the subgradient of the l1-norm at x∗, i.e.,(47)∂x∗1=v∈ℝn:vi=1,forxi∗>0;vi=−1,forxi∗<0;vi≤1,otherwise.
Hence, (46) ensures that(48)ηi=1,forxi∗>0;ηi=−1,forxi∗<0;ηi≤1,forxi∗=0.
This together with (45) means that η=ATw+BTh satisfies (42). Since S1 and S2 are arbitrary disjoint subsets of 1,…,n with S1+S2≤k, we conclude that AT,BT satisfies the restricted weak RSP of order k with respect to y.
We now further show that the restricted weak RSP with respect toy is a sufficient condition for (3) to be stable. Firstly, for the approximation problem (33), let us introduce variables t,s to yield the following equivalent form:(49)minx,t,seTt,s.t.x+t≥0,−x+t≥0,−s≥−ε,MP0TBx+seN≥MP0Tb,A+x≥αeJ+,A−x≤−αeJ−,A0x=0,t,s≥0.
Recall that the solution set of (49) is given as (34). The above optimization problem is a linear programming problem, and the dual problem can be written as(50)maxw−εw3+bTMP0w4+αeJ+Tw5−αeJ−Tw6,s.t.w1−w2+BTMP0w4+A+Tw5+A−Tw6+A0Tw7=0,w1+w2≤e,−w3+eNTw4≤0,w1,w2∈ℝ+n,w3∈ℝ+,w4∈ℝ+N,w5,w6,w7∈ℝ+J+×ℝ−J−×ℝJ0.
According to the dual theory on linear programming, the solution of (49) can be characterized by KKT conditions.Lemma 2.
x∗ is a solution to the problem (33) if and only if x∗,t∗,s∗,w∗∈Θ, where(51)Θ≔x,t,s,w−x−t≤0,x−t≤0,s≤ε,−MP0TBx−seN≤−MP0Tb;−A+x≤−αeJ+,A−x≤−αeJ−,A0x=0;w1−w2+BTMP0w4+A+Tw5+A−Tw6+A0Tw7=0;w1+w2≤e,−w3+eNTw4≤0;eTt=−εw3+bTMP0w4+αeJ+Tw5−αeJ−Tw6;t,s≥0,wi≥0,i=1,…,5,w6≤0.For the convenience of notations, the set in (51) can be written equivalently as(52)Θ=z=x,t,s,wM′z≤p,M″z=q,wherep≔0,0,ε,−MP0Tb,−αeJ+,−αeJ−,e,0,0,0,0,0,0,0,0,0T,q≔0,0,0T,(53)M′≔D100D2D300D4,M″≔M∗,M∗∗,(54)D1≔−I−I0I−I0001−MP0TB0−eN−A+00A−00,D2≔II0000000−IeNT000,D3≔0−I000−I,D4≔−In0000000−In0000000−10000000−IN0000000−IJ+0000000IJ−0,M∗≔A0000000eT0,M∗∗≔0000000I−I0BTMP0A+TA−TA0T00ε−bTMP0−αeJ+TαeJ−T0.The following two lemmas play a key role to establish the stability theory on 1-bit CS problem.Lemma 3.
(Hoffman’s error bound). LetM′∈ℝm×q and M″∈ℝl×q be given matrices and(55)ℱ≔z∈ℝq:M′z≤p,M″z=q.For any vectorx in ℝq, there is a point x∗∈ℱ such that(56)x−x∗2≤σ∞,2M′,M″M′x−p+M″x−q1,where the constant σ∞,2M′,M″ is referred to as Robinson’s constant defined by M1 and M2.Hoffman’s error bound indicates that, for a linear systemℱ, the distance from a point in space to ℱ can be measured in terms of Robinson’s constant and quantity of the linear system being violated at this point.Lemma 4.
(see [25], Lemma 6.2.2). Given three convex compact sets T1,T2, and T3 satisfy T1⊆T2 and T3⊆T2, then(57)x−πT1x2≤dℋT1,T2+2x−z2,∀x∈ℝn,z∈T3.Inspired by [25, 26], we obtain the following result, which states that the restricted weak RSP with respect to y is a sufficient condition for the l1-minimization (3) to be stable in sparse vector recovery.Theorem 2.
Let the problem dataA,B,ε,b,y is given as (3) and rankA;B=m+l. Let ε′>0 be any prescribed small number, and let P0 be the polytope given in (29) satisfying (26). If CT=AT,BT satisfies the restricted weak RSP of order k with respect to y, then for any nonzero x∈ℝn, there is an optimal solution x∗ of (3) such that(58)xx2−x∗x∗22≤τxε′+2γ2σkx1+cBx−b1+Ax−αy1+ε+b−Bx2−ε++−A+x+αeJ++1+A−x+αeJ−+1+A0x1,where α>0 is sufficient small, c≔CCT−1C∞⟶1, γ≔σ∞,2M′,M′′ is the Robinson constant with M′,M″ given in (53), and(59)τx≔2x−x∗2,if0∈x,x∗,1dist0,x,x∗,if0∉x,x∗.
In particular, ifx is a feasible solution of (3), then there is an optimal solution x∗ of (1) such that(60)xx2−x∗x∗22≤τxε′+2γ2σkx1+cBx−b1+Ax−αy1+ε.Proof.
Letx∈ℝn be an arbitrary nonzero vector and P0 be the fixed polytope given in (29) satisfying (26) in Lemma 1. The proof is divided into the following four steps.Step 1.
t,s,w. The first step is to construct t,s,w. Constructing t,s. Let(61)t≔x,s≔MP0Tb−Bx∞.
The choice oft,s ensures(62)−x−t+=0,x−t+=0,MP0Tb−Bx−eNs+=0.
LetS be the support set of the k largest components of x. Define(63)S1≔i:xi>0,i∈S,S2≔i:xi<0,i∈S.
Clearly,S1∩S2=∅ and S=S1∪S2 with S1∪S2=S≤k. Let S3 be the complementary set of S. Hence, S1,S2, and S3 are disjoint. Since CT=AT,BT satisfies the restricted weak RSP of order k with respect to y, there exists a vector η∈RAT,BT such that(64)η=ATh∗+BTv∗for some h∗=h1∗,h2∗,h3∗T∈ℝ+J+×ℝ−J−×ℝJ0, v∗∈ℝl, and(65)ηi=1,fori∈S1,ηi=−1,fori∈S2,ηi≤1,fori∈S3.
Now, we construct a dual feasible solutionw=w1,…,w7.
Constructingw1,w2,w3. Set w1, w2, and w3 as follows:(66)w1i≔0,i∈S1,1,i∈S2,ηi−ηi2,i∈S3,w2i≔1,i∈S1,0,i∈S2,ηi+ηi2,i∈S3,w3≔v∗1.
Hence,w1,w2 satisfies(67)w1+w2≤e,w2−w1=η,w1,w2≥0.
Constructingw4. We assume, without loss of generality, that the first l columns in MP0 are βjj=1,…,l and the second l columns of MP0 are −βjj=1,…,l. The component of w4 is assigned as follows:(68)w4j≔vj∗,ifvj∗>0,j=1,…,l;w4j+l≔−vj∗,ifvj∗<0,j=1,…,l;w4j≔0,otherwise.
It follows from the choice ofw3andw4 that(69)MP0w4=v∗,w41=v∗1,w4≥0,(70)−w3+eNTw4+=−v∗1+eNTw4+=−v∗1+w41=0.
Constructingw5,w6,w7. Let w5,w6,w7≔h∗. Clearly, w5,w6,w7∈ℝ+J+×ℝ−J−×ℝJ0.
With the above choice ofw=w1,…,w7, it follows from (64)–(70) that(71)w1−w2+BTMP0w4+A+Tw5+A−Tw6+A0Tw7=0;w1+w2−e+=0,−w3+eNTw4+=0;t−=0,s−=0,wi−=0,i=1,…,5,w6+=0.Step 2.
Calculatingx−x¯2, where x¯ is a solution of (33) for α∈0,α˜, and α˜ satisfies Tβ∗⊆T∗ for all β∈0,α˜ as required in Corollary 1.
Define(72)Λ≔eTt+εw3−bTMP0w4−αeJ+Tw5+αeJ−Tw6,Υ≔s−ε+.
Forx,t,s,w where t,s,w is constructed as above, Lemma 3 ensures the existence of x¯,t¯,s¯,w¯∈Θ such that(73)xtsw−x¯t¯s¯w¯2≤γΛΥ−A+x+αeJ++A−x+αeJ−+A0xx−t+−x−t+MP0Tb−Bx−seN+w1+w2−e+−w3+eNTw4+w1−w2+BTMP0w4+A+Tw5+A−Tw6+A0Tw7t−,s−,w1−,w2−,w3−,w4−,w5−,w6+1,where γ≔σ∞,2M′,M″ is Robinson’s constant determined by M′,M″ given in (53). Since the vector x,t,s,w satisfies (62) and (71), the inequality (73) can be simplified to(74)x,t,s,w−x¯,t¯,s¯,w¯2≤γΛ+Υ+−A+x+αeJ++A−x+αeJ−+A0x1.
Since(75)max1≤i≤NMP0TBx−bi≤Bx−b2,we have s≤b−Bx2 by (61). Therefore,(76)Υ=s−ε+≤b−Bx2−ε+.
It follows from (69) that(77)Λ=eTt+εw3−bTv∗−αeJ+Th1∗+αeJ−Th2∗,=eTt+εw3−xTBTv∗+Bx−bTv∗−xTATh∗+Ax−αyTh∗,=eTt+εw3−xTη+Bx−bTv∗+Ax−αyTh∗,where the second step comes from the fact y=eJ+,−eJ−,0T and the last step uses the fact η=ATh∗+BTv∗ by (64). Hence,(78)Λ≤eTt−xTη+εw3+Bx−bTv∗+Ax−αyTh∗.
Firstly, we focus on each term of the right-hand side of the above inequality, respectively. Recall thatt=x. Therefore,(79)eTt−xTη=eSTtS+eS3TtS3−xSTηS−xS3TηS3=eS3TtS3−xS3TηS3≤eS3TtS3+xS3TηS3≤xS31+xS31ηS3∞≤xS31+xS31=2xS31=2σkx1,where the second equality is from (65). By using the restricted weak RSP of order k with respect to y, we have(80)maxv∗1,h∗1≤v∗h∗1=CCT−1Cη1≤CCT−1C∞⟶1η∞≤CCT−1C∞⟶1≕c.
Hence,(81)Bx−bTv∗≤Bx−b1v∗∞≤Bx−b1v∗1≤cBx−b1,Ax−αyTh∗≤Ax−αy1h∗∞≤Ax−αy1h∗1≤cAx−αy1,εw3=εv∗1≤cε.
It then follows from (78)–(81) that(82)Λ≤cε+2σkx1+cBx−b1+Ax−αy1,together with (74) and (76) implies(83)x−x¯2≤γ2σkx1+cBx−b1+Ax−αy1+ε+b−Bx2−ε++−A+x+αeJ++1+A−x+αeJ−+1+A0x1.Step 3.
Calculatingx−x∗2, where x∗ is a solution of (3). Recall three sets Tα∗,TαP0, and TαP0∗, where Tα∗ and TαP0∗ are the solution of (18) and (33) (cf. (24) and (34)) and TαP0 is given as (25) with P≔P0. Clearly, x¯∈TαP0∗. Let x∗ denote the projection of x onto T∗, i.e., x∗=πT∗x. Since Tα∗⊆TαP0 and TαP0∗⊆TαP0 by (35), applying Lemma 4 with T1≔Tα∗,T2≔TαP0 and T3≔TαP0∗, the definition of πTx and the fact Tα∗⊆T∗ by Corollary 1 yields(84)x−x∗2=x−πT∗x2≤x−πTα∗x2≤dℋTα∗,TαP0+2x−x¯2,which together with dℋTα∗,TαP0≤ε′ by Lemma 1 implies(85)x−x∗2≤ε′+2x−x¯2.
This combined with the inequality (83) gives(86)x−x∗2≤ε′+2γ2σkx1+cBx−b1+Ax−αy1+ε+b−Bx2−ε++−A+x+αeJ++1+A−x+αeJ−+1+A0x1.Step 4.
Calculatingx/x2−x∗/x∗2. Note first that x∗≠0 due to J+∪J−≠∅. Consider the following two cases:(i)
If0∈x,x∗, since x,x∗≠0, then x=αx∗ for some α≠0. Hence,(87)xx2−x∗x∗22=ax∗ax∗2−x∗x∗22≤2x−x∗2x−x∗2.(ii)
If0∉x,x∗, let fz≔z/z2 as z≠0. Then,(88)∇fz=I−z/z2z/z2Tz2,which implies ∇fz2=1/z2 since eigenvalues of I−z/z2z/z2T are 0 and 1 with multiplicity n−1. Thus,(89)fx−fx∗=∫01∇fx∗+tx−x∗x−x∗dt≤∫01∇fx∗+tx−x∗2x−x∗2dt≤1dist0,x,x∗x−x∗2,where the last inequality is due to the fact for any t∈0,1,(90)∇fx∗+tx−x∗2=1x∗+tx−x∗2≤1dist0,x,x∗.
Combining (87) and (89) together yields(91)xx2−x∗x∗22≤τxx−x∗2,where(92)τx≔2x−x∗2,if0∈x,x∗,1dist0,x,x∗,if0∉x,x∗.
This together with (86) results in (58).
Ifx is the feasible solution of (3), then b−Bx2−ε+=0 and(93)−A+x+αeJ++1=A−x+αeJ−+1=A0x1=0,as α>0 is sufficiently small, which further implies(94)xx2−x∗x∗22≤τxε′+2γ2σkx1+cBx−b1+Ax−αy1+ε.
We now further show that the restricted weak RSP with respect toy is also a sufficient condition for the l1-minimization problem if the noise does not exist, i.e., ε=0. It should be noticed that, in this case, the constraint Bx=b is linear, and hence, it is unnecessary to further introduce a polytope. Thus, the problem (3) and its relaxed problem (49) reduces to(95)minx1s.t.signAx=y,Bx=b,(96)minx,teTt,s.t.x+t≥0,−x+t≥0,A+x≥αeJ+,A−x≤−αeJ−,A0x=0,Bx=b,t≥0.
The dual problem is given as(97)maxwαeJ+Tw3−αeJ−Tw4+bTw6,s.t.w1−w2+A+Tw3+A−Tw4+A0Tw5+BTw6=0,w1+w2≤e,w1,w2≥0,w6∈ℝl,w3,w4,w5∈ℝ+J+×ℝ−J−×ℝJ0.
Similarly, according to the dual theory of linear programming,x∗ is a solution to the problem (96) if and only if there exists x∗,t∗,s∗,w∗∈Θ¯, where(98)Θ¯≔x,t,wx≤t,−x≤t,−A+x≤−αeJ+,A−x≤−αeJ−,A0x=0,Bx=b;w1−w2+A+Tw3+A−Tw4+A0Tw5+BTw6=0,w1+w2≤e;eTt=αeJ+Tw3−αeJ−Tw4+bTw6,w1,w2,t≥0,w3≥0,w4≤0.
The setΘ¯ can be written equivalently as(99)Θ¯=z=x,t,wM¯′z≤p¯,M¯′′z=q¯,where p¯≔0,0,−αeJ+,−αeJ−,e,0,0,0,0,0,, q¯≔0,b,0,0,(100)M¯′≔D¯100D¯2D¯300D¯4,M¯″≔M¯∗,M¯∗∗,(101)D¯1≔I−I−I−I−A+0A−0,D¯2≔II0000,D¯3≔0−I,D¯4≔−In000000−In000000−IJ+000000IJ−00,M¯∗≔A00B0000eT,M¯∗∗≔000000000000I−IA+TA−TA0TBT00−αeJ+αeJ−0−bT.
Following the similar argument as given in Theorem2, we can obtain the following result.Theorem 3.
Let the problem dataA,B,b,y is given as (95) and the matrix C=AT,BTT∈ℝm+l×n with full row rank. If CT=AT,BT satisfies the restricted weak RSP of order k with respect to y, then for any x∈ℝn, there is an optimal solution x∗ of (3) such that(102)xx2−x∗x∗22≤2γτx2σkx1+cAx−αy1+−A+x+αeJ++1+A−x+αeJ−+1+A0x1,where α>0 is sufficiently small, c≔CCT−1C∞⟶1, and γ≔σ∞,2M¯′,M¯′′ is the Robinson constant with M¯′,M¯′′ given in (100). In particular, if x is a feasible solution of (3), then there is an optimal solution x∗ of (3) such that(103)xx2−x∗x∗22≤2γτx2σkx1+cAx−αy1.The following result shows that the property of restricted weak RSP with respect toy is the mildest condition to ensure the stability of l1-minimization problem with any given measurement vector y=eJ+,−eJ−,0∈signAx:x0≤k.Corollary 2.
Let the problem dataA,B,b,y be given as (95) and C=AT,BTT∈ℝm+l×n be a matrix with full row rank. Then, the 1-bit CS problem(104)minx1s.t.A+x≥αeJ+,A−x≤−αeJ−,A0x=0,Bx=b,is stable for all y∈signAx:x0≤k if and only if CT satisfies restricted weak RSP of order k with respect to y.Proof.
Following the argument given in Theorem2, we know that the restricted weak RSP of order k of CT with respect to y is a sufficient condition for l1-minimization problem (104) to be stable.
On the contrary, Theorem1 claims that if the l1-minimization problem is stable for any given y∈signAx:x0≤k, then the matrix CT must satisfy the restricted weak RSP of the order k with respect to y.


## 4. Conclusions

In this paper, the stability theory for 1-bit CS with quadratic constraint is established. In the analysis, it is essential to use the duality theory of linear programming, Hoffman error bound, and the fact that the ball constraint via Euclidean norm can be approximated by polytopes to any level of accuracy. An interesting and challenging topic is to further study the stability theory for 1-bit CS with other norms, e.g.,p-norm, particularly as p∈0,1. In this case, the nonconvex structure of p-norm requires us to adopt the error bounded theory (also called metric subregularity) for nonlinear systems, instead of linear system used in this paper.



---

*Source: 8849395-2020-11-25.xml*