Understanding Machine Learning: From Theory to Algorithms

23.3 Compressed Sensing 337

the condition given in the lemma, the following holds with probability of at least
1 −δ:

sup

v∈Q

∣∣

∣∣‖WUIv‖

2

‖UIv‖^2

− 1

∣∣

∣∣≤/ 2 ,

This also implies that

sup

v∈Q

∣∣

∣∣‖WUIv‖

‖UIv‖

− 1

∣∣

∣∣≤/ 2.

Letabe the smallest number such that

∀x∈S,

‖Wx‖

‖x‖

≤1 +a.

Clearlya <∞. Our goal is to show thata≤. This follows from the fact that
for anyx∈Sof unit norm there existsv∈Qsuch that‖x−UIv‖ ≤/4 and
therefore

‖Wx‖≤‖WUIv‖+‖W(x−UIv)‖≤1 +/2 + (1 +a)/ 4.

Thus,

∀x∈S,

‖Wx‖

‖x‖

≤1 + (/2 + (1 +a)/4).

But the definition ofaimplies that

a≤/2 + (1 +a)/ 4 ⇒ a≤/2 +/^4

1 −/ 4

≤.

This proves that for allx∈Swe have‖‖Wxx‖‖− 1 ≤. The other side follows from
this as well since

‖Wx‖≥‖WUIv‖−‖W(x−UIv)‖≥ 1 −/ 2 −(1 +)/ 4 ≥ 1 −.

The preceding lemma tells us that forx∈Sof unit norm we have

(1−)≤‖Wx‖≤(1 +),

which implies that

(1− 2 )≤‖Wx‖^2 ≤(1 + 3).

The proof of Theorem 23.9 follows from this by a union bound over all choices
ofI.