Understanding Machine Learning: From Theory to Algorithms

23.3 Compressed Sensing 335

Since‖hT 0 ‖ 2 +‖hT 1 ‖ 2 ≤

√

2 ‖hT 0 , 1 ‖ 2 we therefore get that

‖WhT 0 , 1 ‖^22 ≤

√

2 ‖hT 0 , 1 ‖ 2

∑

j≥ 2

‖hTj‖ 2.

Combining this with Equation (23.6) and Equation (23.9) we obtain

(1−)‖hT 0 , 1 ‖^22 ≤

√

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

Rearranging the inequality gives

‖hT 0 , 1 ‖ 2 ≤

√

2 

1 −

s−^1 /^2 ‖hT 0 c‖ 1.

Finally, using Equation (23.8) we get that

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

but since‖hT 0 ‖ 2 ≤‖hT 0 , 1 ‖ 2 this implies

‖hT 0 , 1 ‖ 2 ≤^2 ρ

1 −ρ

s−^1 /^2 ‖xT 0 c‖ 1 ,

which concludes the proof of the second claim.

Proof of Theorem 23.9

To prove the theorem we follow an approach due to (Baraniuk, Davenport, De-
Vore & Wakin 2008). The idea is to combine the Johnson-Lindenstrauss (JL)
lemma with a simple covering argument.
We start with a covering property of the unit ball.

lemma23.11 Let∈(0,1). There exists a finite setQ⊂Rdof size|Q|≤

( 3



)d

such that

sup

x:‖x‖≤ 1

min

v∈Q

‖x−v‖ ≤ .

Proof Letkbe an integer and let

Q′={x∈Rd:∀j∈[d],∃i∈{−k,−k+ 1,...,k}s.t. xj=ik}.

Clearly,|Q′|= (2k+ 1)d. We shall setQ=Q′∩B 2 (1), whereB 2 (1) is the unit
2 ball ofRd. Since the points inQ′are distributed evenly on the unit∞ball,
the size ofQis the size ofQ′times the ratio between the volumes of the unit2 and∞balls. The volume of the`∞ball is 2dand the volume ofB 2 (1) is

πd/^2

Γ(1 +d/2)

.

For simplicity, assume thatdis even and therefore

Γ(1 +d/2) = (d/2)! ≥

(d/ 2

e

)d/ 2

,