一种求解低秩矩阵补全的惯性加速交替方向法

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

摘要/Abstract

摘要：

交替方向法作为求解矩阵补全问题的经典方法之一, 具有能够将一个极小化问题分解成多个规模更小、更容易求解的子问题的优势, 近年来在图像处理和数据分析等领域备受青睐。本文采用交替方向法的框架, 结合惯性策略, 提出了一种求解矩阵补全问题的惯性加速交替方向法。新算法在每步迭代中, 对于其中一部分变量利用交替方向法的前两次迭代点外推得到新一步的迭代点, 从而提高计算效率。本文在合理的假设条件下, 证明了新算法的收敛性。最后, 通过随机矩阵补全的数值实验及图像修复的实例验证了新算法的有效性和可行性。

关键词: 矩阵补全问题, 交替方向法, 惯性加速

Abstract:

The alternating direction method of multiplier is attractive for solving matrix completion problems, which has the advantage of being able to decompose a minimization problem into many smaller and easier subproblems. Therefore, it is popular in the field of image processing and data analysis in recent years. Based on the framework of the alternating direction method of multiplier, we combine the inertial strategy and propose an inertial accelerated alternating direction method of multiplier to solve the matrix completion problems in this paper. In each iteration of the new method, for some of variables, the iterative points of the previous two iterations of the alternating direction method of multiplier are extrapolated to obtain the new iteration points, which improve the computational efficiency of the new method. Under the reasonable assumptions, we prove convergence of the new method. Finally, we also verify the effectiveness and feasibility of the new method by numerical experiments of random matrix completion and an example of image restoration.

Key words: matrix completion problem, alternating direction method of multiplier, inertial acceleration

中图分类号:

O221.2

闫喜红, 唐晓妮. 一种求解低秩矩阵补全的惯性加速交替方向法[J]. 运筹学学报（中英文）, 2025, 29(1): 172-184.

Xihong YAN, Xiaoni TANG. An inertial alternating direction method of multiplier for low rank matrix completion[J]. Operations Research Transactions, 2025, 29(1): 172-184.

图/表 5

表1

IADM算法与ADMM算法、SVT算法的比较(当$ p=0.3 $时)"

$ n $	$ r $	算法	iter	$ t $/s	error1	error2
2 000	10	ADMM	44	6.438 4	$ 1.802\, 7\times10^{-4} $	$ 1.715\, 2\times10^{-4} $
		IADM	38	5.114 7	$ 1.674\, 0\times10^{-4} $	$ 2.378\, 6\times10^{-4} $
		SVT	125	46.202	$ 1.991\, 5\times10^{-4} $	$ 2.272\, 8\times10^{-4} $
2 000	20	ADMM	42	7.416 2	$ 1.535\, 0\times10^{-4} $	$ 2.962\, 5\times10^{-4} $
		IADM	37	6.852 1	$ 1.524\, 9\times10^{-4} $	$ 2.276\, 1\times10^{-4} $
		SVT	148	72.547	$ 1.988\, 7\times10^{-4} $	$ 2.427\, 7\times10^{-4} $
4 000	10	ADMM	45	23.203	$ 1.802\, 4\times10^{-4} $	$ 2.298\, 1\times10^{-4} $
		IADM	40	21.664	$ 1.348\, 5\times10^{-4} $	$ 1.713\, 1\times10^{-4} $
		SVT	107	122.32	$ 1.991\, 9\times10^{-4} $	$ 2.149\, 6\times10^{-4} $
4 000	20	ADMM	44	31.829	$ 1.993\, 5\times10^{-4} $	$ 1.992\, 8\times10^{-4} $
		IADM	38	28.120	$ 1.881\, 2\times10^{-4} $	$ 2.606\, 7\times10^{-4} $
		SVT	122	233.68	$ 1.938\, 5\times10^{-4} $	$ 2.184\, 9\times10^{-4} $
6 000	10	ADMM	45	55.862	$ 1.595\, 9\times10^{-4} $	$ 2.495\, 7\times10^{-4} $
		IADM	40	51.549	$ 1.944\, 1\times10^{-4} $	$ 1.907\, 3\times10^{-4} $
		SVT	102	270.53	$ 1.892\, 6\times10^{-4} $	$ 2.000\, 3\times10^{-4} $
6 000	20	ADMM	33	57.254	$ 1.794\, 5\times10^{-4} $	$ 2.385\, 8\times10^{-4} $
		IADM	28	50.656	$ 1.633\, 3\times10^{-4} $	$ 2.033\, 9\times10^{-4} $
		SVT	112	471.71	$ 1.928\, 0\times10^{-4} $	$ 2.102\, 6\times10^{-4} $
8 000	10	ADMM	45	94.967	$ 1.664\, 0\times10^{-4} $	$ 2.629\, 3\times10^{-4} $
		IADM	40	89.766	$ 1.977\, 4\times10^{-4} $	$ 2.005\, 2\times10^{-4} $
		SVT	96	461.39	$ 1.983\, 4\times10^{-4} $	$ 2.068\, 6\times10^{-4} $
8 000	20	ADMM	33	99.171	$ 1.888\, 3\times10^{-4} $	$ 2.555\, 2\times10^{-4} $
		IADM	28	87.192	$ 1.721\, 4\times10^{-4} $	$ 2.121\, 2\times10^{-4} $
		SVT	107	761.11	$ 1.932\, 3\times10^{-4} $	$ 2.069\, 7\times10^{-4} $
10 000	10	ADMM	45	194.87	$ 1.690\, 0\times10^{-4} $	$ 2.697\, 2\times10^{-4} $
		IADM	41	183.78	$ 1.161\, 0\times10^{-4} $	$ 1.992\, 8\times10^{-4} $
		SVT	94	740.69	$ 1.944\, 0\times10^{-4} $	$ 2.012\, 2\times10^{-4} $
10 000	20	ADMM	45	189.72	$ 1.515\, 3\times10^{-4} $	$ 2.696\, 3\times10^{-4} $
		IADM	40	174.70	$ 1.933\, 1\times10^{-4} $	$ 2.057\, 6\times10^{-4} $
		SVT	103	1 168.2	$ 1.966\, 6\times10^{-4} $	$ 2.081\, 9\times10^{-4} $

表1

表2

IADM算法与ADMM算法、SVT算法的比较(当$ p=0.4 $时)"

$ n $	$ r $	算法	iter	$ t $/s	error1	error2
2 000	10	ADMM	31	4.098 3	$ 1.809\, 4\times10^{-4} $	$ 1.715\, 2\times10^{-4} $
		IADM	28	4.069 7	$ 1.368\, 8\times10^{-4} $	$ 1.708\, 1\times10^{-4} $
		SVT	115	30.287	$ 1.913\, 8\times10^{-4} $	$ 2.110\, 6\times10^{-4} $
2 000	20	ADMM	31	5.875 4	$ 1.526\, 3\times10^{-4} $	$ 1.991\, 7\times10^{-4} $
		IADM	28	6.050 2	$ 1.157\, 1\times10^{-4} $	$ 1.402\, 5\times10^{-4} $
		SVT	131	61.228	$ 1.993\, 9\times10^{-4} $	$ 2.304\, 1\times10^{-4} $
4 000	10	ADMM	33	16.898	$ 1.780\, 0\times10^{-4} $	$ 1.244\, 0\times10^{-4} $
		IADM	28	14.897	$ 1.628\, 8\times10^{-4} $	$ 2.008\, 0\times10^{-4} $
		SVT	101	118.28	$ 1.909\, 0\times10^{-4} $	$ 2.014\, 6\times10^{-4} $
4 000	20	ADMM	31	24.831	$ 1.874\, 1\times10^{-4} $	$ 2.724\, 4\times10^{-4} $
		IADM	28	23.602	$ 1.447\, 9\times10^{-4} $	$ 1.869\, 5\times10^{-4} $
		SVT	112	205.16	$ 1.941\, 9\times10^{-4} $	$ 2.114\, 0\times10^{-4} $
6 000	10	ADMM	33	39.655	$ 1.880\, 5\times10^{-4} $	$ 1.353\, 4\times10^{-4} $
		IADM	28	35.408	$ 1.728\, 5\times10^{-4} $	$ 2.101\, 6\times10^{-4} $
		SVT	94	221.87	$ 1.971\, 9\times10^{-4} $	$ 2.045\, 0\times10^{-4} $
6 000	20	ADMM	33	57.254	$ 1.794\, 5\times10^{-4} $	$ 1.327\, 8\times10^{-4} $
		IADM	28	50.656	$ 1.633\, 3\times10^{-4} $	$ 2.033\, 9\times10^{-4} $
		SVT	104	412.31	$ 1.995\, 6\times10^{-4} $	$ 2.121\, 1\times10^{-4} $
8 000	10	ADMM	33	72.204	$ 1.946\, 5\times10^{-4} $	$ 1.407\, 4\times10^{-4} $
		IADM	28	62.125	$ 1.791\, 3\times10^{-4} $	$ 2.170\, 7\times10^{-4} $
		SVT	92	347.45	$ 1.911\, 4\times10^{-4} $	$ 1.966\, 9\times10^{-4} $
8 000	20	ADMM	33	99.171	$ 1.888\, 3\times10^{-4} $	$ 1.423\, 0\times10^{-4} $
		IADM	28	87.192	$ 1.721\, 4\times10^{-4} $	$ 2.121\, 2\times10^{-4} $
		SVT	100	677.45	$ 1.961\, 3\times10^{-4} $	$ 2.056\, 2\times10^{-4} $
10 000	10	ADMM	33	137.96	$ 1.987\, 2\times10^{-4} $	$ 1.447\, 5\times10^{-4} $
		IADM	28	125.39	$ 1.807\, 5\times10^{-4} $	$ 2.207\, 6\times10^{-4} $
		SVT	89	560.32	$ 1.996\, 9\times10^{-4} $	$ 2.042\, 0\times10^{-4} $
10 000	20	ADMM	33	138.61	$ 1.953\, 1\times10^{-4} $	$ 1.471\, 2\times10^{-4} $
		IADM	28	120.99	$ 1.769\, 7\times10^{-4} $	$ 2.184\, 4\times10^{-4} $
		SVT	98	1 016.8	$ 1.884\, 4\times10^{-4} $	$ 1.959\, 6\times10^{-4} $

表2

表3

IADM算法与ADMM算法、SVT算法的比较(当$ p=0.5 $时)"

$ n $	$ r $	算法	iter	$ t $/s	error1	error2
2 000	10	ADMM	24	3.280 0	$ 1.697\, 9\times10^{-4} $	$ 1.725\, 1\times10^{-4} $
		IADM	21	3.002 6	$ 1.543\, 7\times10^{-4} $	$ 1.563\, 5\times10^{-4} $
		SVT	106	27.883	$ 1.928\, 5\times10^{-4} $	$ 2.068\, 8\times10^{-4} $
2 000	20	ADMM	24	4.680 1	$ 1.514\, 4\times10^{-4} $	$ 1.372\, 0\times10^{-4} $
		IADM	21	4.614 1	$ 1.327\, 8\times10^{-4} $	$ 1.374\, 5\times10^{-4} $
		SVT	120	57.562	$ 1.924\, 4\times10^{-4} $	$ 2.151\, 9\times10^{-4} $
4 000	10	ADMM	25	12.592	$ 1.937\, 8\times10^{-4} $	$ 1.026\, 9\times10^{-4} $
		IADM	21	10.984	$ 1.826\, 7\times10^{-4} $	$ 1.766\, 3\times10^{-4} $
		SVT	95	91.283	$ 1.956\, 9\times10^{-4} $	$ 2.033\, 0\times10^{-4} $
4 000	20	ADMM	24	19.381	$ 1.977\, 4\times10^{-4} $	$ 1.839\, 9\times10^{-4} $
		IADM	21	17.361	$ 1.723\, 6\times10^{-4} $	$ 1.693\, 1\times10^{-4} $
		SVT	106	186.15	$ 1.922\, 6\times10^{-4} $	$ 2.047\, 2\times10^{-4} $
6 000	10	ADMM	26	31.701	$ 1.172\, 4\times10^{-4} $	$ 1.090\, 6\times10^{-4} $
		IADM	21	26.698	$ 1.906\, 1\times10^{-4} $	$ 1.873\, 6\times10^{-4} $
		SVT	91	163.39	$ 1.880\, 6\times10^{-4} $	$ 1.928\, 9\times10^{-4} $
6 000	20	ADMM	24	19.381	$ 1.977\, 4\times10^{-4} $	$ 1.089\, 5\times10^{-4} $
		IADM	21	17.361	$ 1.723\, 6\times10^{-4} $	$ 1.693\, 1\times10^{-4} $
		SVT	99	476.83	$ 1.998\, 1\times10^{-4} $	$ 2.087\, 2\times10^{-4} $
8 000	10	ADMM	26	54.558	$ 1.210\, 2\times10^{-4} $	$ 1.121\, 7\times10^{-4} $
		IADM	21	44.425	$ 1.982\, 1\times10^{-4} $	$ 1.919\, 2\times10^{-4} $
		SVT	87	287.02	$ 1.983\, 8\times10^{-4} $	$ 2.021\, 9\times10^{-4} $
8 000	20	ADMM	26	76.760	$ 1.120\, 1\times10^{-4} $	$ 1.142\, 3\times10^{-4} $
		IADM	21	64.043	$ 1.957\, 5\times10^{-4} $	$ 1.871\, 6\times10^{-4} $
		SVT	96	513.93	$ 1.926\, 5\times10^{-4} $	$ 1.992\, 3\times10^{-4} $
10 000	10	ADMM	26	105.34	$ 1.204\, 6\times10^{-4} $	$ 1.143\, 3\times10^{-4} $
		IADM	21	90.048	$ 1.995\, 2\times10^{-4} $	$ 1.928\, 9\times10^{-4} $
		SVT	86	468.19	$ 1.949\, 9\times10^{-4} $	$ 1.980\, 4\times10^{-4} $
10 000	20	ADMM	26	103.49	$ 1.134\, 2\times10^{-4} $	$ 1.177\, 7\times10^{-4} $
		IADM	21	86.656	$ 1.995\, 4\times10^{-4} $	$ 9.336\, 6\times10^{-4} $
		SVT	93	748.99	$ 1.943\, 3\times10^{-4} $	$ 1.996\, 6\times10^{-4} $

表3

图1

表4

参考文献 23

1	Candès E J , Plan Y . Matrix completion with noise[J]. Proceedings of the IEEE, 2010, 98 (6): 925- 936. doi: 10.1109/JPROC.2009.2035722
2	Spyromitros-xioufis E , Tsoumakas G , Groves W , et al. Multi-target regression via input space expansion: Treating targets as inputs[J]. Machine Learning, 2016, 104 (1): 55- 98. doi: 10.1007/s10994-016-5546-z
3	Hayashi N , Watanabe S . Upper bound of bayesian generalization error in non-negative matrix factorization[J]. Neurocomputing, 2017, 266 (29): 21- 28.
4	Xue H Y , Zhang S M , Cai D . Depth image inpainting: Improving low rank matrix completion with low gradient regularization[J]. IEEE Transactions on Image Processing, 2017, 26 (9): 4311- 4320. doi: 10.1109/TIP.2017.2718183
5	Candès E J , Recht B . Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9 (6): 717- 772. doi: 10.1007/s10208-009-9045-5
6	Cai J F , Candès E J , Shen Z W . A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20 (4): 1956- 1982. doi: 10.1137/080738970
7	Lin Z C, Chen M M, Ma Y. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices [R]. Champaign: Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 2009.
8	Chen C H , He B S , Yuan X M . Matrix completion via an alternating direction method[J]. IMA Journal of Numerical Analysis, 2011, 32 (1): 227- 245.
9	He B S , Xu M H , Yuan X M . Solving large-scale least squares semidefinite programming by alternating direction methods[J]. SIAM Journal on Matrix Analysis and Applications, 2009, 32 (1): 136- 152.
10	Ng M K , Weiss P , Yuan X M . Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods[J]. SIAM Journal on Scientific Computing, 2009, 32 (5): 2710- 2736.
11	闫喜红, 王川龙, 李超, 等. 求解低秩矩阵恢复问题的非单调交替梯度方向法[J]. 中国科学: 数学, 2021, 51 (4): 549- 560.
12	Yang J F , Zhang Y . Alternating direction algorithms for 11-problems in compressive sensing[J]. SIAM Journal on Scientific Computing, 2009, 33 (1): 250- 278.
13	Ochs P , Chen Y J , Brox T , et al. iPiano: Inertial proximal algorithm for nonconvex optimization[J]. SIAM Journal on Imaging Sciences, 2014, 7 (2): 1388- 1419. doi: 10.1137/130942954
14	Polyak B T . Some methods of speeding up the convergence of iteration methods[J]. USSR Computational Mathematics and Mathematical Physics, 1964, 5 (4): 1- 17.
15	Lorenz D A , Pock T . An inertial forward-backward algorithm for monotone inclusions[J]. Journal of Mathematical Imaging and Vision, 2015, 51 (2): 311- 325.
16	Ochs P , Brox T , Pock T . iPiasco: Inertial proximal algorithm for strongly convex optimization[J]. Journal of Mathematical Imaging and Vision, 2015, 53 (2): 171- 181.
17	Bot R I , Csetnek E R , Hendrich C . Inertial douglas-rachford splitting for monotone inclusion problems[J]. Applied Mathematics and Computation, 2015, 256, 472- 487.
18	Bot R I, Csetnek E R. An inertial alternating direction method of multipliers [EB/OL]. (2014-04-17)[2022-08-28]. arXiv: 1404.4582.
19	Chen C H , Ma S Q , Yang J F . A general inertial proximal point algorithm for mixed variational inequality problem[J]. SIAM Journal on Optimization, 2015, 25 (4): 2120- 2142.
20	Chen C H , Chan R H , Ma S Q , et al. Inertial proximal ADMM for linearly constrained separable convex optimization[J]. SIAM Journal on Imaging Sciences, 2015, 8 (4): 2239- 2267.
21	Golub G H , Van Loan C F . Matrix Computations[M]. Baltimore: Johns Hopkins University Press, 1996.
22	He B S , Ma F , Xu S J , et al. A generalized primal-dual algorithm with improved convergence condition for saddle point problems[J]. SIAM Journal on Imaging Sciences, 2022, 15 (3): 1157- 1183.
23	Beck A . First-Order Methods in Optimization[M]. Philadelphia: Society for Industrial and Applied Mathematics, 2017.

像素	$ p $	算法	iter	$ t $/s	error1	PSNR
256*256	0.4	IADM	222	1.964 8	$ 1.940\, 9\times10^{-4} $	25.795 5
		SVT	987	10.758	$ 1.994\, 5\times10^{-4} $	2.170 7
256*256	0.6	IADM	215	1.867 9	$ 1.819\, 7\times10^{-4} $	29.620 8
		SVT	952	8.517 6	$ 1.998\, 9\times10^{-4} $	3.976 8
256*256	0.8	IADM	99	0.849 1	$ 1.773\, 9\times10^{-4} $	32.569 4
		SVT	924	8.901 3	$ 1.953\, 9\times10^{-4} $	6.984 0
512*512	0.4	IADM	401	17.150 1	$ 1.822\, 7\times10^{-4} $	21.817 6
		SVT	945	51.200	$ 1.992\, 7\times10^{-4} $	2.139 3
512*512	0.6	IADM	383	16.275 1	$ 1.931\, 9\times10^{-4} $	25.775 7
		SVT	574	26.014	$ 1.993\, 6\times10^{-4} $	3.982 2
512*512	0.8	IADM	352	14.782 7	$ 1.956\, 2\times10^{-4} $	30.185 0
		SVT	982	44.055	$ 1.993\, 3\times10^{-4} $	6.979 1

[1]	黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114.
[2]	冯俊锴, 张海斌, 秦嫒, 张凯丽. 解一类结构变分不等式问题的非精确并行交替方向法[J]. 运筹学学报, 2018, 22(2): 18-30.
[3]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79-92.
[4]	何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31.
[5]	万芮, 徐姿. 广义交替近似梯度算法的线性收敛分析[J]. 运筹学学报, 2014, 18(3): 1-12.
[6]	卢越, 张继宏, 张立卫. 一类二次规划逆问题的交替方向数值方法[J]. 运筹学学报, 2014, 18(2): 1-16.