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

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

CLC Number:

O221.2

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.

Figures/Tables 5

$ 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} $

$ 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} $

$ 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} $

References 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]	Xinqing MENG, Wenxing ZAHNG. An accelerated method for solving a class of linear equality constrained convex optimization [J]. Operations Research Transactions, 2024, 28(1): 1-17.
[2]	Jianwen PENG, Hongwang LEI. A class of inertial symmetric regularization alternating direction method of multipliers for nonconvex two-block optimization [J]. Operations Research Transactions, 2023, 27(3): 37-52.
[3]	Maoran WANG, Xingju CAI, Zhongming WU, Deren HAN. First-order splitting algorithm for multi-model traffic equilibrium problems [J]. Operations Research Transactions, 2023, 27(2): 63-78.
[4]	Wenhui XIE, Chen LING, Chenjian PAN. A tensor completion method based on tensor train decomposition and its application in image restoration [J]. Operations Research Transactions, 2022, 26(3): 31-43.
[5]	WANG Shuangyue, LUO Ziyan. Low rank support tensor machine based on L_0/1 soft-margin loss function [J]. Operations Research Transactions, 2021, 25(3): 160-172.
[6]	LI Chaoqiong, LI Feng. A partial parallel splitting LQP alternating direction method of multipliers for solving monotone variational inequalities [J]. Operations Research Transactions, 2020, 24(1): 101-114.
[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]	YANG Junfeng. An algorithmic review for total variation regularized data fitting problems in image processing [J]. Operations Research Transactions, 2017, 21(4): 69-83.
[9]	WAN Rui, XU Zi. On the linear convergence of the general alternating proximal gradient method for convex minimization [J]. Operations Research Transactions, 2014, 18(3): 1-12.
[10]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.

An inertial alternating direction method of multiplier for low rank matrix completion

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 23

Related Articles 10

Recommended Articles

Metrics

Comments