Understanding Machine Learning: From Theory to Algorithms

334 Dimensionality Reduction

Combining these two claims with Equation (23.5) we get that

‖h‖ 2 ≤‖hT 0 , 1 ‖ 2 +‖hT 0 c, 1 ‖ 2 ≤ 2 ‖hT 0 , 1 ‖ 2 + 2s−^1 /^2 ‖x−xs‖ 1

≤ 2

(

2 ρ

1 −ρ+ 1

)

s−^1 /^2 ‖x−xs‖ 1

= 2

1 +ρ

1 −ρ

s−^1 /^2 ‖x−xs‖ 1 ,

and this will conclude our proof.

Proving Claim 1:

To prove this claim we do not use the RIP condition at all but only use the fact

thatx?minimizes the` 1 norm. Takej >1. For eachi∈Tjandi′∈Tj− 1 we

have that|hi|≤|hi′|. Therefore,‖hTj‖∞≤‖hTj− 1 ‖ 1 /s. Thus,

‖hTj‖ 2 ≤s^1 /^2 ‖hTj‖∞≤s−^1 /^2 ‖hTj− 1 ‖ 1.

Summing this overj= 2, 3 ,...and using the triangle inequality we obtain that

‖hT 0 c, 1 ‖ 2 ≤

∑

j≥ 2

‖hTj‖ 2 ≤s−^1 /^2 ‖hT 0 c‖ 1 (23.6)

Next, we show that‖hT 0 c‖ 1 cannot be large. Indeed, from the definition ofx?

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

obtain that

‖x‖ 1 ≥‖x+h‖ 1 =

∑

i∈T 0

|xi+hi|+

∑

i∈T 0 c

|xi+hi|≥‖xT 0 ‖ 1 −‖hT 0 ‖ 1 +‖hT 0 c‖ 1 −‖xT 0 c‖ 1

(23.7)

and since‖xT 0 c‖ 1 =‖x−xs‖ 1 =‖x‖ 1 −‖xT 0 ‖ 1 we get that

‖hT 0 c‖ 1 ≤‖hT 0 ‖ 1 + 2‖xT 0 c‖ 1. (23.8)

Combining this with Equation (23.6) we get that

‖hT 0 c, 1 ‖ 2 ≤s−^1 /^2

(

‖hT 0 ‖ 1 + 2‖xT 0 c‖ 1

)

≤‖hT 0 ‖ 2 + 2s−^1 /^2 ‖xT 0 c‖ 1 ,

which concludes the proof of claim 1.

Proving Claim 2:

For the second claim we use the RIP condition to get that

(1−)‖hT 0 , 1 ‖^22 ≤‖WhT 0 , 1 ‖^22. (23.9)

SinceWhT 0 , 1 =Wh−

∑

j≥ 2 WhTj=−

∑

j≥ 2 WhTjwe have that

‖WhT 0 , 1 ‖^22 =−

∑

j≥ 2

〈WhT 0 , 1 ,WhTj〉=−

∑

j≥ 2

〈WhT 0 +WhT 1 ,WhTj〉.

From the RIP condition on inner products we obtain that for alli∈ { 1 , 2 }and

j≥2 we have

|〈WhTi,WhTj〉|≤‖hTi‖ 2 ‖hTj‖ 2.