0
$\begingroup$

I am working on an implementation of deconvolution and Wang et al.'s paper$^\color{magenta}{\dagger}$ mentions something I do not quite understand. The objective function is, in essence,

$$\min_u\sum_{i=1}^{n^2} \| D_i u \|_2 + f(u)$$

where $D_i u$ is the discrete gradient of a grayscale image $u$ at pixel $i$. They say "at each pixel an auxiliary variable $w_i\in\mathbb{R}^2$ is introduced to transfer $D_iu$ out of the non-differentiable term $\| \cdot \|_2$" and they write

$$\min_{w,u}\sum_i\|w_i\|_2+\frac{\beta}{2}\sum_i\|w_i-D_iu\|_2^2+f(u)$$

However, since the square root is not differentiable at the origin, the term $\sum\limits_i\|w_i\|_2$ is non-differentiable, but the authors use proximal gradient methods anyway.

$\color{magenta}{\dagger}$ Yilun Wang, Junfeng Yang, Wotao Yin, Yin Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM Journal on Imaging Sciences, Volume 1, Issue 3, 2008.

$\endgroup$
12
  • $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$ Commented Mar 24 at 8:49
  • $\begingroup$ If $u$ is an image, why do you talk about pixel $i$ instead of pixel $(i,j)$? $\endgroup$ Commented Mar 24 at 9:30
  • $\begingroup$ The authors introduce the equality constraint $w_i = D_iu$ in a "soft way", by ensuring that the norm of the difference $w_i-D_iu$ is minimized. Why do you care about non-differentiability at the origin when it should be the case that $w_i \approx D_iu$? Does the gradient even vanish? $\endgroup$ Commented Mar 24 at 9:37
  • 1
    $\begingroup$ Python libraries like CVXPY were designed so you can write the optimization problem and, as long as it is convex, the solver figures out what to do and you don't need to worry about theory, differentiability, etc. For most people, life is too short to learn mathematics $\endgroup$ Commented Mar 24 at 9:46
  • 1
    $\begingroup$ You might want to take a look at tools like CVXPYgen, which might generate C code from the description of the optimization problem. I heard that SpaceX uses CVXPY to land its rockets vertically $\endgroup$ Commented Mar 24 at 10:02

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.