How to Solve Image Denoising with Total Variation Prior Using ADMM?

Question

I was looking at some articles or Wikipedia on denoising images using the Total Variation norm. The setup is the Rudin Osher Fatemi (ROF) scheme, and the corresponding equation is:

$$ F(u)=\int_{\Omega}|D u|+\lambda \int_{\Omega}(K u-f)^{2} d x $$

Some of the sources mentioned using the ADMM optimizer to solve this denoising problem. But I was hoping that someone might be able to direct me to some code to show an implementation of this approach. Code in MATLAB, Julia, or Python would be excellent, just something to get started with.

Thanks.

Answer 1

Formulation of the Denoising Problem

The problem is given by:

$$ \arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda \operatorname{TV} \left( x \right) = \arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\| D x \right\|}_{1} $$

Where $ D $ is the column stacked derivative operator.

In the above I used the Anisotropic TV Norm.

Solution by ADMM

The ADMM problem will be formulated as:

$$ $$

$$\begin{aligned} \arg \min_{x, z} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\| z \right\|}_{1} \\ \text{subject to} \quad & D x = z \end{aligned}$$

The ADMM will have 3 steps:

1. vX = mC \ (vY + (paramRho * mD.' * (vZ - vU)));.
2. vZ = ProxL1(mD * vX + vU, paramLambda / paramRho);.
3. vU = vU + mD * vX - vZ;.

Where mC = decomposition(mI + paramRho * (mD.' * mD), 'chol');.

I coded this solution in a MATLAB function - SolveProxTvAdmm().
I compared it to a reference by CVX:

The full code is available on my StackExchange Signal Processing Q75231 GitHub Repository (Look at the SignalProcessing\Q75231 folder).

Remark: For the Deblurring problem, open a new question and I will post a code for it as well.

Answer 2

I have done a bit of this myself and you'd need to adapt.
There is a Douglas Rachford self implemented and a primal dual approach here implemented in Recovery of Fusion Frame Structured Signal via Compressed Sensing.

Note that Clarice Poon (Bath University) had some nice tutorials on it.

Another source is the Numerical Tours from Gabriel Peyre. See Denoising by Sobolev and Total Variation Regularization.