Suppose that ΦΦ satisfies the restricted isometry property (RIP) of order 2K2K with δ2K<21δ2K<21. Let x,x^∈RNx,x^∈RN be given, and define h=x^xh=x^x. Let Λ0Λ0 denote the index set corresponding to the KK entries of xx with largest magnitude and Λ1Λ1 the index set corresponding to the KK entries of hΛ0chΛ0c with largest magnitude. Set Λ=Λ0∪Λ1Λ=Λ0∪Λ1. If x^1≤x1x^1≤x1, then
h
2
≤
C
0
σ
K
(
x
)
1
K
+
C
1
Φ
h
Λ
,
Φ
h
h
Λ
2
.
h
2
≤
C
0
σ
K
(
x
)
1
K
+
C
1
Φ
h
Λ
,
Φ
h
h
Λ
2
.
(2)where
C
0
=
2
1

(
1

2
)
δ
2
K
1

(
1
+
2
)
δ
2
K
,
C
1
=
2
1

(
1
+
2
)
δ
2
K
.
C
0
=
2
1

(
1

2
)
δ
2
K
1

(
1
+
2
)
δ
2
K
,
C
1
=
2
1

(
1
+
2
)
δ
2
K
.
(3)We begin by observing that h=hΛ+hΛch=hΛ+hΛc, so that from the triangle inequality
h
2
≤
h
Λ
2
+
h
Λ
c
2
.
h
2
≤
h
Λ
2
+
h
Λ
c
2
.
(4)We first aim to bound hΛc2hΛc2. From Lemma 3 from "ℓ1ℓ1 minimization proof" we have
h
Λ
c
2
=
∑
j
≥
2
h
Λ
j
2
≤
∑
j
≥
2
h
Λ
j
2
≤
h
Λ
0
c
1
K
,
h
Λ
c
2
=
∑
j
≥
2
h
Λ
j
2
≤
∑
j
≥
2
h
Λ
j
2
≤
h
Λ
0
c
1
K
,
(5)where the ΛjΛj are defined as before, i.e., Λ1Λ1 is the index set corresponding to the KK largest entries of hΛ0chΛ0c (in absolute value), Λ2Λ2 as the index set corresponding to the next KK largest entries, and so on.
We now wish to bound hΛ0c1hΛ0c1. Since x1≥x^1x1≥x^1, by applying the triangle inequality we obtain
x
1
≥
x
+
h
1
=
x
Λ
0
+
h
Λ
0
1
+
x
Λ
0
c
+
h
Λ
0
c
1
≥
x
Λ
0
1

h
Λ
0
1
+
h
Λ
0
c
1

x
Λ
0
c
1
.
x
1
≥
x
+
h
1
=
x
Λ
0
+
h
Λ
0
1
+
x
Λ
0
c
+
h
Λ
0
c
1
≥
x
Λ
0
1

h
Λ
0
1
+
h
Λ
0
c
1

x
Λ
0
c
1
.
(6)
Rearranging and again applying the triangle inequality,
h
Λ
0
c
1
≤
x
1

x
Λ
0
1
+
h
Λ
0
1
+
x
Λ
0
c
1
≤
x

x
Λ
0
1
+
h
Λ
0
1
+
x
Λ
0
c
1
.
h
Λ
0
c
1
≤
x
1

x
Λ
0
1
+
h
Λ
0
1
+
x
Λ
0
c
1
≤
x

x
Λ
0
1
+
h
Λ
0
1
+
x
Λ
0
c
1
.
(7)
Recalling that σK(x)1=xΛ0c1=xxΛ01σK(x)1=xΛ0c1=xxΛ01,
h
Λ
0
c
1
≤
h
Λ
0
1
+
2
σ
K
(
x
)
1
.
h
Λ
0
c
1
≤
h
Λ
0
1
+
2
σ
K
(
x
)
1
.
(8)Combining this with Equation 5 we obtain
h
Λ
c
2
≤
h
Λ
0
1
+
2
σ
K
(
x
)
1
K
≤
h
Λ
0
2
+
2
σ
K
(
x
)
1
K
h
Λ
c
2
≤
h
Λ
0
1
+
2
σ
K
(
x
)
1
K
≤
h
Λ
0
2
+
2
σ
K
(
x
)
1
K
(9)where the last inequality follows from standard bounds on ℓpℓp norms (Lemma 1 from "The RIP and the NSP"). By observing that hΛ02≤hΛ2hΛ02≤hΛ2 this combines with Equation 4 to yield
h
2
≤
2
h
Λ
2
+
2
σ
K
(
x
)
1
K
.
h
2
≤
2
h
Λ
2
+
2
σ
K
(
x
)
1
K
.
(10)We now turn to establishing a bound for hΛ2hΛ2. Combining Lemma 4 from "ℓ1ℓ1 minimization proof" with Equation 8 and again applying standard bounds on ℓpℓp norms we obtain
h
Λ
2
≤
α
h
Λ
0
c
1
K
+
β
Φ
h
Λ
,
Φ
h
h
Λ
2
≤
α
h
Λ
0
1
+
2
σ
K
(
x
)
1
K
+
β
Φ
h
Λ
,
Φ
h
h
Λ
2
≤
α
h
Λ
0
2
+
2
α
σ
K
(
x
)
1
K
+
β
Φ
h
Λ
,
Φ
h
h
Λ
2
.
h
Λ
2
≤
α
h
Λ
0
c
1
K
+
β
Φ
h
Λ
,
Φ
h
h
Λ
2
≤
α
h
Λ
0
1
+
2
σ
K
(
x
)
1
K
+
β
Φ
h
Λ
,
Φ
h
h
Λ
2
≤
α
h
Λ
0
2
+
2
α
σ
K
(
x
)
1
K
+
β
Φ
h
Λ
,
Φ
h
h
Λ
2
.
(11)
Since hΛ02≤hΛ2hΛ02≤hΛ2,
(
1

α
)
h
Λ
2
≤
2
α
σ
K
(
x
)
1
K
+
β
Φ
h
Λ
,
Φ
h
h
Λ
2
.
(
1

α
)
h
Λ
2
≤
2
α
σ
K
(
x
)
1
K
+
β
Φ
h
Λ
,
Φ
h
h
Λ
2
.
(12)The assumption that δ2K<21δ2K<21 ensures that α<1α<1. Dividing by (1α)(1α) and combining with Equation 10 results in
h
2
≤
4
α
1

α
+
2
σ
K
(
x
)
1
K
+
2
β
1

α
Φ
h
Λ
,
Φ
h
h
Λ
2
.
h
2
≤
4
α
1

α
+
2
σ
K
(
x
)
1
K
+
2
β
1

α
Φ
h
Λ
,
Φ
h
h
Λ
2
.
(13)Plugging in for αα and ββ yields the desired constants.