Sparse Recovery via Partial Regularization: Models, Theory and
  Algorithms
  In the context of sparse recovery, it is known that most of existing
regularizers such as $\ell_1$ suffer from some bias incurred by some leading
entries (in magnitude) of the associated vector. To neutralize this bias, we
propose a class of models with partial regularizers for recovering a sparse
solution of a linear system. We show that every local minimizer of these models
is sufficiently sparse or the magnitude of all its nonzero entries is above a
uniform constant depending only on the data of the linear system. Moreover, for
a class of partial regularizers, any global minimizer of these models is a
sparsest solution to the linear system. We also establish some sufficient
conditions for local or global recovery of the sparsest solution to the linear
system, among which one of the conditions is weaker than the best known
restricted isometry property (RIP) condition for sparse recovery by $\ell_1$.
In addition, a first-order feasible augmented Lagrangian (FAL) method is
proposed for solving these models, in which each subproblem is solved by a
nonmonotone proximal gradient (NPG) method. Despite the complication of the
partial regularizers, we show that each proximal subproblem in NPG can be
solved as a certain number of one-dimensional optimization problems, which
usually have a closed-form solution. We also show that any accumulation point
of the sequence generated by FAL is a first-order stationary point of the
models. Numerical results on compressed sensing and sparse logistic regression
demonstrate that the proposed models substantially outperform the widely used
ones in the literature in terms of solution quality.
