Regularized Least Squares - Generalized Tikhonov Regularization

In Image Restoration, a true image $f$ (in vector form) can be related to degraded data $y$ through a linear model of the form

$$y = Hf + n$$

where $H$ is a 2D blurring matrix and $n$ is a noise vector and it's required to get $f$ from knowing $y$.

It is necessary to rely on a regularization to stabilize the inversion of ill-posed problem. Through the regularization, the problem is replaced by the one of seeking an estimate $f$ to minimize the Lagrangian:

$$\min_f ||y-Hf||^2_2 + \alpha||Cf||^2_2$$

Where $C$ is a matrix represents a high pass filter, I have read that there are ways to automatically determine the optimum value for the lagrange multiplier $\alpha$ but I didn't understand any thing I'm not a mathematics geek.

Could you explain the way to choose the optimum $\alpha$? Are there any simple tutorials? What are the most powerful algorithms to choose $\alpha$?

thanks,

If one assume the matrix $C$ is the derivative matrix (Finite Differences) then the model above is the MAP where the prior for image derivatives is a Normal Distribution.

In that case one could easily connect the parameter of $\alpha$ to the ratio between the variance of the noise in the image and the variance of the derivative distribution.

Let

$$f_{\alpha,n}=\operatorname{argmin}_f\|Hf-y\|^2_2+\alpha\|Cf\|_2^2,$$

be the Tikhonov regularised solution and $$f^\dagger=H^\dagger y^\dagger$$ be the solution we are trying to approximate, where $$y^\dagger=y-n$$ and $$H^\dagger:\operatorname{range}H\oplus\operatorname{range}H^\perp\to\ker H^\perp$$ is the Moore-Penrose pseudo-inverse of $$H$$.

The optimal parameter $$\alpha_{\text{opt}}$$ can then defined be defined as

$$\alpha_{\text{opt}}:=\operatorname{argmin}_\alpha\|f_{\alpha,n}-f^\dagger\|.$$

Of course, this is not a parameter choice rule per se, as it requires knowledge of $$f^\dagger$$. There are a number of parameter choice rules, however, which you can use to estimate the optimal parameter depending on how much knowledge you have. Parameter choice rules can essentially be split into three categories: a-priori, a-posteriori and heuristic.

An a-priori parameter choice rule

If you know $$\delta:=\|n\|$$ and also the smoothness of $$f^\dagger$$, i.e., you know $$\mu$$, where $$f^\dagger\in\operatorname{range}(H^\ast H)^\mu$$, then you can select the parameter as

$$\alpha_\ast\sim\delta^\frac{2}{2\mu+1},$$

which yields optimal convergence rates for Tikhonov regularisation if $$\mu\le 1$$.

An a-posteriori parameter choice rule

If you do not know $$\mu$$, but you have knowledge of the noise-level, $$\delta$$, then you can use the Morozov's discrepancy principle:

$$\alpha_\ast=\sup\{\alpha:\|Hf_{\alpha,n}-y\|\le\tau\delta\},$$

for a constant $$\tau\ge 1$$.

A couple of heuristic parameter choice rules

If you have neither knowledge of $$\mu$$ nor $$\delta$$, then you can use one of the so-called heuristic parameter choice rules. I will list two:

The quasi-optimality rule selects the parameter as

$$\alpha_\ast=\operatorname{argmin}_\alpha\alpha\|\frac{\mathrm{d}}{\mathrm{d}\alpha}f_{\alpha,n}\|$$

and the heuristic discrepancy rule (also known as the Hanke-Raus rule) chooses

$$\alpha_\ast=\operatorname{argmin}_\alpha\frac{\|Hf_{\alpha,n}-y\|}{\sqrt{\alpha}}.$$

Note, however, that the drawback of the aforementioned heuristic rules is that they only work whenever $$n\in\mathcal{N}_p$$, where

$$\mathcal{N}_p:=\left\{n:\alpha^{2p}\int_\alpha^{\|H\|^2+}\lambda^{-1}\,\mathrm{d}\|F_\lambda n\|^2\le C\int_0^\alpha\lambda^{2p-1}\,\mathrm{d}\|F_\lambda n\|^2\text{ for all }\alpha>0\right\},$$

where $$\{F_\lambda\}_\lambda$$ denotes the spectral family of $$HH^\ast$$, with $$p=1$$ for the heuristic discrepancy rule and $$p=2$$ for the quasi-optimality rule. In particular, $$\mathcal{N}_2\subset\mathcal{N}_1$$, although the quasi-optimality rule tends to perform better when it works. It's important to note that the above noise condition is not particularly restrictive and excludes the worst case (in which heuristic rules are known not to converge).

Actually, I would recommend the quasi-optimality rule. The L-curve rule, mentioned in the comments, tends not to perform as well and moreover, does not have the theoretical backing of the other rules. For numerical comparisons, I recommend a paper by Bauer and Lukas, as well as the PhD thesis of Palm.

References: Regularization of Inverse Problems, Engl, Hanke, Neubauer - https://books.google.at/books/about/Regularization_of_Inverse_Problems.html?id=VuEV-Gj1GZcC&redir_esc=y

Convergence analysis of minimization-based noise level-free parameter choice rules for linear ill-posed problems, Kindermann - https://etna.ricam.oeaw.ac.at/volumes/2011-2020/vol38/abstract.php?vol=38&pages=233-257

Comparing parameter choice methods for regularization of ill-posed problems, Bauer, Lukas - https://www.sciencedirect.com/science/article/abs/pii/S0378475411000607

Numerical comparison of regularization algorithms, Palm - http://dspace.ut.ee/handle/10062/14623?locale-attribute=en

• Good information. I think that in image restoration $f^\dagger$ is not necessarily the vector that we want to approximate, as $f^\dagger$ incorporates no prior knowledge about natural images (such as adjacent pixels tending to have similar intensity values). – littleO Sep 23 '18 at 18:51
• @littleO Is prior information not accounted for by the regularisation functional $\mathcal{R}$, e.g. when we minimise $\frac{1}{2}\|Hf-y\|^2+\alpha\mathcal{R}(f)$? – Kemal Raik Oct 4 at 13:24