# American Institute of Mathematical Sciences

• Previous Article
A new iterative identification method for damping control of power system in multi-interference
• DCDS-S Home
• This Issue
• Next Article
Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem
June  2020, 13(6): 1757-1772. doi: 10.3934/dcdss.2020103

## An alternating minimization method for matrix completion problems

 1 School of Applied Mathematics, Nanjing University Of Finance & Economics, China 2 State Key Laboratory of Scientific and Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, University of Chinese Academy of Sciences, China

* Corresponding author

Received  September 2018 Revised  November 2018 Published  September 2019

Fund Project: The first author is supported by NSFC grants 11401295 and 11726618, and by Major Program of the National Social Science Foundation of China under Grant 12 & ZD114 and by National Social Science Foundation of China under Grant 15BGL158, 17BTQ063 and by Qinglan Project of Jiangsu Province, and Social Science Foundation of Jiangsu Province under Grant 18GLA002. The second author is supported by NSFC grants 11622112, 11471325, 91530204 and 11688101, the National Center for Mathematics and Interdisciplinary Sciences, CAS, and Key Research Program of Frontier Sciences QYZDJ-SSW-SYS010, CAS

Matrix completion problems have applications in various domains such as information theory, statistics, engineering, etc. Meanwhile, solving matrix completion problems is not a easy task since the nonconvex and nonsmooth rank operation is involved. Existing approaches can be categorized into two classes. The first ones use nuclear norm to take the place of rank operation, and any convex optimization algorithms can be used to solve the reformulated problem. The limitation of this class of approaches is singular value decomposition (SVD) is involved to tackle the nuclear norm which significantly increases the computational cost. The other ones factorize the target matrix by two slim matrices. Fast algorithms for solving the reformulated nonconvex optimization problem usually lack of global convergence, meanwhile convergence guaranteed algorithms require restricted stepsize. In this paper, we consider the matrix factorization model for matrix completion problems, and propose an alternating minimization method for solving it. The global convergence to a stationary point or local minimizer is guaranteed under mild conditions. We compare the proposed algorithm with some state-of-the-art algorithms in solving a bunch of testing problems. The numerical results illustrate the efficiency and great potential of our algorithm.

Citation: Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103
##### References:

show all references

##### References:
Relative error vs iteration number, $m$ = $n$ = 2000
Computing time vs sampling ratio, $m$ = $n$ = 2000
Computing time vs dimension
Results of speed performance test for synthetic data with $m$ = $n$ = $2000$
 Problem settings SVT LMaFit New Algorithm sampling ratio rank($L^*$) $\hbox{err}_{\Omega}(L)$ iter time $\hbox{err}_{\Omega}(L)$ iter time $\hbox{err}_{\Omega}(L)$ iter time 20% 5 8.947e-13 126.0 10.288 8.396e-13 67.7 1.746 8.880e-13 42.7 1.218 10 1.183e-7 190.2 22.593 9.005e-13 66.8 1.892 8.525e-13 57.3 1.821 40% 5 8.494e-13 87.0 12.286 7.022e-13 33.3 1.376 6.705e-13 24.2 1.100 10 8.702e-13 101.7 19.319 7.169e-13 39.2 1.722 7.001e-13 29.9 1.468 60% 5 8.470e-13 72.3 14.429 6.895e-13 33.2 1.821 5.106e-13 18.0 1.096 10 8.465e-13 80.4 18.717 7.573e-13 39.1 2.237 5.467e-13 21.0 1.334 80% 5 8.765e-13 62.3 15.112 6.556e-13 23.1 1.547 3.881e-13 15.0 1.100 10 8.180e-13 67.5 19.641 6.421e-13 25.1 1.801 4.308e-13 16.7 1.322
 Problem settings SVT LMaFit New Algorithm sampling ratio rank($L^*$) $\hbox{err}_{\Omega}(L)$ iter time $\hbox{err}_{\Omega}(L)$ iter time $\hbox{err}_{\Omega}(L)$ iter time 20% 5 8.947e-13 126.0 10.288 8.396e-13 67.7 1.746 8.880e-13 42.7 1.218 10 1.183e-7 190.2 22.593 9.005e-13 66.8 1.892 8.525e-13 57.3 1.821 40% 5 8.494e-13 87.0 12.286 7.022e-13 33.3 1.376 6.705e-13 24.2 1.100 10 8.702e-13 101.7 19.319 7.169e-13 39.2 1.722 7.001e-13 29.9 1.468 60% 5 8.470e-13 72.3 14.429 6.895e-13 33.2 1.821 5.106e-13 18.0 1.096 10 8.465e-13 80.4 18.717 7.573e-13 39.1 2.237 5.467e-13 21.0 1.334 80% 5 8.765e-13 62.3 15.112 6.556e-13 23.1 1.547 3.881e-13 15.0 1.100 10 8.180e-13 67.5 19.641 6.421e-13 25.1 1.801 4.308e-13 16.7 1.322
 [1] Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076 [2] Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074 [3] Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $p$ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020442 [4] Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321 [5] Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 [6] Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345 [7] Shiqiu Fu, Kanishka Perera. On a class of semipositone problems with singular Trudinger-Moser nonlinearities. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020452 [8] Antoine Benoit. Weak well-posedness of hyperbolic boundary value problems in a strip: when instabilities do not reflect the geometry. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5475-5486. doi: 10.3934/cpaa.2020248 [9] S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435 [10] Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375 [11] Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052 [12] Lei Liu, Li Wu. Multiplicity of closed characteristics on $P$-symmetric compact convex hypersurfaces in $\mathbb{R}^{2n}$. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378 [13] Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247 [14] Maoding Zhen, Binlin Zhang, Vicenţiu D. Rădulescu. Normalized solutions for nonlinear coupled fractional systems: Low and high perturbations in the attractive case. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020379 [15] Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347 [16] Anna Canale, Francesco Pappalardo, Ciro Tarantino. Weighted multipolar Hardy inequalities and evolution problems with Kolmogorov operators perturbed by singular potentials. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020274 [17] Susmita Sadhu. Complex oscillatory patterns near singular Hopf bifurcation in a two-timescale ecosystem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020342

2019 Impact Factor: 1.233