1

Let me write total variation norm $$ \|u\|_{TV} = \max_{z\in Q} \langle z, Du\rangle, $$

where $Q$ is the unit ball in $\mathbb R^2$ and $D$ is the corresponding gradient matrix.

I can smooth TV by $$ \max_{z\in Q} \langle z, Du\rangle - \frac{\mu}{2} \|z\|^2, $$ follwing the paper Yu. Nesterov, Smooth minimization of non-smooth functions, Mathematical Programming (2005).

I know if $g(x)=\alpha f$, the dual function is $g^*(x)= \alpha f^*(x/\alpha)$. My question is how to smooth $g$?

user26857
  • 52,094
jakeoung
  • 1,261
  • What's your $g$ explicitly ? What's the relationship between the TV semi-norm and your $g$ ? I'll need to see what $g$ you're talking about. The "smoothed" TV above is indeed smooth, as a consequence of the Danskin theorem (since $Q$ is compact!). You can't smooth an arbitrary function :) Please, be specific. – dohmatob Nov 25 '15 at 10:36
  • I am sorry for unclear. $f(u)=| u |{TV}$ as I defined. But it is defined in discrete setting. For example, $f(u)=\sum{i,j} \sqrt{ (\partial_x u_{i,j})^2 + (\partial_y u_{i,j})^2 }$ – jakeoung Nov 26 '15 at 03:02
  • I want to refer to 24page in http://statweb.stanford.edu/~candes/math301/Lectures/Smoothing.pdf – jakeoung Nov 26 '15 at 03:05

1 Answers1

1

Given $\alpha \ge 0$ (lookup the definition of mixed norms), you have $$\alpha\|u\|_{TV} = \alpha \|Du\|_{2,1} = \|\alpha D u \|_{2,1}.$$ So, to smooth $g := \alpha \|.\|_{TV}$, simply replace the linear operator $D$ by the scaled version $\alpha D$.

In particular, you don't need convex conjugates, etc.

dohmatob
  • 9,535
  • Can the $ \text{Prox} $ of that be calculated? – Royi Jun 11 '16 at 10:03
  • In closed form ? No. Iteratively ? Yes. The problem would correspond to what is known as (isotropic) TV-denoising. There are many ways to go about it: Chambolle's algorithm, FISTA, etc. – dohmatob Jun 11 '16 at 14:01
  • Why can't it Closed Form be derived? If you vectorize the image the TV Operator (Anisotropic) can be like $ {\left| D x \right|}_{1} $. Is there a closed from for that (In the case $ D = I $, there is - Shrinkage, what about $ D $ which is Discrete Gradient Operator)? – Royi Jun 11 '16 at 14:57
  • There is simply no reason to expect the possibility of a closed-form formula, not even in the anisotropic case. This is because pixels / voxels of the image are somewhat mixed-up by the penalty. However, in the latter case, you can use the LARS algorithm as suggested in appendix B.2 of http://www.jmlr.org/papers/volume11/mairal10a/mairal10a.pdf, for example. – dohmatob Jun 11 '16 at 15:34