Converting Hadamard Product into Matrix Multiplication in Image Deconvolution with Total Variation (TV) Using ADMM

Question

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

Answer 1

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) $$