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

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

How

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

• 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? Jul 22 at 4:16
• Yes. It is correct.
– Royi
Jul 22 at 4:30
• 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}$$ Jul 22 at 6:15