We use a twofold application of Lemma REF  and Fubini's Theorem.
Throughout fix \(u,v,I,p\)  as in the proposition.
Step 1.
To deal with the randomness originating from \(\varepsilon _{I^c}\) , we work conditionally on \(\varepsilon _I\) .
Observe that there is a set \(\mathcal {Y}\subset \mathcal {S}_{I^c}\)  of cardinality at most \(\exp (c_1 p)\)  such that
\( \big ( \mathbb {E}_{\varepsilon _{I^c}} |V_{I^c,u,v}|^p \big )^{1/p}\le c_2 \Vert u\Vert _2 \max _{y\in \mathcal {Y}} \sum _{i\in I} \varepsilon _i v_i (A^\ast A y)_i.\) 
Indeed, denote by \(I^c=\cup _\ell J_\ell \)  the partition of \(I^c\) , where \(J_1\)  consists of the \(p\)  largest coordinates of \((|u_i|)_{i \in I^c}\) , \(J_2\)  consists of the \(p\)  largest remaining coordinates and so on.
There are at most \(\frac{n}{p}+1\)  such sets \(J_\ell \)  and by
Lemma  REF
\(\big ( \mathbb {E}_{\varepsilon _{I^c}} |V_{I^c,u,v}|^p \big )^{1/p}&= \Big ( \mathbb {E}_{\varepsilon _{I^c}} \Big |\sum _{j\in I^c}\varepsilon _j u_j (W_{I,v})_j \Big |^p\Big )^{1/p} \\&\le c_3 \Vert u\Vert _2 \max _\ell \Vert \mathrm {proj}_{J_\ell } W_{I,v}\Vert _2.\) 
Using a standard volumetric estimate and successive approximation (see, e.g. [1]}) for every \(\ell \) , it follows that there are sets \(\mathcal {S}^{\prime }_{J_\ell }\subset \mathcal {S}_{J_\ell }\) , each of cardinality
\( |\mathcal {S}^{\prime }_{J_\ell }| \le \exp (c_4 p)\) 
such that for every \(x \in \mathbb {R}^m\) ,
\(\max _{y\in \mathcal {S}_{J_\ell }} \langle x,y\rangle \le 2 \max _{y\in \mathcal {S}^{\prime }_{J_\ell }} \langle x,y\rangle .\) 
In particular,
\( \Vert \mathrm {proj}_{J_\ell } x\Vert _2=\max _{y\in \mathcal {S}_{J_\ell }} \langle x,y\rangle \le 2 \max _{y\in \mathcal {S}^{\prime }_{J_\ell }} \langle x,y\rangle \) 
for every \(x\in \mathbb {R}^m\) .
When applied to \(x=W_{I,v}\)  we have that
\(\Vert \mathrm {proj}_{J_\ell } W_{I,v}\Vert _2&\le 2 \max _{y\in \mathcal {S}^{\prime }_{J_\ell }} \sum _{i\in I} \varepsilon _i v_i (A^\ast A y)_i\) 

for every \(\ell \) .
Setting \(\mathcal {Y}:=\cup _\ell \mathcal {S}^{\prime }_{J_\ell }\) , then \(|\mathcal {Y}| \le \exp (c_1 p)\) , because there are at most \(\frac{n}{p}+1\le 2n\)  \(\ell \) 's, and \(p\ge \log n\)  by assumption.
Thus
\(\big (\mathbb {E}_{\varepsilon _{I^c}} |V_{I^c,u,v}|^p \big )^{1/p}\le c_2 \Vert u\Vert _2 \max _{y\in \mathcal {Y}} \sum _{i\in I} \varepsilon _i v_i (A^\ast A y)_i, \) 
which completes the proof of the first step.
Step 2.
Let us turn to the randomness originating from \(\varepsilon _{I}\) .
Denote by \(I=\cup _\ell I_\ell \)  the partition of \(I\) , where \(I_1\)  consists of the \(p\)  largest coordinates of \((|v_i|)_{i \in I}\) , \(I_2\)  are the remaining \(p\) -largest coordinates and so on.
Then, for fixed but arbitrary \(y\in \mathcal {Y}\) , it follows from Lemma REF  that
\(\Big ( \mathbb {E}_{\varepsilon _{I}} \Big | \sum _{i\in I} \varepsilon _i v_i (A^\ast A y)_i \Big |^p \Big )^{1/p}\le c_3 \Vert v\Vert _2 \max _\ell \Vert  \mathrm {proj}_{I_\ell } A^\ast Ay\Vert _2 .\) 

Next, still for an arbitrary \(y\in \mathcal {Y}\) ,
\( \max _\ell \Vert  \mathrm {proj}_{I_\ell } A^\ast Ay \Vert _2\le \max _{x\in \cup _\ell \mathcal {S}_{I_\ell }}\max _{z\in \cup _{\ell } \mathcal {S}_{J_\ell }} \langle Ax,Az\rangle \le \mathcal {O}_{I,p}\) 
where the last inequality follows from the definition of \(\mathcal {O}_{I,p}\)  and by noting that
\(\cup _\ell \mathcal {S}_{I_\ell }\subset \mathcal {S}_{I,p} \ \ {\rm and} \ \ \cup _{\ell } \mathcal {S}_{J_\ell }\subset \mathcal {S}_{I^c,p}.\) 
Combining the two observations,
\(\Big ( \mathbb {E}_{\varepsilon _{I}} \max _{y\in \mathcal {Y}} \Big | \sum _{i\in I} \varepsilon _i v_i (A^\ast A y)_i \Big |^p \Big )^{1/p}&\le \Big ( \sum _{y\in \mathcal {Y} }\mathbb {E}_{\varepsilon _{I}} \Big | \sum _{i\in I} \varepsilon _i v_i (A^\ast A y)_i \Big |^p \Big )^{1/p} \\&\le c_4 | \mathcal {Y}|^{1/p} \Vert v\Vert _2\mathcal {O}_{I,p} \\&\le c_5 \Vert v\Vert _2\mathcal {O}_{I,p},\) 
 where the last inequality holds because \(|\mathcal {Y}| \le \exp (c_1p)\) .
Step 3.
The proof is completed via an application of Fubini's Theorem:
\(\mathbb {E}_{\varepsilon } |V_{I^c,u,v}|^p= \mathbb {E}_{\varepsilon _{I}} \mathbb {E}_{\varepsilon _{I^c}} |V_{I^c,u,v}|^p\le & \mathbb {E}_{\varepsilon _I} c_2^p \Vert u\Vert _2^p \max _{y \in \mathcal {Y}} \Big | \sum _{i\in I} \varepsilon _i v_i (A^\ast A y)_i \Big |^p\\\le & c_2^p \Vert u\Vert _2^p c_5^p \Vert v\Vert _2^p \mathcal {O}_{I,p}^p.\) 
