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

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

运筹学学报

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

张勇¹ 叶万洲^1,*

1. 上海大学数学系, 上海 200444

收稿日期:2016-03-18 出版日期:2016-12-15 发布日期:2016-12-15
通讯作者: 叶万洲 wzhy@shu.edu.cn
基金资助:
国家自然科学基金(No. 61071186)

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

摘要：

给出了一种求解弹性l_{2}-l_{q}正则化问题的迭代重新加权l_{1}极小化算法, 并证明了由该算法产生的迭代序列是有界且渐进正则的. 对于任何有理数q\in(0,1), 基于一个代数的方法, 进一步证明了迭代重新加权l_{1}极小化算法收敛到弹性l_{2}-l_{q}(0<q<1)正则化问题的稳定点. 最后, 通过稀疏信号恢复的数值实例验证了算法的有效性.

关键词: l_{q}正则化, 迭代重新加权l_{1}极小化算法, 非凸优化

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

张勇, 叶万洲. 一种求解弹性l_2-l_q正则化问题的算法[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2016.04.002.

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.

参考文献

[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.

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

An algorithm for elastic l_2-l_q regularization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价