[proofplan] The proof has three ingredients. First, optimality of the Dantzig selector and the support condition on $\beta^*$ force the error vector $\Delta$ into the cone $\mathcal{C}(S)$. Second, feasibility of both $\hat{\beta}_{\mathrm{DS}}$ and $\beta^*$ controls the empirical score $\|X^\top X\Delta/n\|_\infty$ by $2\lambda$. Finally, the cone condition and the restricted eigenvalue condition convert this score bound into a prediction estimate, and substituting that estimate back gives the $\ell^1$ estimate. [/proofplan]

[step:Use Dantzig optimality to place the error in the cone]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*} Using $\hat{\beta}_{\mathrm{DS}} = \beta^* + \Delta$ and $\beta^*_{S^c}=0$, this gives \begin{align*} \|\beta^*_S + \Delta_S\|_1 + \|\Delta_{S^c}\|_1 = \|\beta^* + \Delta\|_1 \leq \|\beta^*\|_1 = \|\beta^*_S\|_1. \end{align*} By the [Reverse Triangle Inequality](/page/Reverse%20Triangle%20Inequality) for the $\ell^1$ norm on $\mathbb{R}^p$, \begin{align*} \|\beta^*_S + \Delta_S\|_1 \geq \|\beta^*_S\|_1 - \|\Delta_S\|_1. \end{align*} Combining the last two displays yields \begin{align*} \|\Delta_{S^c}\|_1 \leq \|\Delta_S\|_1. \end{align*} Thus $\Delta \in \mathcal{C}(S)$. If $s=0$, then $S=\varnothing$, so the cone condition gives \begin{align*} \|\Delta\|_1=\|\Delta_{S^c}\|_1 \leq \|\Delta_S\|_1=0. \end{align*} Hence $\Delta=0$, and both asserted inequalities hold because $\kappa(S,1)>0$ makes the displayed denominators positive and the right-hand sides equal $0$. For the remaining steps, assume $s\geq 1$.[/step]

[guided]The first point is that the Dantzig selector is not merely feasible; it is an $\ell^1$-minimizer among all feasible vectors. Since $\beta^*$ is feasible by hypothesis, the minimizing property gives \begin{align*} \|\hat{\beta}_{\mathrm{DS}}\|_1 \leq \|\beta^*\|_1. \end{align*} We now rewrite this inequality in terms of the error vector $\Delta := \hat{\beta}_{\mathrm{DS}}-\beta^*$. Because $S=\operatorname{supp}(\beta^*)$, the vector $\beta^*$ has no coordinates outside $S$, so $\beta^*_{S^c}=0$. Therefore \begin{align*} \|\hat{\beta}_{\mathrm{DS}}\|_1 = \|\beta^*+\Delta\|_1 = \|\beta^*_S+\Delta_S\|_1+\|\Delta_{S^c}\|_1. \end{align*} The right-hand side of the optimality inequality is \begin{align*} \|\beta^*\|_1=\|\beta^*_S\|_1. \end{align*} Hence \begin{align*} \|\beta^*_S+\Delta_S\|_1+\|\Delta_{S^c}\|_1 \leq \|\beta^*_S\|_1. \end{align*} The only remaining issue is to isolate $\|\Delta_{S^c}\|_1$. The [Reverse Triangle Inequality](/page/Reverse%20Triangle%20Inequality) for the $\ell^1$ norm on $\mathbb{R}^p$ gives \begin{align*} \|\beta^*_S+\Delta_S\|_1 \geq \|\beta^*_S\|_1-\|\Delta_S\|_1. \end{align*} Substituting this lower bound into the previous inequality gives \begin{align*} \|\beta^*_S\|_1-\|\Delta_S\|_1+\|\Delta_{S^c}\|_1 \leq \|\beta^*_S\|_1. \end{align*} After subtracting $\|\beta^*_S\|_1$ from both sides, we obtain \begin{align*} \|\Delta_{S^c}\|_1 \leq \|\Delta_S\|_1. \end{align*} This is exactly the cone condition $\Delta \in \mathcal{C}(S)$. We also handle the edge case in which the support is empty. If $s=0$, then $S=\varnothing$, and the cone condition reads \begin{align*} \|\Delta\|_1=\|\Delta_{S^c}\|_1 \leq \|\Delta_S\|_1=0. \end{align*} Therefore $\Delta=0$. Since $\kappa(S,1)>0$, the denominators in the two claimed right-hand sides are positive; since $s=0$, both right-hand sides are $0$. Thus both desired inequalities hold in this case. From now on, we may assume $s\geq 1$.[/guided]

[step:Use feasibility of both vectors to bound the empirical score]Define the residual map $R: \mathbb{R}^p \to \mathbb{R}^n$ by declaring that, for each $\beta \in \mathbb{R}^p$, the value $R(\beta) \in \mathbb{R}^n$ is \begin{align*} R(\beta)=y-X\beta. \end{align*} Since $\hat{\beta}_{\mathrm{DS}},\beta^* \in \mathcal{D}_\lambda$, we have \begin{align*} \left\|\frac{X^\top R(\hat{\beta}_{\mathrm{DS}})}{n}\right\|_\infty \leq \lambda, \qquad \left\|\frac{X^\top R(\beta^*)}{n}\right\|_\infty \leq \lambda. \end{align*} Because \begin{align*} R(\beta^*)-R(\hat{\beta}_{\mathrm{DS}}) = y-X\beta^* - y + X\hat{\beta}_{\mathrm{DS}} = X\Delta, \end{align*} we first obtain \begin{align*} \left\|\frac{X^\top X\Delta}{n}\right\|_\infty = \left\|\frac{X^\top R(\beta^*)}{n}-\frac{X^\top R(\hat{\beta}_{\mathrm{DS}})}{n}\right\|_\infty. \end{align*} Applying the triangle inequality for the maximum norm $\|\cdot\|_\infty$ on $\mathbb{R}^p$ gives \begin{align*} \left\|\frac{X^\top X\Delta}{n}\right\|_\infty \leq \left\|\frac{X^\top R(\beta^*)}{n}\right\|_\infty + \left\|\frac{X^\top R(\hat{\beta}_{\mathrm{DS}})}{n}\right\|_\infty. \end{align*} Using the two feasibility bounds yields \begin{align*} \left\|\frac{X^\top X\Delta}{n}\right\|_\infty \leq 2\lambda. \end{align*}[/step]

[guided]We next translate feasibility into a bound on the empirical score of the error vector. Define the residual map $R: \mathbb{R}^p \to \mathbb{R}^n$ by declaring that, for each $\beta \in \mathbb{R}^p$, the value $R(\beta) \in \mathbb{R}^n$ is \begin{align*} R(\beta)=y-X\beta. \end{align*} The definition of feasibility in the Dantzig set $\mathcal{D}_\lambda$ gives the two bounds \begin{align*} \left\|\frac{X^\top R(\hat{\beta}_{\mathrm{DS}})}{n}\right\|_\infty \leq \lambda, \qquad \left\|\frac{X^\top R(\beta^*)}{n}\right\|_\infty \leq \lambda. \end{align*} The key point is that the difference of these residuals is exactly the fitted-value error. Since $\Delta=\hat{\beta}_{\mathrm{DS}}-\beta^*$, expanding the two residuals gives \begin{align*} R(\beta^*)-R(\hat{\beta}_{\mathrm{DS}})=y-X\beta^* - y + X\hat{\beta}_{\mathrm{DS}}. \end{align*} Cancelling the two occurrences of $y$ and factoring out $X$ gives \begin{align*} R(\beta^*)-R(\hat{\beta}_{\mathrm{DS}})=X(\hat{\beta}_{\mathrm{DS}}-\beta^*)=X\Delta. \end{align*} Multiplying by $X^\top/n$ gives \begin{align*} \frac{X^\top X\Delta}{n} = \frac{X^\top R(\beta^*)}{n}-\frac{X^\top R(\hat{\beta}_{\mathrm{DS}})}{n}. \end{align*} Applying the triangle inequality for the maximum norm $\|\cdot\|_\infty$ on $\mathbb{R}^p$ gives \begin{align*} \left\|\frac{X^\top X\Delta}{n}\right\|_\infty \leq \left\|\frac{X^\top R(\beta^*)}{n}\right\|_\infty + \left\|\frac{X^\top R(\hat{\beta}_{\mathrm{DS}})}{n}\right\|_\infty. \end{align*} Substituting the two feasibility estimates yields \begin{align*} \left\|\frac{X^\top X\Delta}{n}\right\|_\infty \leq \lambda+\lambda=2\lambda. \end{align*}[/guided]

[step:Convert the score bound into a prediction bound]The Euclidean identity for the matrix $X$ and vector $\Delta$ gives \begin{align*} \frac{\|X\Delta\|_2^2}{n} = \frac{\Delta^\top X^\top X\Delta}{n}. \end{align*} Applying [Hölder's Inequality](/page/Holder%20Inequality) for the conjugate pair $(1,\infty)$ to the vectors $\Delta$ and $X^\top X\Delta/n$ in $\mathbb{R}^p$, and then using the score bound, yields \begin{align*} \frac{\|X\Delta\|_2^2}{n} \leq \|\Delta\|_1\left\|\frac{X^\top X\Delta}{n}\right\|_\infty \leq 2\lambda\|\Delta\|_1. \end{align*} Since $\Delta \in \mathcal{C}(S)$, \begin{align*} \|\Delta\|_1 = \|\Delta_S\|_1+\|\Delta_{S^c}\|_1 \leq 2\|\Delta_S\|_1. \end{align*} Enumerate the finite set $S$ as $S=\{j_1,\dots,j_s\}$, and regard $\Delta_S$ as the vector $(\Delta_{j_1},\dots,\Delta_{j_s}) \in \mathbb{R}^s$. By the [Cauchy-Schwarz Inequality](/page/Cauchy-Schwarz%20Inequality) in $\mathbb{R}^s$, \begin{align*} \|\Delta_S\|_1 \leq \sqrt{s}\,\|\Delta_S\|_2. \end{align*} Thus \begin{align*} \|\Delta\|_1 \leq 2\sqrt{s}\,\|\Delta_S\|_2. \end{align*} If $\Delta_S=0$, the cone condition gives $\|\Delta_{S^c}\|_1=0$, hence $\Delta=0$, and both claimed inequalities follow. Assume therefore that $\Delta_S \neq 0$. Since $\Delta \in \mathcal{C}(S)$, the definition of $\kappa(S,1)$ gives \begin{align*} \kappa(S,1) \leq \frac{\|X\Delta\|_2}{\sqrt{n}\,\|\Delta_S\|_2}, \end{align*} or equivalently \begin{align*} \|\Delta_S\|_2 \leq \frac{\|X\Delta\|_2}{\sqrt{n}\,\kappa(S,1)}. \end{align*} Combining the preceding estimates gives \begin{align*} \frac{\|X\Delta\|_2^2}{n} \leq 2\lambda\|\Delta\|_1 \leq 4\lambda\sqrt{s}\,\|\Delta_S\|_2 \leq \frac{4\lambda\sqrt{s}\,\|X\Delta\|_2}{\sqrt{n}\,\kappa(S,1)}. \end{align*} If $\|X\Delta\|_2=0$, the desired prediction bound is immediate. If $\|X\Delta\|_2>0$, divide by $\|X\Delta\|_2/\sqrt{n}$ to obtain \begin{align*} \frac{\|X\Delta\|_2}{\sqrt{n}} \leq \frac{4\lambda\sqrt{s}}{\kappa(S,1)}. \end{align*} Squaring both sides gives \begin{align*} \frac{\|X\Delta\|_2^2}{n} \leq \frac{16\lambda^2 s}{\kappa(S,1)^2}. \end{align*}[/step]

[guided]We now combine the score control with the restricted eigenvalue condition. First, the Euclidean identity for the matrix $X$ and vector $\Delta$ gives \begin{align*} \frac{\|X\Delta\|_2^2}{n} = \frac{\Delta^\top X^\top X\Delta}{n}. \end{align*} Apply [Hölder's Inequality](/page/Holder%20Inequality) with conjugate exponents $(1,\infty)$ to the two vectors $\Delta \in \mathbb{R}^p$ and $X^\top X\Delta/n \in \mathbb{R}^p$. This gives \begin{align*} \frac{\|X\Delta\|_2^2}{n} \leq \|\Delta\|_1\left\|\frac{X^\top X\Delta}{n}\right\|_\infty. \end{align*} Using the score bound from the previous step, we obtain \begin{align*} \frac{\|X\Delta\|_2^2}{n} \leq 2\lambda\|\Delta\|_1. \end{align*} The cone condition now reduces the full $\ell^1$ norm to the active coordinates: \begin{align*} \|\Delta\|_1 = \|\Delta_S\|_1+\|\Delta_{S^c}\|_1 \leq 2\|\Delta_S\|_1. \end{align*} Enumerate the finite set $S$ as $S=\{j_1,\dots,j_s\}$, and regard $\Delta_S$ as the vector $(\Delta_{j_1},\dots,\Delta_{j_s}) \in \mathbb{R}^s$. Applying the [Cauchy-Schwarz Inequality](/page/Cauchy-Schwarz%20Inequality) in $\mathbb{R}^s$ gives \begin{align*} \|\Delta_S\|_1 \leq \sqrt{s}\,\|\Delta_S\|_2. \end{align*} Therefore \begin{align*} \|\Delta\|_1 \leq 2\sqrt{s}\,\|\Delta_S\|_2. \end{align*} If $\Delta_S=0$, the cone condition gives $\|\Delta_{S^c}\|_1=0$, hence $\Delta=0$, and the prediction inequality follows. Assume $\Delta_S\neq 0$. Since $\Delta\in\mathcal{C}(S)$, the definition of the restricted eigenvalue constant $\kappa(S,1)$ gives \begin{align*} \kappa(S,1) \leq \frac{\|X\Delta\|_2}{\sqrt{n}\,\|\Delta_S\|_2}, \end{align*} so \begin{align*} \|\Delta_S\|_2 \leq \frac{\|X\Delta\|_2}{\sqrt{n}\,\kappa(S,1)}. \end{align*} Combining the estimates yields \begin{align*} \frac{\|X\Delta\|_2^2}{n} \leq 2\lambda\|\Delta\|_1 \leq 4\lambda\sqrt{s}\,\|\Delta_S\|_2 \leq \frac{4\lambda\sqrt{s}\,\|X\Delta\|_2}{\sqrt{n}\,\kappa(S,1)}. \end{align*} If $\|X\Delta\|_2=0$, the desired prediction bound follows. If $\|X\Delta\|_2>0$, divide by $\|X\Delta\|_2/\sqrt{n}$ to obtain \begin{align*} \frac{\|X\Delta\|_2}{\sqrt{n}} \leq \frac{4\lambda\sqrt{s}}{\kappa(S,1)}. \end{align*} Squaring both sides gives \begin{align*} \frac{\|X\Delta\|_2^2}{n} \leq \frac{16\lambda^2 s}{\kappa(S,1)^2}. \end{align*}[/guided]

[step:Substitute the prediction estimate to obtain the $\ell^1$ estimate]From the cone condition and the finite-dimensional Cauchy-Schwarz estimate on the support coordinates, \begin{align*} \|\Delta\|_1 \leq 2\sqrt{s}\,\|\Delta_S\|_2. \end{align*} If $\Delta_S=0$, then the cone condition gives $\|\Delta_{S^c}\|_1=0$, hence $\Delta=0$, and the claimed $\ell^1$ estimate follows. Assume therefore that $\Delta_S\neq 0$. Since $\Delta\in\mathcal{C}(S)$, the definition of $\kappa(S,1)$ gives \begin{align*} \|\Delta_S\|_2 \leq \frac{\|X\Delta\|_2}{\sqrt{n}\,\kappa(S,1)}. \end{align*} Combining the last two displays gives \begin{align*} \|\Delta\|_1 \leq \frac{2\sqrt{s}\,\|X\Delta\|_2}{\sqrt{n}\,\kappa(S,1)}. \end{align*} Using the prediction estimate \begin{align*} \frac{\|X\Delta\|_2}{\sqrt{n}} \leq \frac{4\lambda\sqrt{s}}{\kappa(S,1)}, \end{align*} we obtain \begin{align*} \|\Delta\|_1 \leq \frac{2\sqrt{s}}{\kappa(S,1)} \cdot \frac{4\lambda\sqrt{s}}{\kappa(S,1)} = \frac{8\lambda s}{\kappa(S,1)^2}. \end{align*} Together with the prediction bound, this proves both asserted inequalities.[/step]

[guided]The prediction estimate already proved can now be fed back into the cone and restricted eigenvalue estimates to control $\|\Delta\|_1$. From the cone condition and the finite-dimensional Cauchy-Schwarz estimate on the support coordinates, we have \begin{align*} \|\Delta\|_1 \leq 2\sqrt{s}\,\|\Delta_S\|_2. \end{align*} If $\Delta_S=0$, then this already gives $\|\Delta\|_1=0$, so the desired $\ell^1$ bound holds. If $\Delta_S\neq 0$, the restricted eigenvalue estimate gives \begin{align*} \|\Delta_S\|_2 \leq \frac{\|X\Delta\|_2}{\sqrt{n}\,\kappa(S,1)}. \end{align*} Therefore \begin{align*} \|\Delta\|_1 \leq \frac{2\sqrt{s}\,\|X\Delta\|_2}{\sqrt{n}\,\kappa(S,1)}. \end{align*} The prediction bound gives \begin{align*} \frac{\|X\Delta\|_2}{\sqrt{n}} \leq \frac{4\lambda\sqrt{s}}{\kappa(S,1)}. \end{align*} Substituting this into the preceding display yields \begin{align*} \|\Delta\|_1 \leq \frac{2\sqrt{s}}{\kappa(S,1)} \cdot \frac{4\lambda\sqrt{s}}{\kappa(S,1)} = \frac{8\lambda s}{\kappa(S,1)^2}. \end{align*} Together with the prediction bound, this proves both asserted inequalities.[/guided]