A new hybrid $ l_p $-$ l_2 $ model for sparse solutions with applications to image processing

Xuerui Gao; Yanqin Bai; Shu-Cherng Fang; Jian Luo; Qian Li

doi:10.3934/jimo.2021211

Article Contents

2023, Volume 19, Issue 2: 890-915. Doi: 10.3934/jimo.2021211

This issue Previous Article A novel algorithm for approximating common solution of a system of monotone inclusion problems and common fixed point problem Next Article Distributionally robust chance constrained svm model with $\ell_2$-Wasserstein distance

A new hybrid $ l_p $-$ l_2 $ model for sparse solutions with applications to image processing

1.
Department of Mathematics, Shanghai University, Shanghai 200444, China
2.
Edward P. Fitts Department of Industrial and, Systems Engineering, North Carolina State University, Raleigh, NC 27695-7906, USA
3.
School of Management Science and, Engineering, Dongbei University of Finance and Economics, Dalian 116025, China
4.
School of Mathematics, Physics and, Statistics, Shanghai University of Engineering Science, Shanghai 201620, China

^* Corresponding author: Yanqin Bai (yqbai@shu.edu.cn)
^* Corresponding author: Yanqin Bai (yqbai@shu.edu.cn)

Received: July 31, 2021

Revised: September 30, 2021

Early access: December 2021

Published: February 2023

This work has been sponsored by the National Natural Science Foundations of China Grant 12171307, 11901382 and 71701035; The US Army Research Office Grant W911NF-15-1-0223; Chinese NNF Grant 71620107003 for Major International Joint Research Project

Abstract Full Text(HTML) Figure(13) / Table(4) Related Papers Cited by

Abstract

Finding sparse solutions to a linear system has many real-world applications. In this paper, we study a new hybrid of the $ l_p $ quasi-norm ($ 0 <p< 1 $) and $ l_2 $ norm to approximate the $ l_0 $ norm and propose a new model for sparse optimization. The optimality conditions of the proposed model are carefully analyzed for constructing a partial linear approximation fixed-point algorithm. A convergence proof of the algorithm is provided. Computational experiments on image recovery and deblurring problems clearly confirm the superiority of the proposed model over several state-of-the-art models in terms of the signal-to-noise ratio and computational time.

Keywords:

Sparse optimization,
hybrid of the l_p quasi-norm and l₂ norm,
optimality conditions,
image processing.

Mathematics Subject Classification: Primary: 90C26, 90C46, 90C90; Secondary: 65K05.

Citation:

FullText(HTML)

Figure 1. Comparison for $ Q(x) $ with $ p = 1/3 $ by taking different $ \alpha $

Download: Full-size image PowerPoint slide

Figure 2. Comparison for $ Q^*({{\mathit{\boldsymbol{x}}}}) $ with different $ p $

Download: Full-size image PowerPoint slide

Figure 3. Comparison between $ Q^*(x) $ and $ Q^*_t(x) $ with $ p = 1/3 $

Download: Full-size image PowerPoint slide

Figure 4. Contours of $ F(x) $ with different $ \lambda $ in two dimension

Download: Full-size image PowerPoint slide

Figure 5. 256 $ \times $ 256 Shepp-Logan head phantom and the images recovered by PLAFPA$ _p $

Download: Full-size image PowerPoint slide

Figure 6. Comparison results of recoverability

Download: Full-size image PowerPoint slide

Figure 7. The original images and the observed blurred noise images

Download: Full-size image PowerPoint slide

Figure 8. The values of SNR obtained by PLAFPA$ _p $ with different $ p $ at different numbers of iterations for image deblurring

Download: Full-size image PowerPoint slide

Figure 9. The values of SNR obtained by tested methods at different numbers of iterations for image deblurring

Download: Full-size image PowerPoint slide

Figure 10. The results of "Cameraman" and "Lena" image deblurring obtained by different tested methods

Download: Full-size image PowerPoint slide

Figure 11. The choice of $ \lambda $ for each tested method and the values of SNR obtained by tested methods at different numbers of iterations for the "Cameraman" image deblurring

Download: Full-size image PowerPoint slide

Figure 12. SNR value trend graph with different $ p $ for the method PLAFPA$ _p $

Download: Full-size image PowerPoint slide

Figure 13. $ \Phi(\eta) $ for $ \eta>0 $

Download: Full-size image PowerPoint slide

Table 1. Results of image recovery for the Shepp-Logan head phantom

Method		$ l/n_s $=0.51			$ l/n_s $=0.39			$ l/n_s $=0.25
Method		SNR	time	Iter	SNR	time	Iter	SNR	time	Iter
Soft		136.60	77.70	813	122.18	103.09	1000	89.72	94.73	1000
Half		173.20	10.20	94	169.09	15.87	139	161.68	33.04	306
PQA		160.46	18.36	183	155.84	27.23	285	52.80	42.77	438
H$ L_2 $-$ L_{p} $	$ p=1/5 $	173.80	10.06	94	169.43	13.63	135	162.50	28.59	298
	$ p=1/2 $	173.53	11.10	94	169.25	13.95	137	161.76	29.70	301
	$ p=4/5 $	173.92	9.66	97	169.64	13.91	143	162.10	31.96	322
PLAFPA$ _{p} $	$ p=1/5 $	175.08	6.19	76	170.14	8.63	113	163.09	21.10	256
	$ p=1/2 $	175.53	6.36	77	171.70	9.57	113	163.14	20.31	251
	$ p=4/5 $	175.35	6.30	80	171.58	9.86	121	163.99	21.98	279

| Show Table

DownLoad: CSV

Table 2. Results of image deblurring by PLAFPA$ _{8/9} $ at 500 iterations

	t	10	20	30	40	50	60	70	80	90	100
"Cameraman"	SNR	12.10	12.80	13.05	13.15	13.18	13.19	13.17	13.15	13.12	13.09
	time	10.47	12.53	14.09	15.46	15.92	17.11	17.68	18.31	19.26	20.62
"Lena"	t	10	20	30	40	50	60	70	80	90	100
	SNR	13.96	14.69	15.03	15.17	15.21	15.19	15.15	15.09	15.03	14.97
	time	49.38	54.88	60.33	64.82	68.99	72.83	76.09	78.31	80.59	83.25

| Show Table

DownLoad: CSV

Table 3. "Cameraman" image deblurring at different numbers of iterations

	Iter	100	200	300	400	500	600	700	800	900	1000
Soft	SNR	11.84	12.30	12.46	12.51	12.52	12.52	12.50	12.49	12.47	12.45
	time	1.68	2.75	3.98	4.95	6.12	7.29	8.43	9.51	10.57	11.84
Half	Iter	100	200	300	400	500	600	700	800	900	1000
	SNR	11.37	11.55	11.55	11.51	11.46	11.41	11.36	11.31	11.27	11.23
	time	3.67	5.24	7.68	10.30	13.50	15.88	18.47	20.42	23.21	25.10
PQA	Iter	100	200	300	400	500	600	700	800	900	1000
	SNR	11.98	12.55	12.74	12.77	12.72	12.64	12.54	12.42	12.30	12.18
	time	1.92	2.67	3.91	5.13	6.20	7.46	9.76	9.96	11.27	13.58
H$ L_2 $-$ L_{p} $ with $ p=8/9 $	Iter	100	200	300	400	500	600	700	800	900	1000
	SNR	11.99	12.60	12.81	12.88	12.87	12.82	12.76	12.68	12.59	12.50
	time	6.25	11.89	16.77	21.83	26.35	29.46	34.17	38.54	42.34	46.18
PLAFPA$ _{p} $ with $ p=8/9 $	Iter	100	200	300	400	500	600	700	800	900	1000
	SNR	11.87	12.56	12.88	13.05	13.15	13.20	13.22	13.28	13.22	13.22
	time	5.30	8.71	11.65	14.87	15.92	19.57	22.27	24.01	28.26	29.52

| Show Table

DownLoad: CSV

Table 4. "Lena" image deblurring at different numbers of iteration

	Iter	100	200	300	400	500	600	700	800	900	1000
Soft	SNR	14.86	14.81	14.67	14.53	14.43	14.35	14.29	14.23	14.18	14.13
	time	7.68	15.21	21.94	27.80	37.62	42.08	48.75	56.46	63.33	69.26
Half	Iter	100	200	300	400	500	600	700	800	900	1000
	SNR	14.02	13.85	13.70	13.55	13.43	13.34	13.26	13.19	13.13	13.07
	time	12.50	24.50	35.50	47.05	59.63	71.80	83.47	94.40	107.80	118.27
PQA	Iter	100	200	300	400	500	600	700	800	900	1000
	SNR	15.13	15.15	14.82	14.41	14.00	13.62	13.27	12.94	12.65	12.36
	time	7.63	14.91	22.60	29.37	33.68	43.74	52.27	57.88	65.31	73.68
H$ L_2 $-$ L_{p} $ with $ p=8/9 $	Iter	100	200	300	400	500	600	700	800	900	1000
	SNR	15.18	15.28	15.02	14.69	14.35	14.02	13.72	13.44	13.18	12.94
	time	27.11	47.28	66.64	85.65	95.97	123.68	143.52	159.69	176.60	192.09
PLAFPA$ _{p} $ with $ p=8/9 $	Iter	100	200	300	400	500	600	700	800	900	1000
	SNR	15.13	15.45	15.43	15.33	15.21	15.09	14.96	14.84	14.73	14.62
	time	24.76	38.04	50.43	62.75	68.99	85.64	95.82	105.12	116.96	120.00

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	E. Amaldi and V. Kann, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Theoret. Comput. Sci., 209 (1998), 237-260. doi: 10.1016/S0304-3975(97)00115-1.
[2]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202. doi: 10.1137/080716542.
[3]	A. M. Bruckstein, D. L. Donoho and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51 (2009), 34-81. doi: 10.1137/060657704.
[4]	W. F. Cao, J. Sun and Z. B. Xu, Fast image deconvolution using closed-form thresholding formulas of $L_q(q=\frac{1}{2}, \frac{2}{3})$ regularization, Journal of Visual Communication and Image Representation, 24 (2013), 31-41.
[5]	E. J. Candès, The restricted isometry property and its implications for compressed sensing, C. R. Math. Acad. Sci. Paris, 346 (2008), 589-592. doi: 10.1016/j.crma.2008.03.014.
[6]	E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory, 51 (2005), 4203-4215. doi: 10.1109/TIT.2005.858979.
[7]	E. J. Candès, M. B. Wakin and S. P. Boyd, Enhancing sparsity by reweighted $l_1$ minimization, J. Fourier Anal. Appl., 14 (2008), 877-905. doi: 10.1007/s00041-008-9045-x.
[8]	X. J. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Math. Program., 134 (2012), 71-99. doi: 10.1007/s10107-012-0569-0.
[9]	X. J. Chen, D. D. Ge, Z. Z. Wang and Y. Y. Ye, Complexity of unconstrained $L_2-L_p$ minimization, Math. Program., 143 (2014), 371-383. doi: 10.1007/s10107-012-0613-0.
[10]	R. A. DeVore, B. Jawerth and B. J. Lucier, Image compression through wavelet transform coding, IEEE Trans. Inform. Theory, 38 (1992), 719-746. doi: 10.1109/18.119733.
[11]	D. L. Donoho, De-noising by soft-thresholding, IEEE Trans. Inform. Theory, 41 (1995), 613-627. doi: 10.1109/18.382009.
[12]	D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.
[13]	M. Duarte, M. Davenport, D. Takhar, J. Laska, T. Sun, K. Kelly and R. Baraniuk, Single-pixel imaging via compressive sampling, IEEE Signal Processing Magazine, 25 (2008), 83-91. doi: 10.1109/MSP.2007.914730.
[14]	E. Elhamifar and R. Vidal, Sparse subspace clustering: Algorithm, theory, and applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35 (2013), 2765-2781. doi: 10.1109/TPAMI.2013.57.
[15]	J. Q. Fan and R. Z. Li, Variable selection via nonconcave penalized likelihood and its oracle properties, J. Amer. Statist. Assoc., 96 (2001), 1348-1360. doi: 10.1198/016214501753382273.
[16]	D. Foster and E. George, The risk inflation criterion for multiple regression, Ann. Statist., 22 (1994), 1947-1975. doi: 10.1214/aos/1176325766.
[17]	X. R. Gao, Y. Q. Bai and Q. Li, A sparse optimization problem with hybrid $L_2$-$L_p$ regularization for application of magnetic resonance brain images, J. Combinatorial Optimization, 42 (2019), 760-784. doi: 10.1007/s10878-019-00479-x.
[18]	S. Jiang, S.-C. Fang and Q. W. Jin, Sparse solutions by a quadratically constrained $l_q (0 < q < 1)$ minimization model, Informs J. Comput., 33 (2021), 511-530. doi: 10.1287/ijoc.2020.1004.
[19]	S. Jiang, S.-C. Fang, T. T. Nie and W. X. Xing, A gradient descent based algorithm for $l_p$ minimization, European J. Oper. Res., 283 (2020), 47-56. doi: 10.1016/j.ejor.2019.11.051.
[20]	M. J. Lai and J. Y. Wang, An unconstrained $l_q$ minimization with $0 < q \leq 1$ for sparse solution of underdetermined linear systems, SIAM J. Optim., 21 (2011), 82-101. doi: 10.1137/090775397.
[21]	M. J. Lai, Y. Xu and W. T. Yin, Improved iteratively reweighted least squares for unconstrained smoothed $l_q$ minimization, SIAM J. Numer. Anal., 51 (2013), 927-957. doi: 10.1137/110840364.
[22]	Q. Li, Y. Bai, C. Yu and Y.-X. Yuan, A new piecewise quadratic approximation approach for $L_0$ norm minimization problem, Sci. China Math., 62 (2019), 185-204. doi: 10.1007/s11425-017-9315-9.
[23]	Y. F. Lou, P. H. Yin, Q. He and J. Xin, Computing sparse representation in a highly coherent dictionary based on difference of $L_1$ and $L_2$, J. Sci. Comput., 64 (2015), 178-196. doi: 10.1007/s10915-014-9930-1.
[24]	N. Meinshausen and B. Yu, Lasso-type recovery of sparse representations for high-dimensional data, Ann. Statist., 37 (2009), 246-270. doi: 10.1214/07-AOS582.
[25]	D. Merhej, C. Diab, M. Khalil and R. Prost, Embedding prior knowledge within compressed sensing by neural networks, IEEE Transactions on Neural Networks, 22 (2011), 1638-1649. doi: 10.1109/TNN.2011.2164810.
[26]	B. Natraajan, Sparse approximate solutions to linear systems, SIAM J. Comput., 24 (1995), 227-234. doi: 10.1137/S0097539792240406.
[27]	I. Selesnick, Sparse regularization via convex analysis, IEEE Trans. Signal Process., 65 (2017), 4481-4494. doi: 10.1109/TSP.2017.2711501.
[28]	H. Takeda, S. Farsiu and P. Milanfar, Deblurring using regularized locally adaptive kernel regression, IEEE Trans. Image Process., 17 (2008), 550-563. doi: 10.1109/TIP.2007.918028.
[29]	R. Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B, 58 (1996), 267-288. doi: 10.1111/j.2517-6161.1996.tb02080.x.
[30]	Y. Wang, W. Q. Liu and G. L. Zhou, An efficient algorithm for non-convex sparse optimization, J. Ind. Manag. Optim., 15 (2019), 2009-2021. doi: 10.3934/jimo.2018134.
[31]	Z. B. Xu, X. Y. Chang, F. M. Xu and H. Zhang, $L_{1/2}$ regularization: A thresholding representation theory and a fast solver, IEEE Transactions on Neural Networks and Learning Systems, 23 (2012), 1013-1027.
[32]	B. C. Zhang, W. Hong and Y. R. Wu, Sparse microwave imaging: Principles and applications, Sci. China Inf. Sci., 55 (2012), 1722-1754. doi: 10.1007/s11432-012-4633-4.
[33]	C. Zhang, J. J. Wang and N. H. Xiu, Robust and sparse portfolio model for index tracking, J. Ind. Manag. Optim., 15 (2019), 1001-1015.
[34]	H. Zou, The adaptive lasso and its oracle properties, J. Amer. Statist. Assoc., 101 (2006), 1418-1429. doi: 10.1198/016214506000000735.