A NEW PENALIZED LEAST ABSOLUTE DEVIATION MODEL FOR HIGH DIMENSIONAL SPARSE LINEAR REGRESSION AND AN EFFICIENT SEQUENTIAL LINEAR PROGRAMMING ALGORITHM

摘要

The high dimensional sparse linear regression problem has many important applications in electronic engineering, statistics, and compressed sensing. In this paper, we introduce a new penalized least absolute deviation (LAD) model for the high dimensional sparse linear regression problem. First, we adopt the LAD model because it is suitable for data in the presence of outliers and provides a powerful technique for outlier robustness. Second, we adopt a reweighted difference of l(1) and l(2) norms as a nonconvex regularized term which enables one to reconstruct the sparse signal of interest from substantially fewer measurements. We propose a rule for setting the penalty level and show that the new model can provide a surprisingly good estimation error without any assumptions on the moments of the noise even for Cauchy noise. We present an efficient sequential linear programming algorithm for solving the new model and prove that the generated sequence converges to a stationary point satisfying the first-order optimality condition. Numerical results are also presented to indicate the efficiency of the proposed algorithm.