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

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

摘要/Abstract

摘要：

稀疏正则化模型在信号和图像处理等反问题中有很广泛的应用。本文主要研究线性最小二乘$\ell_0$极小化问题的快速求解方法。外推向前向后分裂算法是最流行的求解方法之一。根据$\ell_0$正则化问题和该算法的特点, 我们将快速收敛的拟牛顿方法合理地应用于外推步中, 进而提出了一种分块变尺度外推算法, 并证明了其收敛性行为。我们在理论上证明了其快速性: 该方法具有线性收敛率, 甚至超线性收敛率。最后, 我们也通过数值实验展示了本文算法的有效性和快速性。

关键词: 分块, 变尺度, 外推, 线性收敛率, 超线性收敛率, ?₀正则化

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

中图分类号:

O221.2

张玉茹, 张雪, 兰茹. 一类线性反问题的变尺度外推硬阈值算法[J]. 运筹学学报（中英文）, 2025, 29(2): 158-174.

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.

图/表 8

表1

表2

表3

表4

表5

图1

图2

图3

参考文献 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