Journal of Applied Sciences

Year: 2014 | Volume: 14 | Issue: 19 | Page No.: 2292-2298
DOI: 10.3923/jas.2014.2292.2298

Some Bounds and Conditional Maximum Bounds for RIC in Compressed Sensing

Shiqing Wang, Yan Shi and Limin Su

Abstract: Compressed sensing seeks to recover an unknown sparse signal with p entries by making far fewer than p measurements. The Restricted Isometry Constants (RIC) has become a dominant tool used for such cases since if RIC satisfies some bound then sparse signals are guaranteed to be recovered exactly when no noise is present and sparse signals can be estimated stably in the noisy case. During the last few years, a great deal of attention has been focused on bounds of RIC. Finding bounds of RIC has theoretical and applied significance. In this study we obtain a bound of RIC. It improves the results. Further we discuss the problems related larger bound of RIC and give the conditional maximum bound.

Keywords: Compressed sensing, L1 minimization, restricted isometry property and sparse signal recovery

INTRODUCTION

Compressed sensing aims to recover high-dimensional sparse signals based on considerably fewer linear measurements. We consider:

where the matrix with n<<p, zε is a vector of measurement errors and the unknown signal βε . Our goal is to reconstruct β based on y and Φ.

A naive approach for solving this problem is to consider L₀ minimization where the goal is to find the sparsest solution in the feasible set of possible solutions. However, this is NP hard and thus is computationally infeasible. It is then natural to consider the method of L₁ minimization which can be viewed as a convex relaxation of L₀ minimization. The L₁ minimization method in this context is:

This method has been successfully used as an effective way for reconstructing a sparse signal in many settings. (Donoho and Huo, 2001; Donoho, 2006; Candes and Tao, 2005; Candes et al., 2006; Candes and Tao, 2006, 2007; Cai et al., 2010a, b).

Recovery of high dimensional sparse signals is closely connected with Lasso and Dantzig selectors, (Candes and Tao, 2007; Bickel et al., 2009; Wang and Su, 2013a-c). One of the most commonly used frameworks for sparse recovery via L₁ minimization is the Restricted Isometry Property (RIP) with a RIC introduced by Candes and Tao (2005). It has been shown that L₁ minimization can recover a sparse signal with a small or zero error under various conditions on δ_k and θ_{k, k}. For example, the condition δ_k+θ_{k, k}+θ_{k, 2k}<1 is used in (Candes and Tao, 2005), δ_3k+3δ_4k<2 in (Candes et al., 2006), δ_2k+θ_{k, 2k}<1 in (Candes and Tao, 2007), δ_1.5k+θ_{k, 1.5k}<1 in (Cai et al., 2009) and δ_1.25k+θ_{k, 1.25k}<1 in (Cai et al., 2010b).

The RIP conditions are difficult to verify for a given matrix Φ. A widely used technique for avoiding checking the RIP directly is to generate the matrix Φ randomly and to show that the resulting random matrix satisfies the RIP with high probability using the well-known Johnson-Lindenstrauss Lemma. (Baraniuk et al., 2008). This is typically done for conditions involving only the restricted isometry constant δ. Attention has been focused on δ_2k as it is obviously necessary to have δ_2k<1 for model identifiability. In a recent study, Davies and Gribonval (2009) constructed examples which showed that if δ_2k≥0.7071, exact recovery of certain k sparse signal can fail in the noiseless case. On the other hand, sufficient conditions on δ_2k has been given. For example, δ_2k<0.4142 is used in (Candes, 2008), δ_2k <0.4531 in (Foucart and Lai, 2009), δ_2k <0.4652 in (Foucart, 2010), δ_2k<0.4721 in (Cai et al., 2010b), δ_2k <0.4734 in (Foucart, 2010) and δ_2k <0.4931 in (Mo and Li, 2011). Some sufficient conditions on δ_k has been given. For example, δ_k<0.307 is used in (Cai et al., 2010c) and δ_k <0.308 in Ji and Peng, (2012) when k is even. In this study, δ_k <0.308 is given for any k and the conditional maximum bound δ_k <0.5 is obtained.

There are several benefits for improving the bound on δ_k. Firstly, it allows more measurement matrices to be used in compressed sensing. Secondly, for the same matrix Φ, it allows k to be larger, that is, it allows recovering a sparse signal with more nonzero elements. Furthermore, it gives better error estimation in a general problem to recover noisy compressible signals.

PRELIMINARIES

Let ||u||₀ be the number of nonzero elements of vector u = (u_i)εR^p. u is called k-sparse if ||u||₀≤k. For an nxp matrix Φ and an integer k,1≤k≤p, the k restricted isometry constant δ_k(Φ) is the smallest constant such that:

for every k-sparse vector u. If k+k'≤p, the k, k' restricted orthogonality constant δ_{k, k'}(Φ), is the smallest number that satisfies:

for all u and u' such that u and u' are k-sparse and k'-sparse, respectively and have disjoint supports. For notational simplicity we shall write δ_k for δ_k(Φ) and θ_k,k' for θ_k,k'(Φ) hereafter.

The following monotone properties can be easily checked:

Candes and Tao (2005) showed that the constants and are related by the following inequalities:

Cai et al. (2010b) showed that for any a≥1 and positive integers k, k' such than ak' is an integer, then:

Cai et al. (2010c) showed that for any xε:

Where:

NEW RIC BOUNDS OF COMPRESSED SENSING MATRICES

In this section, we consider new RIP conditions for sparse signal recovery. Suppose:

y = Φβ+z

with ||z||₂≤ε. Denote the solution of the following L₁ minimization problem:

The following is one of our main results of the study.

Theorem 1:Suppose β is k sparse with k>1. Then under the condition:

δ_k<0.308

the constrained L₁ minimizer given in (10) satisfies:

In particular, in the noiseless case recovers β exactly.

This theorem improves δ_k<0.307 in (Cai et al., 2010c) to δ_k<0.308 and k is even in (Ji and Peng, 2012) to any k. The proof of the theorem is very long but elementary.

Proof: Let s, k be positive integers, 1≤s<k and:

Then from Theorem 3.1 in (Cai et al., 2010c), under the condition δ_k+tθ_{k, s}<1, we have:

By (8):

We show below that:

Where:

The proof is of elementary trigonometric functions, but it is very clever.

So:

It is easy to see f(x) is increasing when:

and decreasing when:

Thus f(x) obtains the minimum value:

That is, if k ≡ 0(mod9), let:

then under the condition δ_k<0.309 we have, see (Cai et al., 2010c):

If k is even, let , then:

If k≥9 is odd, let , then:

since f(x) is increasing when:

When k = 7, then:

When k = 5, then:

When k = 3, we note from the remark of Theorem 3.1 in (Cai et al., 2010c) that in these cases s = 1and , then:

From (11-18) yield:

if k is even and:

if k is odd. With the above relations we can also get:

Corollary 1: Suppose β is k sparse with k ≡ 0(mod9). Then under the condition δ_k<0.309 the constrained L₁ minimizer given in (10) satisfies:

In particular, in the noiseless case recovers β exactly.

The proof sees (11-13):

Corollary 2: Suppose β is k sparse. If k≥9 is odd, then under the condition δ_k<c_k the constrained L₁ minimizer given in (10) satisfies:

Where:

In particular, in the noiseless case recovers β exactly. The proof sees (11-12) and (15). Note that 0.308<c_k≤0.309 from (15).

To the best of our knowledge, this seems to be the first result for sparse recovery with conditions that only involve δ_k and k. In fact, only involving δ_k, k and only involving δ_k are equivalent.

THE CONDITIONAL MAXIMUM BOUND FOR RIC

Let h = -β. For any subset Q⊂{1, 2, ..., p} we define h_Q = hI_Q, where I_Q denotes the indicator function of the set Q, i.e., I_Q(j) = 1 if j∈Q and 0 if j∉Q. Let T be the index set of the k largest elements (in absolute value) and let Ω be the support of β. The following fact which is based on the minimality of , has been widely used (Candes et al., 2006):

We shall show that:

In fact:

and T has the k largest elements (in absolute value) and Ω has at most k elements, so we have by (19):

And:

Definition 1: Let T_m be the index set of the m largest elements (in absolute value). The set T_m is called a sparse index set, if:

and m≤k.

It is obvious that the sparse index set exists. In fact T_k is a sparse index set since:

Here we prove that any sparse index set T_m instead of T_k , Theorem 3.1 in (Cai et al., 2010c) can be improved.

Theorem 2: Suppose β is k-sparse and T_m is sparse index set. Let k₁, k₂, be positive integers such that k₁≥m and 8(k₁-m)≤k₂. Let:

Then under the condition δ_k1+tθk₁, k₂<1 the L₁ minimizer defined in (10) satisfies:

In particular, in the noiseless case where y = Φβ, L₁ minimization recovers β exactly.

Proof: For any sparse index set T_m, let S₀eT_m be the index set of the k₁ largest elements (in absolute value). Rearrange the indices of S^c₀ if necessary according to the descending order of ,. Partition S^c₀ into:

where , the last S_i satisfies . If , then the theorem is trivially true. So here we assume that . Then it follows from (9) that:

Now:

Note that:

Also the next relation:

implies:

Putting them together we get:

If let m = k, then Theorem 2 is Theorem 3.1 in (Cai et al., 2010c).

Let m₀≤m be smallest positive integer so that:

Then we have.

Theorem 3: Suppose β is k-sparse. Let k₁, k₂ be positive integers such that k₁≥k≥m₀ and 8(k₁-m₀)≤k₂. Let:

Then under the condition δ_k+tθ_{k1, k2} <1 the L₁ minimizer defined in (10) satisfies:

In particular, in the noiseless case where y = Φβ, L₁ minimization recovers β exactly.

The proof is similar to of Theorem 2.

Note that k is independent of h, but m and m₀ are dependent of h, i.e., m = m(h) and m₀ = m₀(h).

The following is one of our main results of the study. It is the consequence of Theorem 2.

Theorem 4: Suppose β is k sparse with k>1. If k ≡ 0(mod 5) and T_k/5 is sparse index set, then under the condition δ_k<0.5 the constrained L₁ minimizer given in (10) satisfies:

In particular, in the noiseless case recovers β exactly.

Proof: If k ≡ 0(mod 5) and T_k/5 is sparse index set, then in Theorem 2, set:

Thus:

Then under the condition:

we have:

By (5) and (7) we get:

In this case:

An explicitly example in (Cai et al., 2010c) is constructed in which δ_k<0.5, but it is impossible to recover certain k sparse signals. Therefore, the bound for δ_k cannot go beyond 0.5 in general in order to guarantee stable recovery of k sparse signals.

CONCLUSION

We recognized that ||h_T||₁ may be greater than ||h_Ω||₁ too much. Since ||h_Ts||₁ (1≤s≤k) all may be greater than ||h_Ω||₁ and ||h_T||₁ is the largest of ||h_Ts||₁ (1≤s≤k). We want to find a ||h_T0|| (1≤s₀≤k) such that ||h_Ω||₁≤||h_T0|||₁. On the other hand, the bound in (11) is function of δ_k. This makes the bound cannot more tight since δ_k is fixed. So we propose an idea. That is, the bound in right side hand is function of δs, where s≤k. From Ω and T immediately deduce four index sets Ω^c∩T, Ω∩T, Ω∩T^c and Ω^c∩T^c and m₁=|Ω^c∩T| = k-|Ω∩T|, m₂ = |Ω∩T|, m₃ = |Ω∩T^c| ≤k-|Ω∩T|.

It is easy to show that the bound of Theorem 2 is tighter than the one in (Cai et al., 2010c) under special cases. See the following examples.

Example 1: Suppose β is k-sparse and n≥0. Let:

If Ω = T_q, then under the condition δ_q+t₃θ_{q, n}<1 the L₁ minimizer defined in (10) satisfies:

In particular, in the noiseless case where y = Φβ, L₁ minimization recovers β exactly.

In fact, the proof is similar to of Theorem 2 and note that:

Example 2: Suppose β is k-sparse and n≥0, where k is even. Let:

If |Ω∩T| = k/2, then under the condition:

the L₁ minimizer defined in (10) satisfies:

The proof is similar to of Theorem 2.

REFERENCES