Page 307 - Understanding Machine Learning

23.3 Compressed Sensing 289

Next, we show that h T 1 cannot be large. Indeed, from the definition of x we
c
0

have that x 1 ≥√x 1 = x +h 1 . Thus, using the triangle inequality we obtain that

c
c
x 1 ≥√x + h 1 = |x i + h i |+ |x i + h i |≥ x T 0 1 −⊂h T 0 1 + h T 1 −⊂x T 1

0 0
i∈T 0 i∈T c
0
(23.7)
and since x T 1 = x − x s 1 = x 1 −⊂x T 0 1 we get that
c

0
h T 1 ≤√h T 0 1 + 2 x T 1 . (23.8)
c

c
0 0
Combining this with Equation (23.6) we get that

h T 2 ≤ s −1/2 h T 0 1 + 2 x T 1 ≤√h T 0 2 + 2s −1/2 x T 1 ,

c
c
c
0,1 0 0
which concludes the proof of claim 1.
Proving Claim 2:
For the second claim we use the RIP condition to get that
2 2
≤√Wh T 0,1 2
(1 −
) h T 0,1 2 . (23.9)

= Wh − =− we have that
Since Wh T 0,1 j≥2 Wh T j j≥2 Wh T j

2
=−
Wh T 0,1 2 Wh T 0,1 ,Wh T j =− Wh T 0 + Wh T 1 ,Wh T j .
j≥2 j≥2
From the RIP condition on inner products we obtain that for all i ∈{1,2} and j ≥ 2
we have
| ≤
h T i 2 h T j 2 .

| Wh T i ,Wh T j
√

Since h T 0 2 + h T 1 2 ≤ 2 h T 0,1 2 we therefore get that

√
2

≤
Wh T 0,1 2 2
h T 0,1 2 h T j 2 .
j≥2
Combining this with Equation (23.6) and Equation (23.9) we obtain
√
2 −1/2
≤

c
(1 −
) h T 0,1 2 2
h T 0,1 2 s h T 1 .
0
Rearranging the inequality gives
√
2
−1/2
c

h T 0,1 2 ≤ s h T 1 .
1 −
0
Finally, using Equation (23.8) we get that
h T 0,1 2 ≤ ρs −1/2 ( h T 0 1 + 2 x T 1 ) ≤ ρ h T 0 2 + 2ρs −1/2 x T 1 ,
c
c

0 0
but since h T 0 2 ≤√h T 0,1 2 this implies

2ρ −1/2
c

h T 0,1 2 ≤ s x T 1 ,
1 − ρ 0
which concludes the proof of the second claim.