Article Contents

2023, Volume 17, Issue 3: 562-583. Doi: 10.3934/ipi.2022062

This issue Previous Article Imaging of conductivity distribution based on a combined reconstruction method in brain electrical impedance tomography Next Article Stable determination of an anisotropic inclusion in the Schrödinger equation from local Cauchy data

A Majorization-Minimization Golub-Kahan bidiagonalization method for $ \ell_{2}-\ell_{q} $ mimimization with applications in image restorization

Wenqian Zhang^1, and
Guangxin Huang^1,2, ,

1.
College of Mathematics and Physics, Geomathematics Key Laboratory of Sichuan, Chengdu University of Technology, China
2.
College of Computer Science and Cyber Security (Oxford Brookes College), Chengdu University of Technology, China

^*Corresponding author: Guangxin Huang
^*Corresponding author: Guangxin Huang

Received: January 2022

Revised: September 2022

Early access: November 2022

Published: June 2023

Abstract / Introduction Full Text(HTML) Figure(11) / Table(6) Related Papers Cited by

Abstract

An image restorization problem is often modelled as a discrete ill-posed problem. In general, its solution, even if it exists, is very sensitive to the perturbation in the data. Regularization methods reduces the sensitivity by replacing this problem with a minimization problem with a fidelity term and $ \ell_{q} $ regularization term. In order to improve the sparsity of the solution, we only consider the case of $ 0<q\leq1 $ in this paper. This paper presents a majorization-minimization Golub-Kahan bidiagonalization algorithm to solve this kind of minimization problems. The solution subspace is extended by the Golub-Kahan bidiagonalization process. The restarted case is also considered. The regularization parameter is determined by using the discrepancy principle. Several examples in image restorization are shown for the proposed methods.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Figure 1. Tested image $ \texttt{Lena}$: (a) Corrupted image (band = 4, sigma = 1, noise level $ \nu = 1\cdot 10^{-3} $), (b) original image, image restored by Algorithm 4 for the (c) $ \ell_2 $-$ \ell_{0.3} $ model, (d) $ \ell_2 $-$ \ell_{0.5} $ model, (e) $ \ell_2 $-$ \ell_{0.7} $ model, (f) $ \ell_2 $-$ \ell_{1} $ model

Download: Full-size image PowerPoint slide

Figure 2. Tested image $ \texttt{satellite}$: (a) Corrupted image (band = 5, sigma = 1.5, noise level $ \nu = 1\cdot 10^{-2} $), (b) original image, image restored by (c) Algorithm 1, (d) Algorithm 4 for the $ \ell_{2} $-$ \ell_1 $ model

Download: Full-size image PowerPoint slide

Figure 3. Example 4.2: The diagram of relative error $ e_k $ and number of iterations to Algorithms 1 and 4 for the $ \ell_{2}-\ell_{1} $ model with (a) band = 5, sigma = 1.5, noise level $ \nu = 1\cdot 10^{-2} $; (b) band = 3, sigma = 1, noise level $ \nu = 1\cdot 10^{-3} $

Download: Full-size image PowerPoint slide

Figure 4. Tested image $ \texttt{QRcode}$: (a) Corrupted image (band = 7, sigma = 2, noise level $ \nu = 1\cdot 10^{-2} $), (b) original image, image restored by (c) Algorithm 1, (d) Algorithm 2, (e) Algorithm 4, (f) Algorithm 5 for the $ \ell_{2} $-$ \ell_{0.5} $ model

Download: Full-size image PowerPoint slide

Figure 5. Example 4.3: The diagram of relative error $ e_k $ and number of iterations of Algorithms 1, 2, 4 and 5 for the $ \ell_{2}-\ell_{0.5} $ model with (a) band = 7, sigma = 2, noise level $ \nu = 1\cdot 10^{-2} $; (b) band = 4, sigma = 1, noise level $ \nu = 1\cdot 10^{-3} $

Download: Full-size image PowerPoint slide

Figure 6. Tested image $ \texttt{MRI}$: (a) Corrupted image (band = 10, noise level $ \nu = 1\cdot 10^{-3} $), (b) original image, image restored by (c) Algorithm 2, (d) Algorithm 6, (e) Algorithm 5 for the $ \ell_{2} $-$ \ell_{1} $ model

Download: Full-size image PowerPoint slide

Figure 7. Example 4.4: The diagram of relative error $ e_k $ and number of iterations of Algorithms 2, 5, 6 for the $ \ell_{2}-\ell_{1} $ model with band = 10 and noise level $ \nu = 1\cdot 10^{-3} $

Download: Full-size image PowerPoint slide

Figure 8. Tested image $ \texttt{Lattice}$: (a) Corrupted image (band = 12, noise level $ \nu = 1\cdot 10^{-3} $), (b) original image, image restored by (c) Algorithm 2, (d) Algorithm 6, (e) Algorithm 5 for the $ \ell_{2} $-$ \ell_{1} $ model

Download: Full-size image PowerPoint slide

Figure 9. Example 4.5: The diagram of relative error $ e_k $ and number of iterations to Algorithms 2, 5, 6 for the $ \ell_{2}-\ell_{1} $ model with band = 12, noise level $ \nu = 1\cdot 10^{-2} $

Download: Full-size image PowerPoint slide

Figure 10. Tested image $ \texttt{CDUT}$: (a) Corrupted image (band = 14, noise level $ \nu = 1\cdot 10^{-2} $), (b) original image, image restored by (c) Algorithm 2, (d) Algorithm 6, (e) Algorithm 5 for the $ \ell_{2} $-$ \ell_{1} $ model

Download: Full-size image PowerPoint slide

Figure 11. Example 4.6: The diagram of relative error $ e_k $ and number of iterations to Algorithms 2, 5, 6 for the $ \ell_{2}-\ell_{1} $ model with band = 14 and noise level $ \nu = 1\cdot 10^{-2} $

Download: Full-size image PowerPoint slide

Table 1. Example 4.1: The comparison of Algorithm 4 for the $ \ell_2 $-$ \ell_{q} $ model with different $ q = 1 $, $ 0.7 $, $ 0.5 $ and $ 0.3 $ on test image $ \texttt{Lena}$ corrupted by different levels of blur and Gaussian noise

band=5, sigma=2, noise level $ \nu = 1\cdot 10^{-2} $
$ q $	$ \mu $	SNR	relative error	iterative number
0.3	$ 1.0\cdot10^{-1} $	13.55	$ 7.71\cdot 10^{-2} $	26
0.5	$ 1.0\cdot10^{-1} $	13.55	$ 7.71\cdot 10^{-2} $	26
0.7	$ 1.0\cdot10^{-1} $	13.55	$ 7.71\cdot 10^{-2} $	26
1	$ 1.0\cdot10^{-1} $	13.55	$ 7.71\cdot 10^{-2} $	27

band=4, sigma=1, noise level $ \nu = 1\cdot 10^{-3} $
$ q $	$ \mu $	SNR	relative error	iterative number
0.3	$ 1.0\cdot 10^{-1} $	24.69	$ 2.18\cdot 10^{-2} $	126
0.5	$ 1.0\cdot 10^{-1} $	24.69	$ 2.18\cdot 10^{-2} $	124
0.7	$ 1.0\cdot 10^{-1} $	24.69	$ 2.18\cdot 10^{-2} $	121
1	$ 1.0\cdot 10^{-1} $	28.61	$ 2.18\cdot 10^{-2} $	92

| Show Table

DownLoad: CSV

Table 2. Example 4.2: The comparison of Algorithms 1 and 4 for the $ \ell_2 $-$ \ell_{0.5} $ and $ \ell_{2} $-$ \ell_1 $ models on test image $ \texttt{satellite}$ corrupted by different levels of blur and Gaussian noise

blur		noise	$ \mu $		SNR		relative error		iterative number
band	sigma		Algo.1	Algo.4	Algo.1	Algo.4	Algo.1	Algo.4	Algo.1	Algo.4
					$ \ell_2 $-$ \ell_{0.5} $
7	2	0.05	$ 1.5\cdot 10^{-2} $	$ 9.7\cdot 10^{-3} $	12.67	12.78	$ 2.22\cdot 10^{-1} $	$ 2.20\cdot 10^{-1} $	11	9
5	1.5	0.01	$ 1.5\cdot 10^{-2} $	$ 2.3\cdot 10^{-3} $	14.51	15.39	$ 1.80\cdot 10^{-1} $	$ 1.63\cdot 10^{-1} $	44	47
3	1	0.001	$ 3.0\cdot 10^{-2} $	$ 1.9\cdot 10^{-4} $	16.80	21.14	$ 1.45\cdot 10^{-1} $	$ 8.77\cdot 10^{-2} $	114	85
					$ \ell_2 $-$ \ell_{1} $
7	2	0.05	$ 1.5\cdot 10^{-2} $	$ 9.7\cdot 10^{-3} $	12.70	12.82	$ 2.22\cdot 10^{-1} $	$ 2.19\cdot 10^{-1} $	13	10
5	1.5	0.01	$ 1.5\cdot 10^{-2} $	$ 2.3\cdot 10^{-3} $	14.89	15.76	$ 1.80\cdot 10^{-1} $	$ 1.63\cdot 10^{-1} $	45	50
3	1	0.001	$ 3.0\cdot 10^{-2} $	$ 1.9\cdot 10^{-4} $	16.80	21.23	$ 1.45\cdot 10^{-1} $	$ 8.68\cdot 10^{-2} $	109	92

| Show Table

DownLoad: CSV

Table 3. Example 4.3: The comparison of Algorithms 1, 2, 4 and 5 for the $ \ell_2 $-$ \ell_1 $ and $ \ell_{2} $-$ \ell_{0.5} $ models on test image $ \texttt{QRcode}$ corrupted by different levels of blur and Gaussian noise

					$ \ell_2 $-$ \ell_{0.5} $
blur		noise	$ \mu $				SNR
band	sigma		Algo.1	Algo.2	Algo.4	Algo.5	Algo.1	Algo.2	Algo.4	Algo.5
7	2	0.01	$ 2.1\cdot 10^{-1} $	$ 2.1\cdot 10^{-1} $	$ 2.2\cdot10^{-3} $	$ 1.0\cdot10^{-2} $	9.44	10.98	13.31	21.48
4	1	0.001	$ 1.6\cdot 10^{-1} $	$ 1.6\cdot 10^{-1} $	$ 5.8\cdot 10^{-4} $	$ 5.8\cdot 10^{-4} $	13.49	22.77	24.67	Inf
			PSNR				SSIM
			Algo.1	Algo.2	Algo.4	Algo.5	Algo.1	Algo.2	Algo.4	Algo.5
7	2	0.01	13.09	16.34	18.57	25.52	0.490	0.650	0.519	0.878
4	1	0.001	16.70	26.99	29.13	Inf	0.735	0.953	0.753	1
			relative error				iterative number
			Algo.1	Algo.2	Algo.4	Algo.5	Algo.1	Algo.2	Algo.4	Algo.5
7	2	0.01	$ 3.37\cdot 10^{-1} $	$ 2.83\cdot 10^{-1} $	$ 2.16\cdot 10^{-1} $	$ 8.44\cdot 10^{-2} $	3	34	90	26
4	1	0.001	$ 2.12\cdot 10^{-1} $	$ 7.27\cdot 10^{-2} $	$ 5.84\cdot 10^{-2} $	0	3	49	136	25

					$ \ell_2 $-$ \ell_{1} $
blur		noise	$ \mu $				SNR
band	sigma		Algo.1	Algo.2	Algo.4	Algo.5	Algo.1	Algo.2	Algo.4	Algo.5
7	2	0.01	$ 2.1\cdot 10^{-1} $	$ 2.1\cdot 10^{-2} $	$ 1.6\cdot10^{-3} $	$ 1.4\cdot 10^{-2} $	9.21	10.63	13.34	20.97
4	1	0.001	$ 1.6\cdot 10^{-1} $	$ 1.6\cdot 10^{-1} $	$ 5.8\cdot10^{-4} $	$ 5.8\cdot 10^{-4} $	13.10	22.76	24.10	Inf
			PSNR				SSIM
			Algo.1	Algo.2	Algo.4	Algo.5	Algo.1	Algo.2	Algo.4	Algo.5
7	2	0.01	12.58	16.00	18.51	25.00	0.488	0.629	0.508	0.875
4	1	0.001	16.16	26.98	28.64	Inf	0.740	0.953	0.752	1
			relative error				iterative number
			Algo.1	Algo.2	Algo.4	Algo.5	Algo.1	Algo.2	Algo.4	Algo.5
7	2	0.01	$ 3.46\cdot 10^{-1} $	$ 2.94\cdot 10^{-1} $	$ 2.15\cdot 10^{-1} $	$ 8.94\cdot 10^{-2} $	3	35	90	26
4	1	0.001	$ 2.21\cdot 10^{-1} $	$ 7.28\cdot 10^{-2} $	$ 6.24\cdot 10^{-2} $	0	3	49	135	25

| Show Table

DownLoad: CSV

Table 4. Example 4.4: The comparison of the effects of Algorithms 2, 5, 6 for the $ \ell_2 $-$ \ell_1 $ model on test image $\texttt{MRI} $ corrupted by different levels of blur and Gaussian noise

				$ \ell_2 $-$ \ell_{1} $
noise	$ \mu $			SNR			PSNR
	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5
0.01	$ 9.5\cdot 10^{-3} $	$ 6.3\cdot 10^{-1} $	$ 7.0\cdot 10^{-1} $	17.70	11.99	18.37	28.75	24.12	29.55
0.001	$ 3.0\cdot 10^{-2} $	$ 6.9\cdot 10^{-3} $	$ 1.3\cdot 10^{-3} $	25.54	23.85	27.42	36.70	35.31	38.71
	SSIM			relative error			iterative number
	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5
0.01	0.473	0.431	0.483	$ 1.30\cdot 10^{-1} $	$ 2.51\cdot 10^{-1} $	$ 1.21\cdot 10^{-1} $	50	150	134
0.001	0.711	0.700	0.715	$ 5.28\cdot 10^{-2} $	$ 6.42\cdot 10^{-2} $	$ 4.26\cdot 10^{-2} $	137	150	142

| Show Table

DownLoad: CSV

Table 5. Example 4.5: The comparison of the effects of Algorithms 2, 5, 6 for the $ \ell_2 $-$ \ell_1 $ model on test image $ \texttt{Lattice}$ corrupted by different levels of blur and Gaussian noise

				$ \ell_2 $-$ \ell_{1} $
noise	$ \mu $			SNR			PSNR
	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5
0.01	$ 1.1\cdot 10^{-2} $	$ 3.3\cdot 10^{-3} $	$ 1.0\cdot 10^{-2} $	15.30	17.96	20.54	22.30	26.58	27.42
0.001	$ 2.6\cdot 10^{-3} $	$ 1.5\cdot 10^{-4} $	$ 2.3\cdot 10^{-5} $	17.77	22.29	Inf	24.46	29.38	Inf
	SSIM			relative error			iterative number
	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5
0.01	0.707	0.566	0.736	$ 1.72\cdot 10^{-1} $	$ 1.27\cdot 10^{-1} $	$ 9.40\cdot 10^{-2} $	49	150	47
0.001	0.895	0.668	1	$ 1.29\cdot 10^{-1} $	$ 7.68\cdot 10^{-2} $	0	74	150	25

| Show Table

DownLoad: CSV

Table 6. Example 4.6: The comparison of the effects of Algorithms 2, 5, 6 for the $ \ell_2 $-$ \ell_1 $ model on test image $ \texttt{CDUT}$ corrupted by different levels of blur and Gaussian noise

				$ \ell_2 $-$ \ell_{1} $
noise	$ \mu $			SNR			PSNR
	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5
0.03	$ 2.4\cdot 10^{-2} $	$ 1.3\cdot 10^{-3} $	$ 5.8\cdot 10^{-2} $	13.01	11.69	18.17	25.29	25.27	29.76
0.01	$ 4.4\cdot 10^{-2} $	$ 5.0\cdot 10^{-4} $	$ 1.0\cdot 10^{-30} $	24.98	20.68	Inf	36.74	32.87	Inf
	SSIM			relative error			iterative number
	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5	Algo.2	Algo.6	Algo.5
0.03	0.704	0.430	0.919	$ 2.24\cdot 10^{-1} $	$ 2.60\cdot 10^{-1} $	$ 1.23\cdot 10^{-1} $	49	150	26
0.01	0.979	0.644	1	$ 5.63\cdot 10^{-2} $	$ 9.24\cdot 10^{-2} $	0	49	150	25

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Buccini, G. Huang and L. Reichel, On the choice of regularization matrix for an $\ell_ 2-\ell_q$ minimization method for image restoration, Appl. Numer. Math., 164 (2021), 211-221. doi: 10.1016/j.apnum.2020.11.004.
[2]	A. Buccini and L. Reichel, An $\ell_ 2-\ell_q$ regularization method for large discrete ill-posed problems, J. Sci. Comput., 78 (2019), 1526-1549. doi: 10.1007/s10915-018-0816-5.
[3]	D. Calvetti and L. Reichel, Tikhonov regularization of large linear problems, BIT Numer. Math., 43 (2003), 263-283. doi: 10.1023/A:1026083619097.
[4]	J. Cornelis, N. Schenkels and W. Vanroose, Projected Newton method for noise constrained Tikhonov regularization, Inverse. Probl., 36 (2020), 055002, 28 pp. doi: 10.1088/1361-6420/ab7d2b.
[5]	J. Cornelis and W. Vanroose, Projected Newton method for noise constrained $\ell_p$ regularization, Inverse. Probl., 36 (2020), 125004, 32 pp. doi: 10.1088/1361-6420/abb2fc.
[6]	M. Donatelli, A. Neuman and L. Reichel, Square regularization matrices for large linear discrete ill-posed problems, Numer. Linear. Algebr., 19 (2012), 896-913. doi: 10.1002/nla.1833.
[7]	L. Dykes, G. Huang, S. Noschese and L. Reichel, Regularization matrices for discrete ill-posed problems in several space-dimensions, Numer. Linear Algebr., 25 (2018), 1-16. doi: 10.1002/nla.2163.
[8]	S. Gazzola, P. Novati and M. R. Russo, On Krylov projection methods and Tikhonov regularization, Electron. Trans. Numer. Anal, 44 (2015), 83-123.
[9]	S. Gazzola, E. Onunwor and L. Reichel, On the Lanczos and Golub-Kahan reduction methods applied to discrete ill-posed problems, Numer. Linear. Algebr., 23 (2016), 187-204. doi: 10.1002/nla.2020.
[10]	P. C. Hansen, Regularization tools version 4.0 for Matlab 7.3, Numer. Algorithms, 46 (2007), 189-194. doi: 10.1007/s11075-007-9136-9.
[11]	P. C. Hansen, Discrete Inverse Problems: Insight and Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. doi: 10.1137/1.9780898718836.
[12]	P. C. Hansen, Rank-Deficient and Discrete Ill-posed Problems: Numerical Aspects of Linear Inversion, SIAM Monographs on Mathematical Modeling and Computation. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. doi: 10.1137/1.9780898719697.
[13]	M. E. Hochstenbach and L. Reichel, An iterative method for Tikhonov regularization with a general linear regularization operator, J. Integral. Equ. Appl., 22 (2010), 465-482. doi: 10.1216/JIE-2010-22-3-465.
[14]	G. Huang, A. Lanza and S. Morigi, Majorization minimization generalized Krylov subspace methods for $\ell_p-\ell_q$ optimization applied to image restoration, BIT Numer. Math., 57 (2017), 351-378. doi: 10.1007/s10543-016-0643-8.
[15]	G. Huang, L. Reichel and F. Yin, Projected nonstationary iterated Tikhonov regularization, BIT Numer. Math., 56 (2016), 467-487. doi: 10.1007/s10543-015-0568-7.
[16]	J. Lampe, L. Reichel and H. Voss, Large-scale Tikhonov regularization via reduction by orthogonal projection, Linear. Algebra. Appl., 436 (2012), 2845-2865. doi: 10.1016/j.laa.2011.07.019.
[17]	A. Lanza, S. Morigi, L. Reichel and F. Sgallari, A generalized Krylov subspace method for $\ell_p-\ell_q$ minimization, SIAM J. Sci. Comput., 37 (2015), 30-50. doi: 10.1137/140967982.
[18]	P. Novati and M. R. Russo, Adaptive Arnoldi-Tikhonov regularization for image restoration, Numer. Algorithms, 65 (2014), 745-757. doi: 10.1007/s11075-013-9712-0.