4
$\begingroup$

I would like to solve the following Image Deconvolution equation by ADMM. $$\mathbf { \min\frac{1}{2}\Vert{Cx-b}\Vert_2^2+\Vert w\circ (D x)\Vert_1 \tag 1}$$

Where, $x$ is a vector of unknown pixel values, $b$ is measurements,and $C$ is the point spread kernel, $D$ is the differential operator , $\circ$ is the element-wise multiplication operator, and $w$ is the weighting function which is related to the squared difference between the two neighboring pixels.

From the Stanford - EE 367 / CS 448I: Computational Imaging and Display Notes: Image Deconvolution (lecture 6), in ADMM notation,, the TV-regularized deconvolution problem is, $$\mathbf { \min\frac{1}{2}\Vert{Cx-b}\Vert_2^2+λ\Vert z\Vert_1 \tag 2}$$ $$\mathbf { subject\; to\;Dx-z=0 }$$

where, $D$ is represents the finite differences approximation of the horizontal and vertical image gradients.

[For the x-update equation(2)]

The proximal operator $\mathbf { prox_{f,ρ}}$ is following a quadratic program

$$\mathbf {prox_{f,p}(v)=argmin\frac{1}{2}\Vert{Cx-b}\Vert_2^2+\frac{ρ}{2}\Vert Dx-v\Vert_2^2 ,\qquad v=z-u \tag 3}$$

I write the objective function$(3)$ out as

$$\mathbf {\frac{1}{2}(Cx-b)^T(Cx-b)+\frac{ρ}{2}(Dx-v)^T(Dx-v) }$$

$$\mathbf {= \frac{1}{2}(x^TC^TCx-2x^TC^Tb+b^Tb)+ \frac{ρ}{2}(x^TD^TDx-2x^TD^Tv+v^Tv) \tag 4}$$

The gradient of Eq. 4,and , equated to zero, results in the normal equations, $$\mathbf {x= (C^TC+ρD^TD)^{-1} (C^Tb+ρD^Tv) \tag 5}$$

[What I want you to tell me]

How can I express Eq.(6) as Eq. (5)?  I tried to expand equation (1) as follows, is it correct?

$$\mathbf {prox_{f,p}(v)=argmin\frac{1}{2}\Vert{Cx-b}\Vert_2^2+\frac{ρ}{2}\Vert w\circ Dx-v\Vert_2^2 ,\qquad v=z-u \tag 6}$$

$$\mathbf {\frac{1}{2}(Cx-b)^T(Cx-b)+\frac{ρ}{2}(w\circ Dx-v)^T(w\circ Dx-v) }$$ $$\mathbf {= \frac{1}{2}(x^TC^TCx-2x^TC^Tb+b^Tb)+\\ \frac{ρ}{2}(x^T(D^T\circ w^T)(w\circ D)x-2x^T(D^T\circ w^T)v+v^Tv) \tag 7}$$

The gradient of Eq. 7,and , equated to zero, results in the normal equations, $$\mathbf {x= (C^TC+ρx^T(D^T\circ w^T)(w\circ D))^{-1} (C^Tb+ρ(D^T\circ w^T)v) \tag 8}$$

Eq.8 is True? Thanks for your answer.

How

$\endgroup$

1 Answer 1

1
$\begingroup$

Assuming we know how to solve:

$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| C \boldsymbol{x} - \boldsymbol{b} \right\|}_{2}^{2} + {\left\| E \boldsymbol{x} \right\|}_{1} $$

For any matrix $ E $ one could see that:

$$ \boldsymbol{w} \circ D \boldsymbol{x} = \operatorname{Diag} \left( \boldsymbol{w} \right) D \boldsymbol{x} = E \boldsymbol{x} $$

Where $ \operatorname{Diag} \left( \boldsymbol{w} \right) $ is a diagonal matrix built by the values of $ \boldsymbol{w} $.

So your problem can be rewritten:

$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| C \boldsymbol{x} - \boldsymbol{b} \right\|}_{2}^{2} + {\left\| \boldsymbol{w} \circ D \boldsymbol{x} \right\|}_{1} \Leftrightarrow \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| C \boldsymbol{x} - \boldsymbol{b} \right\|}_{2}^{2} + {\left\| E \boldsymbol{x} \right\|}_{1} $$

Regarding solving:

$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| C \boldsymbol{x} - \boldsymbol{b} \right\|}_{2}^{2} + \frac{\rho}{2} {\left\| \boldsymbol{w} \circ D \boldsymbol{x} - \boldsymbol{v} \right\|}_{2}^{2} $$

Then:

$$\begin{aligned} & \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| C \boldsymbol{x} - \boldsymbol{b} \right\|}_{2}^{2} + \frac{\rho}{2} {\left\| \boldsymbol{w} \circ D \boldsymbol{x} - \boldsymbol{v} \right\|}_{2}^{2} \\ & = \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| C \boldsymbol{x} - \boldsymbol{b} \right\|}_{2}^{2} + \frac{\rho}{2} {\left\| \operatorname{Diag} \left( \boldsymbol{w} \right) D \boldsymbol{x} - \boldsymbol{v} \right\|}_{2}^{2} \\ & = \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| C \boldsymbol{x} - \boldsymbol{b} \right\|}_{2}^{2} + \frac{\rho}{2} {\left\| E \boldsymbol{x} - \boldsymbol{v} \right\|}_{2}^{2} \end{aligned}$$

Then:

$$ \boldsymbol{x} = {\left( {C}^{T} C + \rho {E}^{T} E \right)}^{-1} \left( {C}^{T} \boldsymbol{x} + \rho {E}^{T} \boldsymbol{v} \right) $$

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. Should I think of $$\mathbf E=Diag(w)D$$, then $$\mathbf E^T=(Diag(w)D)^T=D^TDiag(w)^T$$ Is it OK? $\endgroup$ Jul 22, 2021 at 4:16
  • $\begingroup$ Yes. It is correct. $\endgroup$
    – Royi
    Jul 22, 2021 at 4:30
  • $\begingroup$ Let me check only one more thing. Equation(8) is correct? $$\mathbf {x= (C^TC+ρx^T(D^TDiag(w)^T)(Diag(w) D))^{-1} (C^Tb+ρ(D^TDiag( w)^T)v) \tag 8}$$ $\endgroup$ Jul 22, 2021 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.