• PDF
• Cite
• Share
Article Contents  Article Contents

# Smoothing Newton method for $\ell^0$-$\ell^2$ regularized linear inverse problem

• Sparse regression plays a very important role in statistics, machine learning, image and signal processing. In this paper, we consider a high-dimensional linear inverse problem with $\ell^0$-$\ell^2$ penalty to stably reconstruct the sparse signals. Based on the sufficient and necessary condition of the coordinate-wise minimizers, we design a smoothing Newton method with continuation strategy on the regularization parameter. We prove the global convergence of the proposed algorithm. Several numerical examples are provided, and the comparisons with the state-of-the-art algorithms verify the effectiveness and superiority of the proposed method.

Mathematics Subject Classification: Primary: 65F22; Secondary: 90C99.

 Citation: • • Figure 1.  From left to right: the hard thresholding operator $T_{2}(x)$ and corresponding approximations with uniform smoothing function for different $\epsilon$

Figure 2.  The density function

Figure 3.  The limiting form

Figure 4.  Results of random Gaussian matrix with a correlation coefficient $\tilde{\nu} = 0.2$ for strict sparse signal with $n = 1000, p = 2000, \delta = 1e-1, \lambda = 6.3e-01$

Figure 5.  Results of random Gaussian matrix with a correlation coefficient $\tilde{\nu} = 0.2$ for non-strict sparse signal with $n = 1000, p = 2000, \delta = 1e-1, \lambda = 2.1e-01$

Figure 6.  Results of Heaviside matrix for strict sparse signal with $n = 1000, p = 1000, \delta = 1e-1, \lambda = 2.3e-01$

Figure 7.  Results of Heaviside matrix for non-strict sparse signal with $n = 1000, p = 1000, \delta = 1e-1, \lambda = 1.2e-02$

Figure 8.  Results of inverse Laplace matrix for strict sparse signal with $n = 1000, p = 1000, \delta = 1e-3, \lambda = 1.4e-09$

Figure 9.  Results of inverse Laplace matrix for non-strict sparse signal with $n = 1000, p = 1000, \delta = 1e-4, \lambda = 7.1e-11$

Figure 10.  Results of Toeplitz matrix with $n = 1000, p = 1000, \delta = 1e-1, \lambda = 4.5e-01$

Figure 11.  Results of partial Toeplitz matrix with $n = 500, p = 1000, \delta = 1e-1, \lambda = 4.6e-01$

Figure 12.  The exact recovery probability of the support of SNM, LASSO, MCP and SCAD

Figure 13.  The exact recovery probability of the support of SNM, AIHT and FoBa for the same model (5)

Table 1.  The results of relative error $RelErr$ of all the solvers considered here

 Methods Gaussian matrix ($0.3$) Gaussian matrix ($0.8$) Heaviside matrix SNM 2.7e-07 (7.1e-08) 3.2e-07 (1.1e-07) 1.8e-06 (8.5e-07) AIHT 1.4e-03 (9.8e-03) 1.1e-01 (1.2e-01) 1.3e-01 (9.0e-02) FoBa 2.1e-07 (4.4e-08) 1.3e-01 (1.8e-01) 9.0e-07 (3.1e-07) LASSO 3.1e-02 (1.3e-03) 4.9e-02 (3.4e-02) 1.7e-01 (7.1e-02) MCP 2.1e-07 (4.4e-08) 1.1e-01 (1.3e-01) 1.4e-01 (3.5e-01) SCAD 2.1e-07 (4.4e-08) 8.9e-03 (5.2e-02) 9.0e-07 (3.1e-07)
• Figures(13)

Tables(1)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint