[proofplan] We prove the formula directly from the definition of the [convex subdifferential](/page/Convex%20Subdifferential). First, if $z$ is a subgradient at $\beta$, we perturb $\beta$ in one coordinate at a time; the resulting one-dimensional inequalities force $z_j = \operatorname{sgn}(\beta_j)$ at nonzero coordinates and $z_j \in [-1,1]$ at zero coordinates. Conversely, if $z$ satisfies these coordinatewise conditions, then the corresponding one-dimensional supporting inequalities for the absolute value sum over $j=1,\dots,p$ to give the full subgradient inequality for the $\ell^1$ norm. [/proofplan]

[step:Extract the coordinatewise restrictions from the subgradient inequality]Let $f: \mathbb{R}^p \to \mathbb{R}$ be the $\ell^1$ norm map $x \mapsto \|x\|_1$. By the definition of the [convex subdifferential](/page/Convex%20Subdifferential), $z \in \partial f(\beta)$ means that $z \in \mathbb{R}^p$ and, for every $\gamma \in \mathbb{R}^p$, \begin{align*} f(\gamma) \geq f(\beta) + z \cdot (\gamma - \beta). \end{align*} For each $j \in \{1,\dots,p\}$, let $e_j \in \mathbb{R}^p$ denote the $j$-th standard basis vector. Fix $j$ and substitute $\gamma = \beta + t e_j$, where $t \in \mathbb{R}$. Since all coordinates except the $j$-th coordinate are unchanged, the subgradient inequality becomes \begin{align*} |\beta_j + t| - |\beta_j| \geq z_j t \end{align*} for every $t \in \mathbb{R}$. If $\beta_j \ne 0$, set $s_j := \operatorname{sgn}(\beta_j)$. For every $t \in \mathbb{R}$ with $|t| < |\beta_j|$, the numbers $\beta_j$ and $\beta_j + t$ have the same sign, so \begin{align*} |\beta_j + t| - |\beta_j| = s_j t. \end{align*} Thus \begin{align*} s_j t \geq z_j t \end{align*} for all $t$ with $|t| < |\beta_j|$. Taking $t > 0$ gives $s_j \geq z_j$, and taking $t < 0$ gives $s_j \leq z_j$. Hence $z_j = s_j = \operatorname{sgn}(\beta_j)$. If $\beta_j = 0$, the same coordinate inequality becomes \begin{align*} |t| \geq z_j t \end{align*} for every $t \in \mathbb{R}$. Taking $t > 0$ gives $z_j \leq 1$, and taking $t < 0$ gives $z_j \geq -1$. Therefore $z_j \in [-1,1]$. Since $j$ was arbitrary, every $z \in \partial f(\beta)$ satisfies the stated coordinatewise conditions.[/step]

[guided]We start from the definition because the subdifferential is a supporting-hyperplane condition. The function under consideration is the map $f: \mathbb{R}^p \to \mathbb{R}$ given by $x \mapsto \|x\|_1$. Equivalently, for each $x \in \mathbb{R}^p$, \begin{align*} f(x) = \|x\|_1 = \sum_{k=1}^p |x_k|. \end{align*} By the definition of the [convex subdifferential](/page/Convex%20Subdifferential), a vector $z \in \mathbb{R}^p$ lies in $\partial f(\beta)$ precisely when \begin{align*} f(\gamma) \geq f(\beta) + z \cdot (\gamma - \beta) \end{align*} for every $\gamma \in \mathbb{R}^p$. To learn what this condition says about one coordinate, fix $j \in \{1,\dots,p\}$ and let $e_j \in \mathbb{R}^p$ be the $j$-th standard basis vector. We test the subgradient inequality only on points of the form $\gamma = \beta + t e_j$, where $t \in \mathbb{R}$. This changes the $j$-th coordinate and leaves every other coordinate fixed. Therefore \begin{align*} f(\beta + t e_j) - f(\beta) = \sum_{k=1}^p |\beta_k + t(e_j)_k| - \sum_{k=1}^p |\beta_k|. \end{align*} Since $(e_j)_j = 1$ and $(e_j)_k = 0$ for $k \ne j$, all terms with $k \ne j$ cancel, so \begin{align*} f(\beta + t e_j) - f(\beta) = |\beta_j + t| - |\beta_j|. \end{align*} Also, \begin{align*} z \cdot ((\beta + t e_j) - \beta) = z \cdot (t e_j) = z_j t. \end{align*} Thus the subgradient inequality implies the one-dimensional inequality \begin{align*} |\beta_j + t| - |\beta_j| \geq z_j t \end{align*} for every $t \in \mathbb{R}$. Now suppose $\beta_j \ne 0$. Define $s_j := \operatorname{sgn}(\beta_j)$. For every $t$ with $|t| < |\beta_j|$, the perturbation is too small to cross zero, so $\beta_j$ and $\beta_j + t$ have the same sign. Hence \begin{align*} |\beta_j + t| - |\beta_j| = s_j t. \end{align*} Substituting this into the one-dimensional inequality gives \begin{align*} s_j t \geq z_j t \end{align*} for every $t$ with $|t| < |\beta_j|$. If $t > 0$, division by $t$ gives $s_j \geq z_j$. If $t < 0$, division reverses the inequality and gives $s_j \leq z_j$. These two inequalities force \begin{align*} z_j = s_j = \operatorname{sgn}(\beta_j). \end{align*} Now suppose $\beta_j = 0$. The same one-dimensional inequality reduces to \begin{align*} |t| \geq z_j t \end{align*} for every $t \in \mathbb{R}$. Taking $t > 0$ gives $t \geq z_j t$, hence $z_j \leq 1$. Taking $t < 0$ gives $-t \geq z_j t$, and dividing by the negative number $t$ gives $z_j \geq -1$. Therefore \begin{align*} z_j \in [-1,1]. \end{align*} Since the coordinate $j$ was arbitrary, the subgradient condition forces exactly the stated coordinate restrictions.[/guided]

[step:Sum the one-dimensional supporting inequalities to prove the converse] Assume now that $z \in \mathbb{R}^p$ satisfies the stated coordinatewise conditions. We prove that $z \in \partial f(\beta)$. Fix $\gamma \in \mathbb{R}^p$. For each $j \in \{1,\dots,p\}$, we claim that \begin{align*} |\gamma_j| \geq |\beta_j| + z_j(\gamma_j - \beta_j). \end{align*} If $\beta_j > 0$, then $z_j = 1$, and the inequality becomes \begin{align*} |\gamma_j| \geq \gamma_j, \end{align*} which holds for every real number $\gamma_j$. If $\beta_j < 0$, then $z_j = -1$, and the inequality becomes \begin{align*} |\gamma_j| \geq -\gamma_j, \end{align*} which also holds for every real number $\gamma_j$. If $\beta_j = 0$, then $z_j \in [-1,1]$, so $|z_j| \leq 1$, and \begin{align*} z_j \gamma_j \leq |z_j|\,|\gamma_j| \leq |\gamma_j|. \end{align*} Thus the coordinate inequality holds in every case. Summing these inequalities over $j=1,\dots,p$ gives \begin{align*} \sum_{j=1}^p |\gamma_j| \geq \sum_{j=1}^p |\beta_j| + \sum_{j=1}^p z_j(\gamma_j - \beta_j). \end{align*} By the definitions of the $\ell^1$ norm and the Euclidean dot product, this becomes \begin{align*} \sum_{j=1}^p |\gamma_j| \geq \|\beta\|_1 + z \cdot (\gamma - \beta). \end{align*} Since $\gamma \in \mathbb{R}^p$ was arbitrary, this is precisely the defining inequality for $z \in \partial f(\beta)$. Therefore every vector satisfying the coordinatewise conditions belongs to $\partial \|\beta\|_1$. [/step]

[step:Identify the two inclusions with the stated set] The first step proves \begin{align*} \partial \|\beta\|_1 \subset \left\{ z \in \mathbb{R}^p : z_j = \operatorname{sgn}(\beta_j) \text{ if } \beta_j \ne 0, \text{ and } z_j \in [-1,1] \text{ if } \beta_j = 0 \right\}. \end{align*} The second step proves the reverse inclusion. Hence the two sets are equal, which is the desired formula for the subdifferential of the $\ell^1$ norm at $\beta$. [/step]