[proofplan]
The proof uses only the optimality of $\hat{\beta}_{\mathrm{DS}}$ for the $\ell^1$ objective and the fact that $\beta^*$ is feasible. Since $\beta^*$ is an admissible competitor, the $\ell^1$ norm of $\hat{\beta}_{\mathrm{DS}}=\beta^*+\Delta$ cannot exceed the $\ell^1$ norm of $\beta^*$. Splitting the coordinates into the support $S$ of $\beta^*$ and its complement turns this optimality inequality into a comparison between the on-support and off-support parts of $\Delta$.
[/proofplan]
[step:Use feasibility of $\beta^*$ to obtain the basic $\ell^1$ optimality inequality]
Since $\beta^* \in \mathcal{D}_\lambda$ and $\hat{\beta}_{\mathrm{DS}}$ minimizes the $\ell^1$ norm over $\mathcal{D}_\lambda$, we have
\begin{align*}
\|\hat{\beta}_{\mathrm{DS}}\|_1 \leq \|\beta^*\|_1.
\end{align*}
By the definition $\Delta := \hat{\beta}_{\mathrm{DS}}-\beta^*$, this is equivalently
\begin{align*}
\|\beta^*+\Delta\|_1 \leq \|\beta^*\|_1.
\end{align*}
[/step]
[step:Split the optimality inequality into support and complement coordinates]
Because $S=\operatorname{supp}(\beta^*)$, we have $\beta^*_{S^c}=0$. Therefore the coordinate decomposition over the disjoint sets $S$ and $S^c$ gives
\begin{align*}
\|\beta^*+\Delta\|_1
= \|\beta^*_S+\Delta_S\|_1+\|\beta^*_{S^c}+\Delta_{S^c}\|_1.
\end{align*}
Since $\beta^*_{S^c}=0$, this becomes
\begin{align*}
\|\beta^*+\Delta\|_1
= \|\beta^*_S+\Delta_S\|_1+\|\Delta_{S^c}\|_1.
\end{align*}
Also $\|\beta^*\|_1=\|\beta^*_S\|_1$. Substituting these identities into the basic optimality inequality gives
\begin{align*}
\|\beta^*_S+\Delta_S\|_1+\|\Delta_{S^c}\|_1 \leq \|\beta^*_S\|_1.
\end{align*}
[guided]
The purpose of introducing $S=\operatorname{supp}(\beta^*)$ is that $\beta^*$ vanishes outside $S$. More precisely, for every coordinate $j \in S^c$, one has $\beta^*_j=0$. Hence the off-support coordinates of $\beta^*+\Delta$ are exactly the off-support coordinates of $\Delta$.
Using the coordinate decomposition of the $\ell^1$ norm over the disjoint sets $S$ and $S^c$, we first obtain
\begin{align*}
\|\beta^*+\Delta\|_1
= \sum_{j \in S} |\beta^*_j+\Delta_j|+\sum_{j \in S^c} |\beta^*_j+\Delta_j|.
\end{align*}
Since $\beta^*_j=0$ for every $j \in S^c$, the second sum reduces to the off-support error:
\begin{align*}
\|\beta^*+\Delta\|_1
= \sum_{j \in S} |\beta^*_j+\Delta_j|+\sum_{j \in S^c} |\Delta_j|.
\end{align*}
By the definition of restricted vectors and the $\ell^1$ norm, this is
\begin{align*}
\|\beta^*+\Delta\|_1
= \|\beta^*_S+\Delta_S\|_1+\|\Delta_{S^c}\|_1.
\end{align*}
Similarly, since $\beta^*_j=0$ for every $j \in S^c$,
\begin{align*}
\|\beta^*\|_1
= \sum_{j \in S} |\beta^*_j|
= \|\beta^*_S\|_1.
\end{align*}
Substituting these two identities into
\begin{align*}
\|\beta^*+\Delta\|_1 \leq \|\beta^*\|_1
\end{align*}
gives
\begin{align*}
\|\beta^*_S+\Delta_S\|_1+\|\Delta_{S^c}\|_1 \leq \|\beta^*_S\|_1.
\end{align*}
This is the key inequality: the off-support error appears with a positive sign, and the only remaining task is to lower bound the first term on the left in terms of $\|\beta^*_S\|_1$ and $\|\Delta_S\|_1$.
[/guided]
[/step]
[step:Apply the reverse triangle inequality on the support]
For the vectors $\beta^*_S,\Delta_S \in \mathbb{R}^p$, the [Triangle Inequality](/theorems/???) gives
\begin{align*}
\|\beta^*_S\|_1
= \|(\beta^*_S+\Delta_S)-\Delta_S\|_1
\leq \|\beta^*_S+\Delta_S\|_1+\|\Delta_S\|_1.
\end{align*}
Rearranging,
\begin{align*}
\|\beta^*_S+\Delta_S\|_1 \geq \|\beta^*_S\|_1-\|\Delta_S\|_1.
\end{align*}
Combining this with
\begin{align*}
\|\beta^*_S+\Delta_S\|_1+\|\Delta_{S^c}\|_1 \leq \|\beta^*_S\|_1
\end{align*}
yields
\begin{align*}
\|\beta^*_S\|_1-\|\Delta_S\|_1+\|\Delta_{S^c}\|_1
\leq \|\beta^*_S\|_1.
\end{align*}
Subtracting $\|\beta^*_S\|_1$ from both sides gives
\begin{align*}
\|\Delta_{S^c}\|_1 \leq \|\Delta_S\|_1.
\end{align*}
This is the desired cone condition.
[/step]
