A) The witness approach
1) For $j\in m^{\ast}$, by definition, $\widehat{z}_{j} = \widetilde{z}_{j}$ and $(\nabla Q (\tilde {\beta _{\lambda}}) +\lambda \widetilde z)_{j} =0$.
Thus $$(\nabla Q (\tilde \beta _{\lambda}) +\lambda \widehat z)_{j} =0$$
Else, by definition, $\widehat z_{j} = - \frac{1}{\lambda} (\nabla Q (\tilde \beta _{\lambda})_{j})$, that is $$(\nabla Q (\tilde \beta _{\lambda}) +\lambda \widehat z)_{j} =0$$
Finally $$\nabla Q (\tilde \beta _{\lambda}) +\lambda \widehat z =0$$
2) Suppose that for all $j\notin m^{\ast}$, $|\widehat{z}_{j}| \leqslant 1$.
Since by definition of $m^{\ast}$, for all $j\notin m^{\ast}$, $(\tilde \beta _{\lambda})_{j} =0$. Thus $\widehat{z}_{j} \in \partial_{j}|.|_{1}(\tilde {\beta _{\lambda}})$.
For all $j\in m^{\ast}$, $\widehat{z}_{j} =\widetilde{z}_{j} \in \partial_{j}|.|_{1}(\tilde {\beta _{\lambda}})$.
Therefore, $\widehat{z} \in \partial|.|_{1}(\tilde {\beta _{\lambda}})$ satisfies $\nabla Q (\tilde \beta _{\lambda}) +\lambda \widehat z =0$. That is to say $0 \in \partial L_{\lambda}(\tilde {\beta _{\lambda}})$.
By strict convexity of Q, which implies the strict convexity of $L_{\lambda}$, $\tilde {\beta _{\lambda}}$ is the unique minimizer of $L_{\lambda}$. Thus $\widehat{\beta _{\lambda}}$ is equal to $\tilde {\beta _{\lambda}}$, so its support $\widehat{m _{\lambda}}$ is included in $m^{\ast}$.
B)Checking the dual feasibility condition
1) We know that : $(\nabla Q (\tilde {\beta _{\lambda}}) +\lambda \widetilde z)_{m^{\ast} } =0$.
Now,
$$ Q(\beta + \delta \beta)= ||Y - X\beta -X\delta\beta||^{2}$$
$$= ||Y - X\beta ||^{2} -2 <Y - X\beta, X\delta\beta> + ||X\delta\beta||^{2}$$
$$= Q(\beta) -2 <X^{T}(Y - X\beta), \delta\beta> + O(||\delta\beta||^{2}) $$
Thus $$ \nabla Q (\beta) = -2 X^{T}(Y - X\beta) $$
So
$$ (-2 X^{T}(Y - X\tilde {\beta _{\lambda}}) +\lambda \widetilde z)_{m^{\ast} } =0$$
$$-2 X_{m^{\ast} }^{T}Y +2 X_{m^{\ast} }^{T} X\tilde {\beta _{\lambda}} + \lambda \widetilde z_{m^{\ast} } =0 $$
Since the support of $\tilde {\beta _{\lambda}}$ is in $m^{\ast}$, we have :
$$ X\tilde {\beta _{\lambda}} = X_{m^{\ast} }(\tilde {\beta _{\lambda}})_{m^{\ast} }$$
So
$$X_{m^{\ast} }^{T} X_{m^{\ast} }(\tilde {\beta _{\lambda}})_{m^{\ast} } = X_{m^{\ast} }^{T}Y - \lambda / 2 \ \widetilde z_{m^{\ast} } $$
$X_{m^{\ast} }^{T} X_{m^{\ast} }$ is inversible because $rank(X) =p$, so $rank(X_{m^{\ast} }) = rank(X_{m^{\ast} }^{T} X_{m^{\ast} }) = m^{\ast}$.
Finally
(1)2) For $j\notin m^{\ast}$,
$$(\nabla Q (\tilde \beta _{\lambda}) +\lambda \widehat z)_{j} =0$$
$$-2 X_{j}^{T}Y +2 X_{j }^{T} X_{m^{\ast} }(\tilde {\beta _{\lambda}})_{m^{\ast} } + \lambda \widehat z_{j} =0$$
$$\lambda \widehat z_{j} = 2 X_{j}^{T}Y -2 X_{j }^{T} X_{m^{\ast} } (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}(X_{m^{\ast} }^{T}Y - \lambda / 2 \ \widetilde z_{m^{\ast} })$$ (cf 1.)
$$\lambda/2 \ \widehat z_{j} = X_{j}^{T}( I - X_{m^{\ast} } (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}X_{m^{\ast} }^{T}) Y + \lambda/2 \ X_{j}^{T}X_{m^{\ast} } (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}\widetilde z_{m^{\ast} }$$
Now, $$X_{m^{\ast} } (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}X_{m^{\ast} }^{T} = P_{m^{\ast} }.$$
Indeed, for $A= X_{m^{\ast} }B$ any element of $S_{m^{\ast} }$, we have :
$$ X_{m^{\ast} } (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}X_{m^{\ast} }^{T}A = X_{m^{\ast} } (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1} (X_{m^{\ast} }^{T}X_{m^{\ast} })B $$
$$ = X_{m^{\ast} }B = A $$
And for A in the orthogonal of $S_{m^{\ast} }$, we have : $X_{m^{\ast} }^{T}A=0$.
Thus $$ X_{m^{\ast} } (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}X_{m^{\ast} }^{T}A =0. $$
Then, writing $Y = X_{m^{\ast} } \beta^{\ast} + \epsilon$, we deduce :
$$ (I - P_{m^{\ast} })Y = (I - P_{m^{\ast} })\epsilon .$$
And finally :
(2)3) Since $\widetilde z \in \partial|.|_{1}(\tilde {\beta _{\lambda}})$, $|\widetilde z_{m^{\ast} }|_{\infty} \leqslant 1$.
Because of the incoherence condition (4.24), we deduce
$$ max_{j \notin m^{\ast} } (|X_{j}^{T}X_{m^{\ast} } (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}\widetilde z_{m^{\ast} }|) \leqslant 1 - \gamma $$
4)$$ P( max_{j \notin m^{\ast} } {|2/\lambda \ X_{j}^{T}( I - P_{m^{\ast} })\epsilon|} > \gamma / 2) \leqslant \sum_{j \notin m^{\ast} } P(|2/\lambda \ X_{j}^{T}( I - P_{m^{\ast} })\epsilon| > \gamma / 2)$$
Now, for any $j \notin m^{\ast}$, $2/\lambda \ X_{j}^{T}( I - P_{m^{\ast} })\epsilon$ is a centered Gaussian random variable of variance :
$$ (2 \sigma /\lambda)^{2} X_{j}^{T}( I - P_{m^{\ast}}) ( I - P_{m^{\ast}})^{T} X_{j} = (2 \sigma /\lambda)^{2} ||( I - P_{m^{\ast}}) X_{j}| \leqslant (2 \sigma /\lambda)^{2} $$
because the columns of X are normalized, and $( I - P_{m^{\ast}})$ is an orthogonal projection, thus 1-Lipschitz.
Thus $$ P(|2/\lambda \ X_{j}^{T}( I - P_{m^{\ast} })\epsilon| > \gamma / 2) \leqslant P(|Z| > \lambda \gamma / 4\sigma ) $$
with Z a standard Gaussian random variable, and with Lemma B.3 :
$$ \leqslant e^{-(\lambda \gamma / 4\sigma)^{2} /2} $$
So $$ P( max_{j \notin m^{\ast} } {|2/\lambda \ X_{j}^{T}( I - P_{m^{\ast} })\epsilon|} > \gamma / 2) \leqslant p \times e^{-(\lambda \gamma / 4\sigma)^{2} /2} $$
For $\lambda = 4 \sigma / \gamma \ \sqrt{2(1+A) \log(p)}$,
$$ P( max_{j \notin m^{\ast} } {|2/\lambda \ X_{j}^{T}( I - P_{m^{\ast} })\epsilon|} > \gamma / 2) \leqslant p \times e^{-(1+A) \log(p)} = p^{-A} $$
With probability at least $1 - p^{-A}$, we have thus $$ max_{j \notin m^{\ast} } {|2/\lambda \ X_{j}^{T}( I - P_{m^{\ast} })\epsilon|} \leqslant \gamma / 2 .$$
With 2. and 3., for any $j \notin m^{\ast}$,
$$ |\widehat z_{j}| \leqslant |2/\lambda \ X_{j}^{T}( I - P_{m^{\ast} })\epsilon| + |X_{j}^{T}X_{m^{\ast} } (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}\widetilde z_{m^{\ast} }| \leqslant 1 - \gamma + \gamma /2 $$
So $|\widehat z_{j}| \leqslant 1$ for all $j \notin m^{\ast}$ with at least the same probability.
C) Support recovery
1) With B.1 :
$$ (\tilde {\beta _{\lambda}})_{m^{\ast} } = (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}(X_{m^{\ast} }^{T}Y - \lambda / 2 \ \widetilde z_{m^{\ast} }) $$
$$ = (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}(X_{m^{\ast} }^{T} (X_{m^{\ast} } \beta^{\ast}_{m^{\ast} } + \epsilon) - \lambda / 2 \ \widetilde z_{m^{\ast} }) $$
$$ = \beta^{\ast}_{m^{\ast} } + (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}(X_{m^{\ast} }^{T} \epsilon - \lambda / 2 \ \widetilde z_{m^{\ast} })$$
2) For $j \notin m^{\ast}$, $(\tilde \beta _{\lambda})_{j} - \beta^{\ast}_{j} = 0 -0 =0$, so these are not a problem.
The condition $||X_{m^{\ast} }^{T} \epsilon||_{\infty} \leqslant \lambda /4$ combined with $|\widetilde z_{m^{\ast} }|_{\infty} \leqslant 1$ implies
$$ ||X_{m^{\ast} }^{T} \epsilon - \lambda / 2 \ \widetilde z_{m^{\ast} }||_{\infty} \leqslant 3 \lambda /4 $$
Then $$||\tilde {\beta _{\lambda}} - \beta^{\ast}||_{\infty} = || (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}(X_{m^{\ast} }^{T} \epsilon - \lambda / 2 \ \widetilde z_{m^{\ast} })||_{\infty} $$
$$ \leqslant 3 \lambda /4 | (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}|_{\infty, \infty} $$
Now, $$ P(||X_{m^{\ast} }^{T} \epsilon||_{\infty} > \lambda /4 ) \leqslant \sum_{j \in m^{\ast} }P(|X_{j}^{T} \epsilon|>\lambda /4 ) .$$
For $j \in m^{\ast}$, $X_{j}^{T} \epsilon$ is a centered Gaussian random variable of variance $\sigma^{2}$. Like in B.4., we know that
$$ P(|X_{j}^{T} \epsilon|>\lambda /4 ) \leqslant e^{- (\lambda / 4\sigma)^{2}/2} $$
$$ \leqslant e^{- (1+A) \log(p) / \gamma^{2}} $$
since $\gamma \leqslant 1$,
$$ \leqslant p^{-1-A} $$
Thus $$ P(||X_{m^{\ast} }^{T} \epsilon||_{\infty} > \lambda /4 ) \leqslant p \times p^{-1-A} =p^{-A}$$
So with probability at least $1 - p^{-A}$, $||X_{m^{\ast} }^{T} \epsilon||_{\infty} \leqslant \lambda /4$, and finally
(3)3) Let's assume $min_{j \in m^{\ast} } |\beta^{\ast}_{j}| > 3 \lambda /4 | (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}|_{\infty, \infty}$.
With probability at least $1 - 2 p^{-A}$, we have both $|\widehat z_{j}| \leqslant 1$ for all $j \notin m^{\ast}$ and $||\tilde {\beta _{\lambda}} - \beta^{\ast}||_{\infty} \leqslant 3 \lambda /4 | (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}|_{\infty, \infty}$ .
With A.2., we deduce that $\widehat{m _{\lambda}}$ is included in $m^{\ast}$.
Reciprocally, for any $j\in m^{\ast}$,$$ |(\tilde {\beta _{\lambda}})_{j}| > min_{j \in m^{\ast} } |\beta^{\ast}_{j}| - ||\tilde {\beta _{\lambda}} - \beta^{\ast}||_{\infty} $$
$$ |(\tilde {\beta _{\lambda}})_{j}| > 3 \lambda /4 | (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}|_{\infty, \infty} -3 \lambda /4 | (X_{m^{\ast} }^{T} X_{m^{\ast} })^{-1}|_{\infty, \infty} =0 $$
Thus $m^{\ast}$ is included in $\widehat{m _{\lambda}}$.
That is to say the Lasso estimator has the same support as the quantity it estimates with probability at least $1 - 2 p^{-A}$.