\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

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
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Comparison for $ Q(x) $ with $ p = 1/3 $ by taking different $ \alpha $

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

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

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

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

    Figure 6.  Comparison results of recoverability

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

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

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

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

    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

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

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

    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
    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
  • [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. BrucksteinD. 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. CaoJ. 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èsM. 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. ChenD. D. GeZ. 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. DeVoreB. 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. DuarteM. DavenportD. TakharJ. LaskaT. SunK. 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. GaoY. 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. JiangS.-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. JiangS.-C. FangT. 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. LaiY. 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. LiY. BaiC. 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. LouP. H. YinQ. 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. MerhejC. DiabM. 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. TakedaS. 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. WangW. 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. XuX. Y. ChangF. 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. ZhangW. 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. ZhangJ. 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.
  • 加载中

Figures(13)

Tables(4)

SHARE

Article Metrics

HTML views(423) PDF downloads(466) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return