I'm trying to run proximal gradient descent on the following problem:
$$min_u \frac{1}{2} ||u-z||_2^2 + \lambda |Du|$$ where $|Du| = \sum_{i=1}^{N-1} |u_{i+1} - u_i| $
I've come up with the dual problem:
$min_{\gamma} \frac{1}{2} || z - D^T\gamma ||_2^2$ subject to $||\gamma||_{\infty} \leq \lambda$
where you get the following primal solution: $u_* = z - D^T\gamma_*$; I'm a little stuck on solving the dual problem to get the proximal operator with the $l_{\infty}$ norm.
for the first part the derivative is: $-DD^T(z-D^T\gamma)$ and I'm actually a little stuck here.
Also, is there an efficient way to compute $D$, $DD^T$ and $D^T$ without calculating the entire matrix?