Sparse Recovery via Partial Regularization: Models, Theory, and Algorithms

Zhaosong Lu () and Xiaorui Li ()
Additional contact information
Zhaosong Lu: Department of Mathematics, Simon Fraser University, British Columbia, Canada
Xiaorui Li: Department of Mathematics, Simon Fraser University, British Columbia, Canada

Mathematics of Operations Research, 2018, vol. 43, issue 4, 1290-1316

Abstract: In the context of sparse recovery, it is known that most of the existing regularizers such as ℓ 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 substantially sparse or the magnitude of all of 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 condition for sparse recovery by ℓ 1 . In addition, a first-order 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.

Keywords: sparse recovery; partial regularization; null space property; restricted isometry property; proximal gradient method; augmented Lagrangian method; compressed sensing; sparse logistic regression (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0905 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:43:y:2018:i:4:p:1290-1316

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().