Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
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"
}


hosted by DSL   •   site info   •   help