1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Because the dual of a norm at a point is formally defined as the the max of inner products of that point and points in the norms unit ball. Dualization (of norms) is an involution operator (i.e "dual of dual of the dual of a norm is the norm"). Conclude. $\endgroup$
    – dohmatob
    Mar 31, 2018 at 8:34

1 Answer 1

3
$\begingroup$

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:

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .