|
|
|
|
Efficient Sparse Recovery via Adaptive Non-Convex Regularizers with Oracle Property
Ming Lin, Rong Jin, Changshui Zhang
Abstract:
The main shortcoming of sparse recovery with
a convex regularizer is that it is a biased esti-
mator and therefore will result in a suboptimal
performance in many cases. Recent studies have
shown, both theoretically and empirically, that
non-convex regularizer is able to overcome the
biased estimation problem. Although multiple
algorithms have been developed for sparse recov-
ery with non-convex regularization, they are ei-
ther computationally demanding or not equipped
with the desired properties (i.e. optimal recovery
error, selection consistency and oracle property).
In this work, we develop an algorithm for effi-
cient sparse recovery based on proximal gradient
descent. The key feature of the proposed algo-
rithm is introducing adaptive non-convex regu-
larizers whose shrinking threshold vary over it-
erations. The algorithm is compatible with most
popular non-convex regularizers, achieves a ge-
ometric convergence rate for the recovery er-
ror, is selection consistent, and most importantly
has the oracle property. Based on the proposed
framework, we suggest to use a soâ??called ACCQ
regularizer, which is equivalent to zero proximal
projection gap adaptive hard-thresholding. Ex-
periments with both synthetic data sets and real
images verify both the efficiency and effective-
ness of the proposed method compared to the
state-of-the-art methods for sparse recovery.
Keywords:
Pages: 505-514
PS Link:
PDF Link: /papers/14/p505-lin.pdf
BibTex:
@INPROCEEDINGS{Lin14,
AUTHOR = "Ming Lin
and Rong Jin and Changshui Zhang",
TITLE = "Efficient Sparse Recovery via Adaptive Non-Convex Regularizers with Oracle Property",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "505--514"
}
|
|
