运筹学学报 >
2016 , Vol. 20 >Issue 4: 11 - 20
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.04.002
一种求解弹性l_2-l_q正则化问题的算法
An algorithm for elastic l_2-l_q regularization
Received date: 2016-03-18
Online published: 2016-12-15
给出了一种求解弹性l_{2}-l_{q}正则化问题的迭代重新加权l_{1}极小化算法, 并证明了由该算法产生的迭代序列是有界且渐进正则的. 对于任何有理数q\in(0,1), 基于一个代数的方法, 进一步证明了迭代重新加权l_{1}极小化算法收敛到弹性l_{2}-l_{q}(0<q<1)正则化问题的稳定点. 最后, 通过稀疏信号恢复的数值实例验证了算法的有效性.
关键词： l_{q}正则化; 迭代重新加权l_{1}极小化算法; 非凸优化
张勇, 叶万洲 . 一种求解弹性l_2-l_q正则化问题的算法[J]. 运筹学学报, 2016 , 20(4) : 11 -20 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.04.002
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
[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.
/
| 〈 |
|
〉 |
