Recently, I am following paper Becker S, Bobin J, Candès E J. NESTA: A fast and accurate first-order method for sparse recovery[J]. SIAM Journal on Imaging Sciences, 2011, 4(1): 1-39.
In section 6.3 Total-variation minimization. The equation (6.3) is $$ \|x\|_{\text{TV}} = \max \langle u, Dx \rangle. $$ Originally, for 2D image denoise $$ \|x\|_{\text{TV}} = \sum_{i,j} \sqrt{(x_{i+1,j}-x_{i,j})^2+(x_{i,j+1}-x_{i,j})} = \max \langle u,Dx \rangle,$$ where $$ u=[u_1,u_2]$$ and $$ u_1^2[i,j] + u_2^2[i,j]\le 1.$$ The question is: why the original TV norm (it is square root) could be converted into $\max \langle \rangle$, which is linear version?
This comes from the Dual Function of the TV Norm.
You can read about its derivation by the Dual Formulation of the ROF (Rudin Osher Fatemi) Model (Another reference would be Dual Methods for the Minimization of the Total Variation by Rémy Abergel [See appendix]).
If you have a minimization problem given by:
$$ \arg \min_{x} f \left( x \right) + \lambda \left\| D x \right\| $$
You can replace it by:
$$ \arg \min_{x} \max_{z \: : \: {\left\| z \right\|}_{*} \leq 1} f \left( x \right) + \lambda {z}^{T} D x $$
Where $ \left\| \cdot \right\|_{*} $ is the Dual Norm of $ \left\| \cdot \right\| $.
For instance, for $ {L}_{p} $ norms it means $ {\left\| \cdot \right\|} = {\left\| \cdot \right\|}_{p} $ and $ {\left\| \cdot \right\|}_{*} = {\left\| \cdot \right\|}_{q} $ where $ \frac{1}{p} + \frac{1}{q} = 1 $.
Remark
It would be great if someone could add a simple and intuitive derivation why the above is the Dual of the TV Norm.
References: