# Restrictedp-Isometry Properties of Partially Sparse Signal Recovery

Authors: Haini Bi; Lingchen Kong; Naihua Xiu
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

By generalizing the restrictedp-isometry property to the partially sparse signal recovery problem, we give a sufficient condition for exactly recovering partially sparse signal via the partial lp minimization (truncated lp minimization) problem with p∈(0,1]. Based on this, we establish a simpler sufficient condition which can show how the p-RIP bounds vary corresponding to different ps.


---

## Body

## 1. Introduction

The partially sparse signal recovery (PSSR) is the problem of recovering a partially sparse signal from a certain number of linear measurements when the part of the signal is known to be sparse, which was coined by Bandeira et al. [1, 2]. This type of problems has many applications in signal and image processing, derivative-free optimizations, and so on; see, for example, [1–4]. Clearly, PSSR includes sparse signal recovery (SSR) as a special case. The latter is the well-known NP-hard problem in the compressed sensing (CS), which is also called cardinality minimization problem (CMP, orl0-norm minimization problems); see, for example, [5–8]. In particular, Candés and Tao [8] introduced a restricted isometry property (RIP) of a sensing matrix which guarantees to recover a sparse solution of SSR by minimizing its convex relaxation (ℓ1-norm minimization). However, there are some problems which cannot be reformulated as an SSR, but a PSSR. As we know, PSSR happens naturally in sparse Hessian recovery; see, for example, [2], where Bandeira et al. employed partially sparse recovery approach for building sparse quadratic interpolation models of functions with sparse Hessian. They have successfully applied the ℓ1-norm minimization of PSSR in interpolation-based trust-region methods for derivative-free optimization. Vaswani and Lu [3] successfully applied modified CS (partially sparse recovery) in image reconstruction, where the sufficient RIP condition is weaker than the RIP for SSR. Moreover, Bandeira et al. [1] considered the RIP and null space properties (NSP) for PSSR and extended recovery results under noisy measurements to the partially sparse case, where partial NSP is a necessary and sufficient condition for PSSR. In [4], Jacques also established the partial RIP condition for PSSR with noise via its convex relaxation problem.Note that in the CS context, the SSR problem can also be relaxed to alp-norm minimization (truncated lp-minimization) problem with 0<p<1; see, for example, [9–19]. It is well known that Chartrand [20] firstly show that fewer measurements are required for exact reconstruction if we replace l1-norm with lp-norm (0<p<1), and Chartrand and Staneva [10] established p-RIP conditions for exact SSR via lp-minimization. In particular, the numerical experiments in magnetic resonance imaging (MRI) showed that this approach works very efficiently; see [9] for details. Wang et al. [19] studied the performance of lp-minimization for strong recovery and weak recovery where we need to recover all the sparse vectors on one support with one sign pattern. Moreover, Saab et al. [16] provided a sufficient condition for SSR via lp-minimization and provided a lower bound of the support size up to which lp-minimization can recover all such sparse vectors, and Foucart and Lai [14] improved this bound by considering a generalized version of RIP condition. While SSR and lp-minimization have been the focus point of some recent research, there are fewer research related to PSSR and the partially lp-minimization. One may naturally wonder whether we can generalize the p-RIP conditions introduced by [10] from the SSR to the PSSR case. This paper will deal with this issue. We will give a different p-RIP recovery condition for PSSR via its nonconvex relaxation. Furthermore, based on the recent work by Oymak et al. [21], we also extend our result to the matrix setting.In the next section, we give the PSSR model and review some preliminaries onp-RIP conditions. In Section 3, we establish the exact partially p-RIP recovery conditions for PSSR via its nonconvex lp-minimization. In Section 4, we give a sufficient condition for partially low-rank matrix recovery via the partially Schatten-p minimization problem.


## 2. Preliminaries

In this section, we will review some basic concepts and results on thep-RIP recovery conditions for SSR and introduce the p-RIP definition for PSSR. We begin with defining the mathematical model of the PSSR problem as follows:
(1)min∥x∥0,s.t.A1x+A2y=b,
where the l0-norm ∥x∥0 is defined as ∥x∥0:=|{i:xi≠0}| (which is not really a norm since it is not positive homogeneous). For any positive number s, we say x is s-sparse if ∥x∥0≤s. A=[A1,A2]∈ℝM×N is a sensing matrix with A1∈ℝM×(N-r),  A2∈ℝM×r, and b∈ℝM. It means that the unknown vector consists of two parts (x,y), where x∈ℝN-r is sparse and y∈ℝr is possibly dense. When A=A1, the previous problem reduces to the following l0-norm minimization problem (sparse signal recovery, SSR):
(2)min∥x∥0,s.t.Ax=b.
The previous PSSR problem (1) is an NP-hard problem, since its special case SSR (2) is well-known NP-hard problem in the compressed sensing (CS). As we mentioned in Section 1, one popular and powerful approach is to solve it via ℓ1-norm minimization (its convex relaxation), where the l0-norm is replaced by the l1-norm in SSR (2). Moreover, we can also use a nonconvex approach for exact reconstruction with fewer measurements than the convex relaxation; see, for example, [9, 10]. That is the lp-norm minimization problem with 0<p<1, where we replace the l0-norm with the lp-norm in (2) as follows:
(3)min∥x∥pp,s.t.Ax=b.
Note that ∥·∥p is not a norm when p∈(0,1), but it is much close to l0-norm. Moreover, the numerical experiments in MRI showed that the approach via lp-minimization works very efficiently; see [9] for details. In particular, Chartrand and Staneva [10] introduced the concept of restricted isometry constant via lp-norm.Definition 1 (p-RIC [10]).
Given a matrixA∈ℝM×N, where M<N, s is a positive number and 0<p<1, then we say that δs is the restricted p-isometry constant (or p-RIC) of order s of the matrix A if δs is the smallest number, such that
(4)(1-δs)∥x∥2p≤∥Ax∥pp≤(1+δs)∥x∥2p,
for all s-sparse vectors x.In the same paper, Chartrand and Staneva gave the following sufficient condition for exact SSR vialp-minimization.Theorem 2 (see [10]).
LetA∈ℝM×N, x∈ℝN, and k=∥x∥0 be the size of the support of x, 0<p<1, a1>1, and a2=a12/(2-p), rounded up, so that a2k is an integer (a2=⌈a12/(2-p)k⌉/k). If A satisfies
(5)δa2k+a1δ(a2+1)k<a1-1,
then x is the unique minimizer of problem (2).Inspired by the previous analysis, it is natural to give the partiallylp-norm minimization problem for PSSR (1) as follows:
(6)min∥x∥pp,s.t.A1x+A2y=b.
In order to establish the link between the PSSR (1) and its partially lp-norm minimization problem, we need to give a partially p-RIC definition. Here we borrow the idea from Bandeira et al. [1]. Assume that A2 is full column rank. For A=[A1,A2] as mentioned above, let
(7)B:=I-A2(A2TA2)-1A2T,
which is the matrix of the orthogonal projection from ℝN to ℜ(A2)⊥.Definition 3 (Partiallyp-RIC).
LetA=[A1,A2]∈ℝM×N, where A1∈ℝM×(N-r), and A2∈ℝM×r is full column rank. We say that δs-rr is the Partially Restricted Isometry Constant (Partially p-RIC) of order s-r of the matrix A if δs-rr is the p-RIC of order s-r of the matrix BA1; that is, δs-rr is the smallest number, such that
(8)(1-δs-rr)∥x∥2p≤∥BA1x∥pp≤(1+δs-rr)∥x∥2p,
for all (s-r)-sparse vectors x, where B is given by (7).


## 3. Main Results

We will give our main results which state sufficientp-RIP recovery conditions on the exact PSSR via the nonconvex lp-norm minimization. We begin with the following useful lemma.Lemma 4.
For0<p≤1, let c1=a11-p/2 and c2=a21-p/2 with a1>0 and a2>0. If (c1-1)/c2>|a1-a2|/a2, then a1>1 and a2>1.Proof.
In order to prove the lemma, we consider the following two cases.
Case  1(a1≥a2). In this case, from the fact (c1-1)/c2>|a1-a2|/a2, we have
(9)a1a2-(a1a2)1-p/2<1-(1a2)1-p/2.
If 0<a2≤1, from the previous inequality we easily obtain
(10)0<a1a2-(a1a2)1-p/2<1-(1a2)1-p/2≤0,
which is a contradiction. Hence a1≥a2>1.
Case  2(a1<a2). Similarly, in this case, from (c1-1)/c2>|a1-a2|/a2, we obtain
(11)0<1-a1a2<c1-1c2.
If 0<a1≤1, then
(12)c1=a11-p/2≤1.
Combining the previous inequalities we obtain
(13)0<1-a1a2<c1-1c2≤0,
which is a contradiction. Hence 1<a1<a2.
Therefore, taking into account the previous two cases, we completed the proof.We below propose a general recovery condition for PSSR via itsp-norm minimization.Theorem 5.
LetA=[A1,A2]∈ℝM×N with A1∈ℝM×(N-r) and A2∈ℝM×r. Suppose that A2 is full column rank, and let A1x+A2y=b with ∥x∥0=k. For 0<p≤1, a1>0, and a2>0, let c1=a11-p/2, c2=a21-p/2 with (c1-1)/c2>|a1-a2|/a2. If
(14)a2c1δ(a2+1)k+(|a1-a2|c2+a2)δa1k<a2c1-|a1-a2|c2-a2,
then (x,y) is the unique minimizer of problem(6)Proof.
Note that(x,y) is a feasible solution to optimization problem (6). We remain to show that the solution set is a singleton {(x,y)}. This proof generally modifies that of [10], but under different assumptions. (Specifically, we use a different way to arrange the elements of T0C in the following.) Let (u,v) be an arbitrary solution to problem (6). we will show that u=x and y=v. We will prove u=x firstly. Taking h=u-x, we will show that h=0. Let Φ=BA1. For T∈{1,…,N-r}, ΦT denotes the matrix equaling Φ in those columns whose indices belong to T and otherwise zero. Similarly, we define the vector hT. Let T0 be the support of x. Then, the supports of x and hT0C are disjoint since T0⋂‍T0C=∅. From direct calculation, we obtain
(15)∥x∥pp≥∥u∥pp=∥x+h∥pp=∥x+hT0+hT0C∥pp=∥x+hT0∥pp+∥hT0C∥pp≥∥x∥pp-∥hT0∥pp+∥hT0C∥pp,
where the first inequality holds because (u,v) solves (6), and the last one holds by the triangle inequality for ∥·∥pp. Then we have
(16)∥hT0C∥pp≤∥hT0∥pp.
Now we arrange the elements ofT0C in order of decreasing magnitude of |h| and partition into T0C=T1⋃‍T2⋃‍⋯⋃‍TJ, where T1 has a2k elements and Tj  (j≥2) each has a1k elements (except possibly TJ). Set T01=T0⋃‍T1. Note that
(17)BA2=[I-A2(A2TA2)-1A2T]A2=0.
Direct calculations yield
(18)0=∥B(A1x+A2y-A1u-A2v)∥pp=∥BA1x-BA1u∥pp=∥Φx-Φu∥pp=∥Φh∥pp=∥ΦhT01+∑j≥2‍ΦhTj∥pp≥∥ΦhT01∥pp-∥∑j≥2‍ΦhTj∥pp≥∥ΦhT01∥pp-∑j≥2‍∥ΦhTj∥pp≥(1-δ(a2+1)k)∥hT01∥2p-(1+δa1k)×∑j≥2‍∥hTj∥2p.
Now we discuss the relation between l2-norm and lp-norm. For each t∈Tj and s∈Tj-1, it holds |ht|≤|hs|. So, we have for j=2,(19)|ht|p≤∥hT1∥ppa2k⟹|ht|2≤∥hT1∥p2(a2k)2/p⟹∥hT2∥22a1k≤∥hT1∥p2(a2k)2/p⟹∥hT2∥2p≤ap/2a2k1-p/2∥hT1∥pp.
Similarly, we obtain that for j≥3,
(20)∥hTj∥2p≤1(a1k)1-p/2∥hTj-1∥pp.
Applying the Holder's inequality, we obtain
(21)∥hT0∥pp=∑t∈T0‍|ht|p·1≤(∑t∈T0‍|ht|2)p/2(∑t∈T0‍1)1-p/2=∥hT0∥2p·k1-p/2.
Similarly, we have
(22)∥hT1∥pp≤∥hT1∥2p·(a2k)1-p/2.
Therefore,
(23)∑j≥2‍∥hTj∥2p≤a1p/2a2k1-p/2∥hT1∥pp+1(a1k)1-p/2∑j≥2‍∥hTj∥pp(By(19)and(20))=1(a1k)1-p/2∑j≥1‍∥hTj∥pp+(a1-a2)a1p/2a1a2k1-p/2∥hT1∥pp=1(a1k)1-p/2∥hT0C∥pp+(a1-a2)a1p/2a1a2k1-p/2∥hT1∥pp≤1(a1k)1-p/2∥hT0∥pp+(a1-a2)a1p/2a1a2k1-p/2∥hT1∥pp(By(16))≤k1-p/2(a1k)1-p/2∥hT0∥2p+(a1-a2)(a2k)1-p/2a2(a1k)1-p/2∥hT1∥2p(By(21)and(22))=1c1∥hT0∥2p+(a1-a2)c2a2c1∥hT1∥2p≤1c1∥hT0∥2p+|a1-a2|c2a2c1∥hT1∥2p≤1c1∥hT01∥2p+|a1-a2|c2a2c1∥hT01∥2p.
Thus by (18) and (23), we have
(24)0≥(1-δ(a2+1)k)∥hT01∥2p-(1+δa1k)∑j≥2‍∥hTj∥2p(By(18))≥(1-δ(a2+1)k)∥hT01∥2p-1+δa1kc1∥hT01∥2p-|a1-a2|c2(1+δa1k)a2c1∥hT01∥2p(By(23))=[1-δ(a2+1)k-1+δa1kc1-|a1-a2|c2(1+δa1k)a2c1]×∥hT01∥2p.
Clearly, the assumption ensures that the scalar factor is positive, and hence we obtain hT01=0. That means hT0=0. Using ∥hT0C∥pp≤∥hT0∥pp, we obtain hT0C=0. Therefore, h=0, which means x=u.
Now we remain to show thaty=v. It is obvious that A1x+A2y=A1u+A2v. Since x=u, we have A2(y-v)=0. Then y=v because A2 is full column rank.Theorem5 states a different sufficient condition for the exactly PSSR via its nonconvex relaxation from the existing conditions for SSR.Theorem 6.
LetA=[A1,A2]∈ℝM×N with A1∈ℝM×(N-r) and A2∈ℝM×r. Suppose that A2 is full column rank, and let A1x+A2y=b with ∥x∥0=k. For 0<p≤1 and a>1, if
(25)δ(a+1)k<a1-p/2-1a1-p/2+1,
then (x,y) is the unique minimizer of problem (6). Specifically, for all 0<p≤1, if
(26)δ(a+1)k<a-1a+1,
then (x,y) is the unique minimizer of problem (6).Proof.
Applying Theorem5, here we only need to show that if (25) holds, we can find a1 and a2, such that (14) holds. We consider the three cases in the following.
Case  i(a1≥a2+1). In this case, we easily obtain a1-a2≥1 and δa1k≥δ(a2+1)k. Therefore the following condition can guarantee the inequality (14):
(27)a2c1δa1k+[(a1-a2)c2+a2]δa1k<a2(c1+c2-1)-a1c2.
Simplifying the previous inequality, we obtain
(28)δa1k<a2c1-(a1-a2)c2-a2a2c1+(a1-a2)c2+a2=a11-p/2-(a1-a2)a2-p/2-1a11-p/2+(a1-a2)a2-p/2+1.
In this case, employing a2-p/2>0, we easily get that a1=a2+1 gives the maximum value of the right of the inequality (the strongest result) which satisfies the condition (14). That is,
(29)δ(a2+1)k<(a2+1)1-p/2-a2-p/2-1(a2+1)1-p/2+a2-p/2+1.
Case  ii(a2≤a1<a2+1). In this case, we can get that 0≤a1-a2<1 and δa1k<δ(a2+1)k. Similarly, the following condition can guarantee the inequality (14):
(30)a2c1δ(a2+1)k+[(a1-a2)c2+a2]δ(a2+1)k<a2(c1+c2-1)-a1c2.
Simplifying the previous inequality, we obtain
(31)δ(a2+1)k<a11-p/2-(a1-a2)a2-p/2-1a11-p/2+(a1-a2)a2-p/2+1.
In this case, employing a2-p/2>0, we get that a1=a2 give the maximum value of the right of the inequality; that is,
(32)δ(a2+1)k<a21-p/2-1a21-p/2+1.
Case  iii(a1<a2). In this case, it is clear that 0<a2-a1, a1<a2+1, and δa1k<δ(a2+1)k. So the following condition can guarantee the inequality (14):
(33)a2c1δ(a2+1)k+[(a2-a1)c2+a2]δ(a2+1)k<a2(c1-c2-1)+a1c2.
Simplifying the previous inequality, we obtain
(34)δ(a2+1)k<a11-p/2-(a2-a1)a2-p/2-1a11-p/2+(a2-a1)a2-p/2+1.
In this case, employing a2-p/2>0, we chose a2-a1→0 to give the maximum value of the right of the inequality. That is,
(35)δ(a2+1)k<a21-p/2-1a21-p/2+1.
It is easy to see that((a2+1)1-p/2-a2-p/2-1)/((a2+1)1-p/2+a2-p/2+1)<(a21-p/2-1)/(a11-p/2+1). In fact, (a2+1)1-p/2+a2-p/2+1>a21-p/2+1. On the other hand, (a2+1)1-p/2-a2-p/2-1-(a21-p/2-1)=(a2+1)[(a2+1)-p/2-a2-p/2]<0, which means (a2+1)1-p/2-a2-p/2-1<a21-p/2-1.
Therefore, combining the previous three cases, we obtain that one can choosea1=a2 to get the weakest sufficient condition. It is easy to see that a1=a2 satisfying the assumptions of Theorem 5.
After the previous discussion, using condition (25) and choosing a1=a2=a, we can derive condition (14).
Specifically, we consider the following function:(36)f(p)=a1-p/2-1a1-p/2+1=1-2a1-p/2+1.
Clearly,
(37)f′(p)=-a1-p/2lna(a1-p/2+1)2<0,
and hence f(p) is a decreasing function of p. Thus, for all 0<p≤1, condition
(38)δ(a+1)k<a-1a+1
can guarantee condition (14).
The proof is completed.Applying Theorem6, we understand how the p-RIP bounds related to p as in Figure 1. From Figure 1, it is easy to give a stronger result (i.e., weaker sufficient condition) for smaller p. Moreover, by taking different values of p with p=1/4,1/2,3/4, we obtain some interesting p-RIP bounds as in Table 1.Table 1
Bounds comparison on different values ofp.
p
=
1
4
0.1756
0.2943
0.3807
0.4468
0.4991
0.5417
p
=
1
2
0.1509
0.2542
0.3307
0.3902
0.4380
0.4776
p
=
3
4
0.1260
0.2133
0.2788
0.3304
0.3726
0.4080
p
=
1
0.1010
0.1716
0.2251
0.2679
0.3033
0.3333Figure 1
The upper bound ofp-RIC of order (a+1)k with particular values of p.


## 4. Final Remark

In this paper, we studied the restrictedp-isometry property to the partially sparse signal recovery problem and proposed a sufficient p-RIP condition for exactly recovering partially sparse signal via the partially lp-minimization problem with p∈(0,1]. It is worth generalizing the p-RIP condition from the vector case to the matrix case. Note that the well-known low-rank matrix recovery (LMR) problem has many applications and appeared in the literature of a diverse set of fields including matrix completion, quantum state tomography, face recognition, magnetic resonance imaging (MRI), computer vision, and system identification and control; see, for example, [21, 22] for more details and the reference therein. In particular, Oymak et al. [21] showed that several sufficient RIP recovery conditions for k sparse vector are also sufficient for recovery of matrices of rank up to 2k via Schatten p-norm minimization. According to our approach to extend the p-RIP bound from SSP to partially SSR, we can obtain some different restricted p-isometry properties for LMR problem by using the idea in [21].



---

*Source: 692169-2013-03-26.xml*