中文

Operations Research Transactions >

2025 , Vol. 29 >Issue 1: 172 - 184

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

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

Expand
  • 1. School of Mathematics and Statistics, Taiyuan Normal University, Jinzhong 030619, Shanxi, China

Received date: 2022-09-28

  Online published: 2025-03-08

Copyright

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

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

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.014

References

1 Candès E J , Plan Y . Matrix completion with noise[J]. Proceedings of the IEEE, 2010, 98 (6): 925- 936.
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.
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.
5 Candès E J , Recht B . Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9 (6): 717- 772.
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.
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.
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.
Options
Outlines

/

〈 〉