一类线性反问题的变尺度外推硬阈值算法

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

Abstract

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, ?₀ regularization

CLC Number:

O221.2

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.

Figures/Tables 8

References 34

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. doi: 10.1090/S0025-5718-2012-02631-7
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. doi: 10.1007/s00371-017-1440-3
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.

$ K $	tol
$ K $	$ 1\times 10^{-4} $	$ 1\times 10^{-5} $	$ 1\times 10^{-6} $
1	4.043 0/6/0.020 6/1	5.363 0/8/0.020 6/1	6.043 0/9/0.020 6/1
2	4.700 0/7/0.020 6/1	5.361 0/8/0.020 6/1	6.046 0/9/0.020 6/1
3	3.931 0/6/0.020 6/1	5.349 0/8/0.020 6/1	6.041 0/9/0.020 6/1
4	4.637 0/7/0.020 6/1	5.374 0/8/0.020 6/1	6.777 0/10/0.020 6/1
5	4.657 0/7/0.020 6/1	5.362 0/8/0.020 6/1	6.769 0/10/0.020 6/1
10	4.667 0/7/0.020 6/1	6.088 0/8/0.020 6/1	6.791 0/10/0.020 6/1
15	4.650 0/7/0.020 6/1	6.109 0/8/0.020 6/1	6.782 0/10/0.020 6/1
20	4.634 0/7/0.020 6/1	6.052 0/8/0.020 6/1	6.842 0/10/0.020 6/1

$ K $	$ N $
$ K $	100	200	250	500
1	4.344 0/5/0.021 4/1	4.511 0/5/0.021 4/1	4.809 0/5/0.021 4/1	6.623 0/5/0.021 4/1
2	4.166 0/5/0.021 4/1	4.582 0/5/0.021 4/1	4.800 0/5/0.021 4/1	6.010 0/5/0.021 4/1
3	4.021 0/5/0.021 4/1	4.514 0/5/0.021 4/1	4.726 0/5/0.021 4/1	6.062 0/5/0.021 4/1
4	4.112 0/5/0.021 4/1	4.486 0/5/0.021 4/1	4.713 0/5/0.021 4/1	6.129 0/5/0.021 4/1
5	4.194 0/5/0.021 4/1	4.515 0/5/0.021 4/1	4.785 0/5/0.021 4/1	5.853 0/5/0.021 4/1
10	4.116 0/5/0.021 4/1	4.513 0/5/0.021 4/1	4.783 0/5/0.021 4/1	5.897 0/5/0.021 4/1
15	4.076 0/5/0.021 4/1	4.597 0/5/0.021 4/1	4.695 0/5/0.021 4/1	5.864 0/5/0.021 4/1
20	4.078 0/5/0.021 4/1	4.658 0/5/0.021 4/1	4.824 0/5/0.021 4/1	5.942 0/5/0.021 4/1

$ K $	$ N $
$ K $	100	200	250	500
1	5.029 0/6/0.020 6/1	5.391 0/6/0.020 6/1	5.425 0/6/0.020 6/1	6.988 0/6/0.020 6/1
2	5.001 0/6/0.020 6/1	5.394 0/6/0.020 6/1	5.501 0/6/0.020 6/1	7.027 0/6/0.020 6/1
3	4.853 0/6/0.020 6/1	5.464 0/6/0.020 6/1	5.594 0/6/0.020 6/1	6.994 0/6/0.020 6/1
4	4.877 0/6/0.020 6/1	5.559 0/6/0.020 6/1	5.517 0/6/0.020 6/1	7.012 0/6/0.020 6/1
5	4.983 0/6/0.020 6/1	5.576 0/6/0.020 6/1	5.558 0/6/0.020 6/1	7.072 0/6/0.020 6/1
10	4.938 0/6/0.020 6/1	5.496 0/6/0.020 6/1	5.658 0/6/0.020 6/1	7.070 0/6/0.020 6/1
15	4.962 0/6/0.020 6/1	5.414 0/6/0.020 6/1	5.757 0/6/0.020 6/1	7.001 0/6/0.020 6/1
20	4.978 0/6/0.020 6/1	5.424 0/6/0.020 6/1	5.719 0/6/0.020 6/1	6.982 0/6/0.020 6/1

$ K $	$ N $
$ K $	100	200	250	500
1	5.500 0/7/0.019 6/1	5.949 0/7/0.019 6/1	6.320 0/7/0.019 6/1	7.955 0/7/0.019 6/1
2	5.483 0/7/0.019 6/1	5.999 0/7/0.019 6/1	6.461 0/7/0.019 6/1	8.074 0/7/0.019 6/1
3	5.616 0/7/0.019 6/1	5.944 0/7/0.019 6/1	6.399 0/7/0.019 6/1	7.980 0/7/0.019 6/1
4	5.587 0/7/0.019 6/1	5.936 0/7/0.019 6/1	6.680 0/7/0.019 6/1	8.124 0/7/0.019 6/1
5	5.596 0/7/0.019 6/1	5.920 0/7/0.019 6/1	6.375 0/7/0.019 6/1	8.295 0/7/0.019 6/1
10	5.558 0/7/0.019 6/1	5.913 0/7/0.019 6/1	6.504 0/7/0.019 6/1	8.054 0/7/0.019 6/1
15	5.529 0/7/0.019 6/1	5.936 0/7/0.019 6/1	6.527 0/7/0.019 6/1	8.137 0/7/0.019 6/1
20	5.586 0/7/0.019 6/1	5.980 0/7/0.019 6/1	6.499 0/7/0.019 6/1	8.255 0/7/0.019 6/1

方法	tol
方法	$ 1\times 10^{-4} $	$ 1\times 10^{-5} $	$ 1\times 10^{-6} $
VMEPIHT	4.235 0/6/0.020 9/1	5.408 0/8/0.020 9/1	6.010 0/9/0.020 9/1
分块VMEPIHT	3.990 0/5/0.020 9/1	4.893 0/6/0.020 9/1	5.729 0/7/0.020 9/1

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 34

Related Articles 8

Recommended Articles

Metrics

Comments

[1]	Xianzhi YUAN. Consensus game and consensus equilibrium in blockchain ecology [J]. Operations Research Transactions, 2024, 28(3): 1-26.
[2]	Hongyin CHEN, Yukun CHENG, Xiaotie DENG, Zhanghao YAO. Auction in blockchain: Applications and challenges [J]. Operations Research Transactions, 2023, 27(1): 1-29.
[3]	Jiahao LYU, Honglin LUO, Zehua YANG, Jianwen PENG. A stochastic Bregman ADMM with its application in training sparse structure SVMs [J]. Operations Research Transactions, 2022, 26(2): 16-30.
[4]	Jia HU, Tiande GUO, Congying HAN. Mini-batch stochastic block coordinate descent algorithm [J]. Operations Research Transactions, 2022, 26(1): 1-22.
[5]	LIU Mingxi, GAN Guohua, CHENG Yukun, XIAO Lin, LIU Shuai, FANG Yong. Development and prospect of blockchain consensus mechanism [J]. Operations Research Transactions, 2020, 24(1): 23-39.
[6]	CHEN Caihua. Some notes on the divergence example for multi-block alternating direction method of multipliers [J]. Operations Research Transactions, 2019, 23(3): 135-140.
[7]	JIAN Jinbao, LAO Yixian, CHAO Miantao, MA Guodong. ADMM-SQP algorithm for two blocks linear constrained nonconvex optimization [J]. Operations Research Transactions, 2018, 22(2): 79-92.
[8]	CHEN Jian, SU Kaixiong, PENG Zheng, SU Lichao. Measurement method of block compressed sensing based on partial trigonometric function transform matrices [J]. Operations Research Transactions, 2015, 19(4): 59-71.