中文

Operations Research Transactions >

2025 , Vol. 29 >Issue 2: 158 - 174

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.02.012

Research Article

A variable metric extrapolation hard threshold algorithm for some linear inverse problem

Expand
  • School of Mathematics and Computer Science, Shanxi Normal University, Taiyuan 030031, Shanxi, China

Received date: 2022-04-27

  Online published: 2025-06-12

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.
Fold

Abstract

Sparsity regularization model is widely used in inverse problems such as signal and image processing. This paper mainly focuses on the linear least squares $\ell_0$ minimization problem coming from linear inverse problems. Extrapolation forward-backward splitting algorithm is one of the most popular solving methods. If the iteration number is sufficiently large, the non-zero index set of iteration point remains unchanged. Then extrapolation forward-backward splitting algorithm methods is equivalent to solving the problem $\min\limits_{x\in C} f(x)$ where $C$ is some linear subspace related to iteration points. On the other hand, variable metric type method can reach fast performance in practice. Encouraged by these, we employ the fast convergent quasi Newton method into the extrapolation step, and then propose a block variable metric extrapolation algorithm. Meanwhile, its convergence, linear convergence rate and superlinear convergence rate are studied. Finally, numerical experiments show the effectiveness and fast-speed of the proposed algorithm.

Key words： block; variable metric; extrapolation; linear convergence rate; super-linear convergence rate; ?0 regularization

Cite this article

Yuru ZHANG, Xue ZHANG, Ru LAN . A variable metric extrapolation hard threshold algorithm for some linear inverse problem[J]. Operations Research Transactions, 2025 , 29(2) : 158 -174 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.02.012

References

1 Zhang Y , Dong B , Lu Z S . $\ell_0$ minimization for wavelet frame based image restoration[J]. Mathematics of Computation, 2012, 82 (282): 995- 1015.
2 He L T , Wang Y L , Xiang Z Y . Wavelet frame-based image restoration using sparsity, nonlocal, and support prior of frame coefficients[J]. The Visual Computer, 2019, 35 (2): 151- 174.
3 柳宁, 赵焕明, 李德平, 等. 基于$\ell_0$稀疏先验的运动模糊标签图像盲复原[J]. 华南理工大学学报(自然科学版), 2021, 49 (3): 8- 16.
4 张晶, 乌彩英. 基于$\ell_1$-$\ell_0$模型的信号重构算法[J]. 内蒙古大学学报(自然科学版), 2020, 51 (6): 593- 599.
5 张秀再, 赵慧. 改进的自适应混合优化平滑$\ell_0$重构算法[J]. 海军工程大学学报, 2020, 32 (4): 6- 12.
6 刘光宇, 袁权, 张令威, 等. 基于卷积谱与$\ell_0$正则化的图像盲去模糊[J]. 计算机工程与设计, 2020, 41 (6): 1658- 1662.
7 李响, 蒋敏, 彭钰蘅, 等. 编码曝光图像的$\ell_0$正则化去模糊重建方法[J]. 数据采集与处理, 2020, 35 (1): 65- 78.
8 Gong M G , Liu J , Li H , et al. A multiobjective sparse feature learning model for deep neural networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2017, 26 (12): 3263- 3277.
9 Wang C X , Zeng L , Zhang L L , et al. An adaptive iteration reconstruction method for limited-angle CT image reconstruction[J]. Journal of Inverse and Ill-posed Problems, 2018, 26 (6): 771- 787.
10 Lu X Q , Wang Y L , Yuan Y . Sparse coding from a bayesian perspective[J]. IEEE Transactions on Neural Networks and Learning Systems, 2013, 24 (6): 929- 939.
11 Kiefer L , Storath M , Weinmann A . Iterative potts minimization for the recovery of signals with discontinuities from indirect measurements: The multivariate case[J]. Foundations of Computational Mathematics, 2021, 21 (3): 649- 694.
12 李庆龙, 曾雪迎. 一类信号恢复问题的投影迭代硬阈值算法[J]. 中国海洋大学学报(自然科学版), 2022, 52 (2): 129- 134.
13 Chen J X, Zhang M M, Li Y. A reconstruction algorithm for electrical capacitance tomography via total variation and $\ell_0$-norm regularizations using experimental data [EB/OL]. [2022-04-26]. arXiv: 1711.02544.
14 Lions P L , Mercier B . Splitting algorithms for the sum of two nonlinear operators[J]. SIAM Journal on Numerical Analysis, 1979, 16 (6): 964- 979.
15 Passty G . Ergodic convergence to a zero of the sum of monotone operators in Hilbert space[J]. Journal of Mathematical Analysis and Applications, 1979, 72 (2): 383- 390.
16 Attouch H , Bolte J , Svaiter B F . Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods[J]. Mathematical Programming, 2013, 137 (1-2): 91- 129.
17 Lu Z S . Iterative hard thresholding methods for $\ell_0$ regularized convex cone programming[J]. Mathematical Programming, 2013, 147 (1-2): 125- 154.
18 Bot R I , Csetnek E R , László S C . An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions[J]. EURO Journal on Computational Optimization, 2016, 4 (1): 3- 25.
19 Li H , Lin Z C . Accelerated proximal gradient methods for nonconvex programming[J]. In Advances in Neural Information Processing Systems (NIPS), 2015, 28
20 Yao Q M, Kwok J T, Gao F, et al. Efficient inexact proximal gradient algorithm for nonconvex problems [C]//Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligenc, 2017.
21 Bao C L , Dong B , Hou L K , et al. Image restoration by minimizing zero norm of wavelet frame coefficients[J]. Inverse Problems, 2016, 32 (11): 115004.
22 Zhang X , Zhang X Q . A new proximal iterative hard thresholding method with extrapolation for $\ell_0$ minimization[J]. Journal of Scientific Computing, 2019, 79 (2): 809- 826.
23 Attouch H , Peypouquet J . The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $o(k^{-2})$[J]. SIAM Journal on Optimization, 2016, 26 (3): 1824- 1834.
24 Frankel P , Garrigos G , Peypouquet J . Splitting methods with variable metric for Kurdyka-?ojasiewicz functions and general convergence rates[J]. Journal of Optimization Theory and Applications, 2015, 165 (3): 874- 900.
25 Chouzenoux E , Pesquet J C , Repetti A . A block coordinate variable metric forward-backward algorithm[J]. Journal of Global Optimization, 2016, 66 (3): 457- 485.
26 Ochs P . Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano[J]. SIAM Journal on Optimization, 2019, 29 (1): 541- 570.
27 Bonettini S , Zanella R , Zanni L . A scaled gradient projection method for constrained image deblurring[J]. Inverse Problems, 2009, 25
28 Bonettini S , Prato M . New convergence results for the scaled gradient projection method[J]. Inverse Problems, 2015, 31 (9): 095008.
29 Porta F , Prato M , Zanni L . A new steplength selection for scaled gradient methods with application to image deblurring[J]. Journal of Scientific Computing, 2015, 65 (3): 895- 919.
30 Zhang X, Zhang X Q. Variable metric extrapolation proximal iterative hard thresholding method for $\ell_0 $ minimization problem [EB/OL]. [2022-04-26]. arXiv: 2108.03365.
31 Beck A , Teboulle M . A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2 (1): 183- 202.
32 Nocedal J , Wright S J . Numerical Optimization[M]. New York: Springer, 1999.
33 Zhang X , Zhang X Q . A note on the complexity of proximal iterative hard thresholding algorithm[J]. Journal of the Operations Research Society of China, 2015, 3 (4): 459- 473.
34 王宜举, 修乃华. 非线性最优化理论与方法(第2版)[M]. 北京: 科学出版社, 2016.
Options
Outlines

/

〈 〉