一类稀疏优化问题的迭代阈值算法及收敛性研究
Research on Iterative Thresholding Algorithms and Convergence for a Class of Sparse Optimization Problems
摘要: Nesterov加速策略以其显著的收敛加速效果，被广泛应用于各类梯度优化算法的设计中。本文将Nesterov加速技术与迭代有限收缩阈值算法相结合，针对非凸稀疏优化问题提出了基于延拓技术的加速迭代有限收缩阈值算法(A-ILSTAC)和基于截断技术的加速迭代有限收缩阈值算法(A-ILSTAT)。在限制等距性质(RIP)条件下，本文证明了所提算法能够收敛到近似真实稀疏解，其误差由噪声水平和有限收缩幅度决定。初步数值实验表明，本文算法能够找到近似真实稀疏解，且效果显著优于原始迭代有限收缩阈值算法。
Abstract: Nesterov’s acceleration strategy is renowned in speeding up the convergence of gradient-based optimization algorithms. By merging this strategy and the iterative limited shrinkage thresholding algorithms, we propose an accelerated iterative limited shrinkage thresholding algorithm with continuation (A-ILSTAC) and the one with truncation (A-ILSTAT) for nonconvex sparse optimization problems, respectively. Under the restricted isometry property (RIP) condition, we prove that the proposed algorithms converge to an approximate true sparse solution within a tolerance relevant to the noise level and the limited shrinkage magnitude. Preliminary numerical results show that our proposed algorithms can find approximate true sparse solutions that are much better than sparse solutions that are found by using original iterative limited shrinkage thresholding algorithms.
文章引用：赵心雨. 一类稀疏优化问题的迭代阈值算法及收敛性研究[J]. 应用数学进展, 2026, 15(4): 735-747. https://doi.org/10.12677/aam.2026.154197

参考文献

[1] Chen, S.S., Donoho, D.L. and Saunders, M.A. (1998) Atomic Decomposition by Basis Pursuit. SIAM Journal on Scientific Computing, 20, 33-61. [Google Scholar] [CrossRef] 
[2] Donoho, D.L. (2006) Compressed Sensing. IEEE Transactions on Information Theory, 52, 1289-1306. [Google Scholar] [CrossRef] 
[3] Beck, A. and Teboulle, M. (2009) A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. SIAM Journal on Imaging Sciences, 2, 183-202. [Google Scholar] [CrossRef] 
[4] Elad, M. (2010) Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer Science & Business Media.
[5] Qin, J., Hu, Y., Xu, F., Yalamanchili, H.K. and Wang, J. (2014) Inferring Gene Regulatory Networks by Integrating ChIP-seq/chip and Transcriptome Data via LASSO-Type Regularization Methods. Methods, 67, 294-303. [Google Scholar] [CrossRef] [PubMed]
[6] Wang, J., Hu, Y., Li, C. and Yao, J. (2017) Linear Convergence of CQ Algorithms and Applications in Gene Regulatory Network Inference. Inverse Problems, 33, Article ID: 055017. [Google Scholar] [CrossRef] 
[7] Bach, F., Jenatton, R., Mairal, J. and Obozinski, G. (2012) Structured Sparsity through Convex Optimization. Statistical Science, 27, 450-468. [Google Scholar] [CrossRef] 
[8] Hu, Y., Li, C., Meng, K., Qin, J. and Yang, X. (2017) Group Sparse Optimization via Regularization. Journal of Machine Learning Research, 18, 1-52.
[9] Bickel, P.J., Ritov, Y. and Tsybakov, A.B. (2009) Simultaneous Analysis of Lasso and Dantzig Selector. The Annals of Statistics, 37, 1705-1732. [Google Scholar] [CrossRef] 
[10] Cai, T.T., Xu, G. and Zhang, J. (2009) On Recovery of Sparse Signals via Minimization. IEEE Transactions on Information Theory, 55, 3388-3397. [Google Scholar] [CrossRef] 
[11] Candes, E.J. and Tao, T. (2005) Decoding by Linear Programming. IEEE Transactions on Information Theory, 51, 4203-4215. [Google Scholar] [CrossRef] 
[12] Daubechies, I., Defrise, M. and De Mol, C. (2004) An Iterative Thresholding Algorithm for Linear Inverse Problems with a Sparsity Constraint. Communications on Pure and Applied Mathematics, 57, 1413-1457. [Google Scholar] [CrossRef] 
[13] Hale, E.T., Yin, W. and Zhang, Y. (2008) Fixed-Point Continuation for-Minimization: Methodology and Convergence. SIAM Journal on Optimization, 19, 1107-1130. [Google Scholar] [CrossRef] 
[14] Xiao, L. and Zhang, T. (2013) A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem. SIAM Journal on Optimization, 23, 1062-1091. [Google Scholar] [CrossRef] 
[15] Chartrand, R. and Staneva, V. (2008) Restricted Isometry Properties and Nonconvex Compressive Sensing. Inverse Problems, 24, Article ID: 035020. [Google Scholar] [CrossRef] 
[16] Fan, J. and Li, R. (2001) Variable Selection via Nonconcave Penalized Likelihood and Its Oracle Properties. Journal of the American Statistical Association, 96, 1348-1360. [Google Scholar] [CrossRef] 
[17] Xu, Z., Chang, X., Xu, F. and Zhang, H. (2012) Regularization: A Thresholding Representation Theory and a Fast Solver. IEEE Transactions on Neural Networks and Learning Systems, 23, 1013-1027. [Google Scholar] [CrossRef] [PubMed]
[18] Zhang, C. (2010) Nearly Unbiased Variable Selection under Minimax Concave Penalty. The Annals of Statistics, 38, 894-942. [Google Scholar] [CrossRef] 
[19] Chen, X., Xu, F. and Ye, Y. (2010) Lower Bound Theory of Nonzero Entries in Solutions of-Minimization. SIAM Journal on Scientific Computing, 32, 2832-2852. [Google Scholar] [CrossRef] 
[20] Locatelli, M. and Schoen, F. (2013) Global Optimization: Theory, Algorithms, and Applications. Society for Industrial and Applied Mathematics. [Google Scholar] [CrossRef] 
[21] Blumensath, T. and Davies, M.E. (2009) Iterative Hard Thresholding for Compressed Sensing. Applied and Computational Harmonic Analysis, 27, 265-274. [Google Scholar] [CrossRef] 
[22] Foucart, S. and Rauhut, H. (2013) A Mathematical Introduction to Compressive Sensing. Springer.
[23] Lu, Z. (2014) Iterative Reweighted Minimization Methods for Regularized Unconstrained Nonlinear Programming. Mathematical Programming, 147, 277-307. [Google Scholar] [CrossRef] 
[24] Attouch, H., Bolte, J. and Svaiter, B.F. (2013) Convergence of Descent Methods for Semi-Algebraic and Tame Problems: Proximal Algorithms, Forward-Backward Splitting, and Regularized Gauss-Seidel Methods. Mathematical Programming, 137, 91-129. [Google Scholar] [CrossRef] 
[25] Boţ, R.I., Csetnek, E.R. and Nguyen, D. (2019) A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems. SIAM Journal on Optimization, 29, 1300-1328. [Google Scholar] [CrossRef] 
[26] Wen, Z., Yin, W., Goldfarb, D. and Zhang, Y. (2010) A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation. SIAM Journal on Scientific Computing, 32, 1832-1857. [Google Scholar] [CrossRef] 
[27] Jiao, Y., Jin, B. and Lu, X. (2017) Iterative Soft/Hard Thresholding with Homotopy Continuation for Sparse Recovery. IEEE Signal Processing Letters, 24, 784-788. [Google Scholar] [CrossRef] 
[28] Blumensath, T. and Davies, M.E. (2010) Normalized Iterative Hard Thresholding: Guaranteed Stability and Performance. IEEE Journal of Selected Topics in Signal Processing, 4, 298-309. [Google Scholar] [CrossRef] 
[29] Zhao, Y. (2020) Optimal k-Thresholding Algorithms for Sparse Optimization Problems. SIAM Journal on Optimization, 30, 31-55. [Google Scholar] [CrossRef] 
[30] Hu, Y., Hu, X. and Yang, X. (2025) On Convergence of Iterative Thresholding Algorithms to Approximate Sparse Solution for Composite Nonconvex Optimization. Mathematical Programming, 211, 181-206. [Google Scholar] [CrossRef] 
[31] Nesterov, Y. (1983) A Method of Solving a Convex Programming Problem with Convergence Rate . Proceedings of the USSR Academy of Sciences, 269, 543-547.

为你推荐