consider the fused lasso $$\phi(x) = \gamma \sum\limits_{i=1}^{n-1} |x_i - x_{i+1}|, $$
we want to find the subdifferential of $\phi$.
I tried discussing different cases for $x_i$, for example,
$$\frac{\partial \phi(x)}{x_i} = \begin{cases} 0 & \text{if } x_{i-1} < x_i < x_{i+1} \text{ or } x_{i+1} < x_i < x_{i-1} \\ 2\gamma & \text{if } x_i > \max\{ x_{i-1}, x_{i+1}\}\\ -2\gamma & \text{if } x_i < \min\{ x_{i-1}, x_{i+1}\}\\ [0, 2\gamma] & \text{if } x_{i-1} = x_{i} > x_{i+1}\\ [-2\gamma, 0] & \text{if } x_{i-1} = x_{i} < x_{i+1}\\ [-2\gamma, 2\gamma] & \text{if } x_{i-1} = x_{i} = x_{i+1}\\ \end{cases}, \forall i \in \{2, 3, \cdots, n-1\}$$ I am not sure if it is correct and wondering if there is any simpler method.
Let $I$ be the $n\times n$ identity matrix, $U$ be the similarly sized superdiagonal shift matrix, and $e$ be the $n^{th}$ column of $I.\;$
Then construct the following vector $$\eqalign{ Mx &= (I-ee^T-U)\,x \\ &= \Big[\,(x_1-x_2)\quad(x_2-x_3)\;\ldots\;(x_{n-1}-x_n)\quad(x_n-x_n)\;\Big]^T \\ }$$ and the associated element-wise sign vector $$s={\rm sign}(Mx)$$ Write the objective function in terms of these new variables and calculate its (sub)gradient. $$\eqalign{ \phi &= \gamma\; s^TMx \\ d\phi &= \gamma\; s^TM\,dx &= \gamma\; (M^Ts)^Tdx \\ \frac{\partial\phi}{\partial x} &= \gamma\;(M^Ts) \\ }$$ As an example, for $n=5,\;$ the $M$ matrix looks like this $$\eqalign{ M &= \left[ \begin{array}{r} 1& -1& 0& 0& 0 \\ 0& 1& -1& 0& 0 \\ 0& 0& 1& -1& 0 \\ 0& 0& 0& 1& -1 \\ 0& 0& 0& 0& 0\end{array} \right] }$$ Not sure that this is any simpler, but it is more compact.
All the untidiness hides inside the sign function $$ {\rm sign}(z) = \begin{cases} \;\;{\tt+1} \quad&{\rm if}\quad z>0 \\ \big[{\tt-1},{\tt+1}\big] \quad&{\rm if}\quad z=0 \\ \;\,{\tt-1} \quad&{\rm if}\quad z<0 \\ \end{cases} $$