一种求解弹性l_2-l_q正则化问题的算法

doi:10.15960/j.cnki.issn.1007-6093.2016.04.002

Operations Research Transactions

Previous Articles Next Articles

An algorithm for elastic l_2-l_q regularization

ZHANG Yong¹ YE Wanzhou^1,*

1. Department of Mathematics, Shanghai University, Shanghai 200444, China

Received:2016-03-18 Online:2016-12-15 Published:2016-12-15

Abstract

Abstract:

In this paper, we present an iteratively re-weighted l_{1} minimization (IRL1) algorithm for solving elastic l_{2}-l_{q} regularization. We prove that any sequence generated by the IRL1 algorithm is bounded and asymptotically regular. We further prove that the sequence is convergent based on an algebraic method for any rational q \in (0,1) and the limit is a stationary point of the elastic l_{2}-l_{q}(0<q<1) minimization problem. Numerical experiments on sparse signal recovery are presented to demonstrate the effectiveness of the proposed algorithm.

Key words: l_{q} regularization, IRL1 algorithm, nonconvex optimization

ZHANG Yong, YE Wanzhou. An algorithm for elastic l_2-l_q regularization[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.04.002.

References

[1] Donoho D L. Compressed sensing [J]. IEEE Transactions on Information Theory, 2006, 52: 1289-1306.
[2] Cand\`{e}s E J, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information [J]. IEEE Transactions on Information Theory, 2006, 52: 489-509.
[3] Chartrand R. Exact reconstruction of sparse signals via nonconvex minimization [J]. IEEE Signal Processing Letter, 2007, 14: 707-710.
[4] Natraajan B K. Sparse approximation to linear systems [J]. SIAM Journal on Computing, 1995, 24: 227-237.
[5] Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit [J]. SIAM Journal on Scientific Computing, 1998, 20: 33-61.
[6] Daubechies I, Defries M, De Mol C. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint [J]. Communications on Pure and Applied Mathematics, 2004, 57: 1413-1457.
[7] Zou H. The adaptive lasso and its oracle properties [J]. Journal of the American Statistical Association, 2006, 101: 1418-1429.
[8] Xu Z B, Zhang H, Wang Y, et al. $L_{1/2}$ regularization [J]. Science China, 2010, 53: 1159-1169.
[9] Xu Z B, Chang X Y, Xu F M, et al. $L_{1/2}$ regularization: a thresholding representation theory and a fast solver [J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23: 1013-1027.
[10] Zou H, Hastie T. Regularization and variable selection via the elastic net [J]. Journal of the Royal Statistical Society: Series B, 2005, 67: 301-320.
[11] Cand\`{e}s E, Wakin M, Boyd S. Enhancing sparsity by reweighted $\ell_{1}$ minimization [J]. Journal of Fourier Analysis and Applications, 2008, 14: 877-905.
[12] Beck A, Teboulle M. A fast iterative shrinkage thresholding algorithm for linear inverse problems [J]. SIAM Journal in Imaging Sciences, 2009, 2: 183-202.
[13] Garcia C B, Li T Y. On the number of solutions to polynomial systems of equations [J]. SIAM Journal on Numerical Analysis, 1980, 17: 540-546.

An algorithm for elastic l_2-l_q regularization

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments