 Solution

Let $h=\hat{\theta }-{\theta }^{\ast }$. The defining minimum for graph total variation denoising, compared with the feasible value ${\theta }^{\ast }$, gives $n^{-1}\Vert z-h{\Vert }_2^2+\lambda \Vert D\hat{\theta }{\Vert }_1\le n^{-1}\Vert z{\Vert }_2^2+\lambda \Vert D{\theta }^{\ast }{\Vert }_1$. Expand the squared Euclidean norm and cancel $\Vert z{\Vert }_2^2/n$ to obtain the basic inequality for a penalized least-squares estimator: