New regularization method and iteratively reweighted algorithm for sparse vector recovery

doi:10.1007/s10483-020-2561-6

Applied Mathematics and Mechanics (English Edition) ›› 2020, Vol. 41 ›› Issue (1): 157-172.doi: https://doi.org/10.1007/s10483-020-2561-6

New regularization method and iteratively reweighted algorithm for sparse vector recovery

Wei ZHU¹, Hui ZHANG², Lizhi CHENG²

1. Post-doctoral Research Station of Statistics, School of Mathematics and Computational Science, Xiangtan University, Xiangtan 411105, Hunan Province, China;
2. Department of Mathematics, National University of Defense Technology, Changsha 410073, China

收稿日期:2019-06-17 修回日期:2019-07-21 发布日期:2019-12-14
通讯作者: Wei ZHU E-mail:zhuwei@xtu.edu.cn
基金资助:
Project supported by the National Natural Science Foundation of China (No. 61603322) and the Research Foundation of Education Bureau of Hunan Province of China (No. 16C1542)

New regularization method and iteratively reweighted algorithm for sparse vector recovery

Wei ZHU¹, Hui ZHANG², Lizhi CHENG²

1. Post-doctoral Research Station of Statistics, School of Mathematics and Computational Science, Xiangtan University, Xiangtan 411105, Hunan Province, China;
2. Department of Mathematics, National University of Defense Technology, Changsha 410073, China

Received:2019-06-17 Revised:2019-07-21 Published:2019-12-14
Contact: Wei ZHU E-mail:zhuwei@xtu.edu.cn
Supported by:
Project supported by the National Natural Science Foundation of China (No. 61603322) and the Research Foundation of Education Bureau of Hunan Province of China (No. 16C1542)

摘要/Abstract

摘要： Motivated by the study of regularization for sparse problems, we propose a new regularization method for sparse vector recovery. We derive sufficient conditions on the well-posedness of the new regularization, and design an iterative algorithm, namely the iteratively reweighted algorithm (IR-algorithm), for efficiently computing the sparse solutions to the proposed regularization model. The convergence of the IR-algorithm and the setting of the regularization parameters are analyzed at length. Finally, we present numerical examples to illustrate the features of the new regularization and algorithm.

关键词: regularization method, iteratively reweighted algorithm (IR-algorithm), sparse vector recovery

Abstract: Motivated by the study of regularization for sparse problems, we propose a new regularization method for sparse vector recovery. We derive sufficient conditions on the well-posedness of the new regularization, and design an iterative algorithm, namely the iteratively reweighted algorithm (IR-algorithm), for efficiently computing the sparse solutions to the proposed regularization model. The convergence of the IR-algorithm and the setting of the regularization parameters are analyzed at length. Finally, we present numerical examples to illustrate the features of the new regularization and algorithm.

Key words: regularization method, iteratively reweighted algorithm (IR-algorithm), sparse vector recovery

中图分类号:

49K35
90C06

Wei ZHU, Hui ZHANG, Lizhi CHENG. New regularization method and iteratively reweighted algorithm for sparse vector recovery[J]. Applied Mathematics and Mechanics (English Edition), 2020, 41(1): 157-172.

参考文献

[1] TIKHONOV, A. N. On the solution of ill-posed problems and the method of regularization. Doklady Akademii Nauk SSSR, 151, 501-504(1963)
[2] BENJAMIN, S. and THORSTEN, H. Higher order convergence rates for Bregman iterated variational regularization of inverse problems. Numerische Mathematik, 141, 215-252(2018)
[3] ZHU, W., SHU, S., and CHENG, L. Z. An efficient proximity point algorithm for total-variationbased image restoration. Advances in Applied Mathematics and Mechanics, 6, 145-164(2014)
[4] CLASON, C., KRUSE, F., and KUNISH, K. Total variation regularization of multi-material topology optimization. ESAIM:Mathematical Modelling and Numerical Analysis, 52, 275-303(2018)
[5] ZHANG, H., CHENG, L. Z., and ZHU, W. Nuclear norm regularization with a low-rank constraint for matrix completion. Inverse Problems, 26, 115009(2010)
[6] DONG, J., XUE, Z. C., GUAN, J., HAN, Z. F., and WANG, W. W. Low rank matrix completion using truncated nuclear norm and sparse regularizer. Signal Processing:Image Communication, 68, 76-87(2018)
[7] USEVICH, K. and COMON, P. Hankel low-rank matrix completion:performance of the nuclear norm relaxation. IEEE Journal of Selected Topics in Signal Processing, 10, 637-646(2017)
[8] ZHU, W., SHU, S., and CHENG, L. Z. First-order optimality condition of basis pursuit denoise problem. Applied Mathematics and Mechanics (English Edition), 35(10), 1345-1352(2014) https://doi.org/10.1007/s10483-014-1860-9
[9] ZHU, W., SHU, S., and CHENG, L. Z. Proximity point algorithm for low-rank matrix recovery from sparse noise corrupted data. Applied Mathematics and Mechanics (English Edition), 35(2), 259-268(2014) https://doi.org/10.1007/s10483-014-1788-6
[10] BREDIES, K. and LORENZ, D. A. Regularization with non-convex separable constraints. Inverse Problem, 25, 085011(2009)
[11] GRASMAIR, M., HALTMEIER, M., and SCHERZER, O. Sparse regularization with lq penalty term. Inverse Problems, 24, 055020(2008)
[12] ENGL, H. W. and RAMLAU, R. Regularization of inverse problems. Encyclopedia of Applied and Computational Mathematics, Springer, Heidelberg (2015)
[13] ARJOUNE, Y., KAABOUCH, N., GHAZI, H. E., and TAMTAOUI, A. Compressive sensing:performance comparison of sparse recovery algorithms. 2017 IEEE 7th Annual Computing and Communication Workshop and Conference (CCWC), IEEE, Las Vegas (2017)
[14] DAN, W. and ZHANG, Z. Generalized sparse recovery model and its neural dynamical optimization method for compressed sensing. Circuits Systems and Signal Processing, 36, 4326-4353(2017)
[15] CHARTRAND, R. and STANEVA, V. Restricted isometry properties and nonconvex compressive sensing. Inverse Problems, 24, 657-682(2008)
[16] CHARTRAND, R. and YIN, W. T. Iteratively reweighted algorithms for compressive sensing. International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2008), 3869-3872(2008)
[17] CHARTRAND, R. Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Processing Letters, 14, 707-710(2007)
[18] GE, D., JIANG, X., and YE, Y. A note on complexity of Lp minimization. Mathematics Programming, 129, 285-299(2011)
[19] FOUCART, S. and LAI, M. J. Sparsest solutions of underdetermined linear systems via lqminimization for 0< q ≤ 1. Applied and Computational Harmonic Analysis, 26, 395-407(2009)
[20] FOUCART, S. A note on guaranteed sparse recovery via l₁-minimization. Applied and Computational Harmonic Analysis, 29, 97-103(2010)
[21] CANDÈS, E. J. and PLAN, Y. A probabilistic and RIPless theory of compressed sensing. IEEE Transactions on Information Theory, 57, 7235-7254(2010)
[22] SUN, Q. Y. Sparse approximation property and stable recovery of sparse signals from noisy measurements. IEEE Transactions on Signal Processing, 59, 5086-5090(2011)
[23] FAZEL, M. Matrix Rank Minimization with Applications, Ph. D. dissertation, Stanford University, California (2002)
[24] CANDÈS, E. J., WAKIN, M. B., and BOYD, S. P. Enhancing sparsity by reweighted l₁ minimization. Journal of Fourier Analysis and Applications, 14, 877-905(2008)
[25] DAUCHEBIES, I., DEVORE, R., FORNASIER, M., and GUNTURK, C. S. Iteratively reweighted least squares minimization for sparse recovery. Communications on Pure and Applied Mathematics, 63, 1-38(2010)
[26] MOURAD, N. and REILLY, J. F. Minimizaing nonconvex functions for sparse vector reconstruction. IEEE Transactions on Signal Processing, 58, 3485-3496(2010)
[27] NEEDELL, D. Noisy signal recovery via iterative reweighted L₁-minimization. 2009 Conference Record of the Forty-Third Asilomar Conference on Signals, Systems and Computers, IEEE, Pacific Grove (2009)
[28] XU, W. Y., KHAJEHNEJAD, M. A., AVESTIMEHR, S., and HASSIBI, B. Breaking through the thresholds:an analysis for iterative reweighted l₁ minimization via the Grassmann angle framework. ICASSP 2010:IEEE International Conference on Acoustics, Speech and Signal, IEEE, Texas (2009)
[29] CHEN, X. J., XU, F., and YE, Y. Lower bound theory of nonzero entries in solutions of l₂-l_p minimization. SIAM Journal on Scientific Computing, 32, 2832-2852(2010)
[30] LAI, M. J. and WANG, J. An unconstrained lq minimization with 0 < q ≤ 1 for sparse solution of underdetermined linear systems. SIAM Journal on Optimization, 21, 82-101(2011)
[31] MOL, C. D., VITO, E. D., and ROSASCO, L. Elastic-net regularization in learning theory. Journal of Complexity, 25, 201-230(2009)
[32] JIN, B. T., LORENZ, D. A., and SCHIFFLER, S. Elastic-net regularization:error estimates and active set methods. Inverse Problems, 25, 115022(2009)
[33] ZOU, H. and HASTIE, T. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society:Series B, 67, 301-320(2005)
[34] CAI, J. F., OSHER, S., and SHEN, Z. W. Linearized Bregman iterations for compressed sensing. Mathematics of Computation, 78, 1515-1536(2009)
[35] YIN, W. Analysis and generalizations of the linearized Bregman method. SIAM Journal on Imaging Sciences, 3, 856-877(2010)
[36] ZHANG, H., CHENG, L. Z., and ZHU, W. A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm. Applied and Computational Harmonic Analysis, 31, 454-459(2011)
[37] BERTSEKAS, D. P., NEDIĆ, A., and OZDAGLAR, A. E. Convex Analysis and Optimization, Athena Scietific and Tsinghua University Press, Beijing (2006)
[38] YUAN, Z. Y. and WANG, H. X. Phase retrieval via reweighted wirtinger flow method. Applied Optics, 56, 2418-2427(2017)
[39] HARDY, G. H., LITTLEWOOD, J. E., and PÓLYA, G. Inequalities, Posts and Telecom Press, Beijing (2010)
[40] FORNASIER, M. Theoretical Foundations and Numerical Methods for Sparse Recovery, De Gruyter, Berlin (2010)

New regularization method and iteratively reweighted algorithm for sparse vector recovery

New regularization method and iteratively reweighted algorithm for sparse vector recovery

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	顾智杰;谭永基. Fundamental solution method for inverse source problem of plate equation[J]. Applied Mathematics and Mechanics (English Edition), 2012, 33(12): 1513-1532.
[2]	王登刚;刘迎曦;李守巨. CHAOS-REGULARIZATION HYBRID ALGORITHM FOR NONLINEAR TWO-DIMENSIONAL INVERSE HEAT CONDUCTION PROBLEM[J]. Applied Mathematics and Mechanics (English Edition), 2002, 23(8): 973-980.
[3]	尤云祥;缪国平. ON THE REGULARIZATION METHOD OF THE FIRST KIND OF FREDHOLM INTEGRAL EQUATION WITH A COMPLEX KERNEL AND ITS APPLICATION[J]. Applied Mathematics and Mechanics (English Edition), 1998, 19(1): 75-83.