# Improved Bounds for Restricted Isometry Constants

Authors: Jiabing Ji; Jigen Peng
Journal: Discrete Dynamics in Nature and Society
 (2012)

---

## Abstract

The purpose of this paper is to establish improved bounds for restricted
isometry constantsδk. Our results, to some extent, improve and extend the well-known bound (δk<0.307) in (Cai et al., 2010) to δk<0.308.


---

## Body

## 1. Introduction

Consider the following equation:(1.1)y=Aβ+z,
where the matrix A∈ℝn×m(n<m) and z∈ℝn is a vector of measurement errors. If z=0, then (1.1) is an underdetermined linear system with fewer equations than unknowns. The task is to reconstruct the signal β∈ℝm based on the matrix A and the vector y. Usually, we consider ℓ0 minimization problem:
(1.2)min⁡β^∈Rn‖β^‖0,subjecttoy=Aβ^+zand‖z‖2≤ϵ,
where ∥·∥0 denotes the ℓ0-norm of a vector, that is, the number of its nonzero components.We need to solve this problem and find the sparsest solution among all the possible solutions. But it requires a combinatorial search and remains an NP-hard problem that cannot be solved in practice. Naturally, an alternative strategy is to findℓ1 minimization problem:
(1.3)min⁡β^∈Rn‖β^‖1,subjecttoy=Aβ^+zand‖z‖2≤ϵ,
and we expect to find the sparsest solution.In order to exactly recover the sparsest solution inℓ1 minimization, Candès and Tao [1] introduced restricted isometry property (see Restricted Isometry Constants in Definition 2.1). So far, there are various methods [1–9] to give the sufficient conditions on δ2k: Candès [3] established that δ2k<2-1≈0.4142 is the sufficient condition of exactly recover k-sparse vectors via ℓ1 minimization (a vector x is k-sparse if ∥x∥0≤k). This sufficient condition was later improved to δ2k<2(3-2)/7≈0.4531 in [6] and to δ2k<3/(4+6)≈0.4652 in [5]. Later, the sufficient condition was improved to δ2k<1/(1+1.25)≈0.4721 in [10] for the special case that k is a multiple of 4 or k is very large and to δ2k<4/(6+6)≈0.4734 in [5]. Naturally, we want to give the sufficient condition about δk. To the best of our knowledge, T. T. Cai et al. [2] firstly show that the restricted isometry constant δk of A satisfies δk<0.307 for general k, then k-sparse signals are guaranteed to be recovered exactly via ℓ1 minimization. Based on this motivation, we construct a different partition of {1,2,…,m} and then discuss the error between original signal β and recover signal β^ in (1.3). The main work of this paper is to improve the condition to δk<0.308 and to prove that the k-sparse signals can be recovered exactly via ℓ1 minimization in no noise case and be estimated stably under the perturbation of noise.To state our main results, we firstly give the following preliminaries.


## 2. Preliminaries

In 2005, Candès and Tao [1] firstly present the definition of the restricted isometry constant.Definition 2.1 (see [1], restricted isometry constants).
LetF be the matrix with finite collection of vectors (vj)j∈J∈ℝn as columns. For every integer 1≤S≤|J|, the S-restricted isometry constants δS are defined as the smallest quantity such that FT obeys
(2.1)(1-δS)‖c‖22≤‖FTc‖22≤(1+δS)‖c‖22
for all subsets T⊂J of cardinality at most S and all real coefficients (cj)j∈T. Similarly, we define the S,S'-restricted orthogonality constants θS,S′ for S+S′≤|J| to be the smallest quantity such that
(2.2)|〈FTc,FT′c′〉|≤θS,S′‖c‖2⋅‖c′‖2
holds for all disjoint sets T,T′⊆J of cardinality |T|≤S and |T′|≤S′.
In addition, we can easily check the following monotone properties:(2.3)δk≤δk1,ifk≤k1≤n,θk,k′≤θk1,k1′,ifk≤k1,k′≤k1′,k1+k1′≤n.
Apart from the above relationship, Candès and Tao [1] proved that the restricted orthogonality constant θk,k′ and the restricted isometry constant δk are related by the following lemma.Lemma 2.2 (see [1]).
One hasθS,S′≤δS+S′≤θS,S′+max(δS,δS′) for all S,S′.In the sequel, a useful inequality betweenℓ1-norm and ℓ2-norm will be introduced.Proposition 2.3 (see [2]).
For anyx∈ℝn,
(2.4)‖x‖2-‖x‖1n≤n4(max⁡1≤i≤n|xi|-min⁡1≤i≤n|xi|).At the last of preliminaries, we introduce the square root lifting inequality [10].Lemma 2.4 (see [10]).
For anya≥1 and positive integers k,k′ such that ak′ is an integer, then
(2.5)θk,ak′≤aθk,k′.


## 3. Improved Bounds for Restricted Isometry Constants

In this section, we discuss the new restricted isometry constantδk for sparse signal recovery via ℓ1 minimization in (1.3).Theorem 3.1.
Supposeβ is k-sparse. Then the ℓ1 minimizer β^ defined in (1.3) satisfies
(3.1)‖β-β^‖2≤221+δk1-13/4δkϵ,
where δk is the k-restricted isometry constant of A in (1.3).Proof.
Leth=β^-β∈ℝm. Partition {1,2,…,m} into the following sets:
(3.2)T0={1,2,…,k},T1={k+1,…,k+k2},T2={k+k2+1,…,2k},…,
where k is an even number. And rearranging the indices if necessary, |h(1)|≥|h(2)|≥⋯, where |h(i)|, i=1,2,…,m is the ith entry of the above vector by rearranging the indices. Then by Proposition 2.3, we obtain
(3.3)∑i≥1‍‖hTi‖2≤1k/2∑i≥1‍‖hTi‖1+k/24(|h(k+1)|-|h(k+k2)|)+⋯.
By the triangle inequality for ∥·∥1, we have
(3.4)|‖β‖1-‖-hT0‖1|≤‖β+hT0‖1.
Since T0⋂‍T0c=∅, we have
(3.5)‖β‖1-‖hT0‖1+‖hT0c‖1≤‖β+hT0+hT0c‖1=‖β+h‖1=‖β^‖1≤‖β‖1.
The last inequality holds because β^ solves (1.3). Then the result is that
(3.6)‖hT0c‖1≤‖hT0‖1.
Substituting (3.6) into (3.3), we get
(3.7)∑i≥1‍‖hTi‖2≤1k/2‖hT0c‖1+k/24|h(k+1)|≤1k/2‖hT0‖1+k/24⋅‖hT0‖2k≤1k/2⋅k‖hT0‖2+142‖hT0‖2≤928‖hT0‖2.
And note that(3.8)|〈Ah,AhT0〉|≥|〈AhT0,AhT0〉|-∑i≥1‍|〈AhTi,AhT0〉|.
From (2.2) and (2.5) in Lemma 2.4, we have
(3.9)|〈AhTi,AhT0〉|≤θk/2,k‖hTi‖2⋅‖hT0‖2.
By Lemma 2.2, we have
(3.10)θk/2,k=θk/2,2⋅k/2≤2δk/2+k/2=2δk.
From (3.7)–(3.10), we have
(3.11)|〈Ah,AhT0〉|≥(1-δk)‖hT0‖22-θk/2,k‖hT0‖2∑i≥1‍‖hTi‖2≥(1-δk)‖hT0‖22-2δk‖hT0‖2⋅92/8‖hT0‖2≥(1-13δk4)‖hT0‖22.
From (1.3), we have
(3.12)‖Ah‖2=‖A(β^-β)‖2≤‖Aβ^-y‖2+‖Aβ-y‖2≤2ϵ.
In addition, we obtain the following relation by simple calculation
(3.13)‖hT0c‖22=(|h(k+1)|2+|h(k+2)|2+⋯)≤max⁡i≥k+1|h(i)|⋅(|h(k+1)|+|h(k+2)|+⋯)=max⁡i≥k+1|h(i)|⋅‖hT0c‖1≤‖hT0‖1k⋅‖hT0c‖1.
Since ∥hT0c∥1≤∥hT0∥1, we have
(3.14)‖hT0c‖22≤‖hT0‖12k.
By the norm inequality ∥hT0∥12≤k∥hT0∥22 and (3.14), we have
(3.15)‖hT0c‖22≤‖hT0‖22.
From (3.7), (3.11)-(3.12), and (3.15), we have
(3.16)‖h‖2≤2‖hT0‖2≤2|〈Ah,AhT0〉|(1-13δk/4)‖hT0‖2≤2‖Ah‖2⋅‖AhT0‖2(1-13δk/4)‖hT0‖2≤2⋅2ϵ⋅1+δk‖hT0‖2(1-13δk/4)‖hT0‖2≤221+δk1-13δk/4ϵ.Remark 3.2.
Ifϵ=0, it is the case where the k-sparse signals are guaranteed to be recovered exactly via ℓ1 minimization under no noise situation.Corollary 3.3.
Lety=Aβ+z with ∥z∥2≤ϵ. Suppose β is k-sparse with k>1. Then under the condition δk<0.308 the constrained ℓ1 minimizer β^ given in (1.3) satisfies
(3.17)‖β-β^‖2≤3.23440.308-δkϵ.Proof.
The proof of this corollary can be easily obtained if we putδk<0.308 into the inequality (3.1) in Theorem 3.1.



---

*Source: 841261-2012-06-27.xml*