Matrix Completion via Successive Low-rank Matrix Approximation




matrix completion, low-rank matrix approximation, hard thresholding


In this paper, a successive low-rank matrix approximation algorithm is presented for the matrix completion (MC) based on hard thresholding method, which approximate the optimal low-rank matrix from rank-one matrix step by step. The algorithm enables the distance between the matrix with the observed elements and the projection on low-rank manifold to be minimum. The optimal low-rank matrix with observed elements is obtained when the distance is zero. In theory, convergence and convergent error of the new algorithm are analyzed in detail. Furthermore, some numerical experiments show that the algorithm is more effective in CPU time and precision than the orthogonal rank-one matrix pursuit(OR1MP) algorithm and the augmented Lagrange multiplier (ALM) method when the sampling rate is low.


Amit, Y., Fink, M., Srebro, N. and Ullman, S.(2007) Uncovering shared structures in multiclass classification. in: Processings of the 24th International Conference on Machine Learing, ACM, 17–24

Argyriou, A.,Evgeniou, T., Pontil, M. (2007) Multi-task feature learing Adv. Neural Inf. Process Syst., 19, 41–48

Sarki, R., Ahmed, K., Wang,H., Zhang,Y. (2020) Automated detection of mild and multi-class diabetic eye diseases using deep learning,Health Information Science and Systems 8(1),1–9.

Bertalmio, M., Sapiro, G., Caselles, V., and Ballester, C. (2000) Image inpainting. Image inpainting, Comput. Graph, 34, 417–424

Supriya,S., Siuly S., H Wang and Y Zhang (2020) auto-mated epilepsy detection techniques from electroencephalo-gram signalsa review study, Health Information Science and Systems 8(1),1–15

Pandey, D., H Wang, X Yin, K Wang, Y Zhang and J Shen (2022) Automatic breast lesion segmentation in phase preserved DCE-MRIs, Health Information Science and Systems 10(1),1 19

Tomasi, C. and Kanade, T. (1992) Shape and motion from image streams under orthography: a factorization method, Int. J. Comput. Vis, 9, 137–154

Mesbahi, M. and Papavassilopoulos, G. P. (1997) On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Trans. Automat. Control, 42, 239–243

J. Y. Li, Zhan,Z.H., H. Wang and J. Zhang (2020) Data-driven evolutionary algorithm with perturbation-based ensemble surrogates, IEEE Transations on Cybernetics, 51(8), 3925–3937

Candès, E. J. and Recht, B. (2009) Exact matrix completion via convex optimization. Found. Comput. Math., 9, 717–772

Ma, S., Goldfarb D. and Chen L. (2011) Fixed point and bregman iterative methods for matrix rank minimization, Math. Program, 128, 321–353

Cai, J. F., Candès, E. J. and Shen, Z. (2010) A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 1956–1982

Toh, K. C. and Yun S. (2010) An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pac. J. Optim., 6, 615–640

Lin, Z., Chen, M., Wu, L. and Ma, Y. (2013) The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices, arXiv:1009.5055v3

Chen, C., He, B. and Yuan, X. (2012) Matrix completion via an alternating direction method, IMA J. Numer. Anal., 32, 227–245

Vandereycken, B. (2013) Low-rank matrix completion by Riemannian optimization, SIAM J. Optim., 23(2), 1214–1236

Mishra, B. and Apuroop, K. A. (2012) Sepulchre, R.: A Riemannian geometry for low-rank matrix completion, arXiv:1211.1550

Boumal, N. and Absil, P. A. (2011) RTRMC: A Riemannian trust-region method for low-rank matrix completion, Neural Information Processing Systems conference, NIPS

Tanner, J. and Wei, K. Low rank matrix completion by alternating steepest descent methods, Appl. Comput. Harmon. Anal., 40, 417–429 (2016)

Wang, Z., Lai, M., Lu, Z. and Fan, W., Davulcu, H. and Ye, J.( 2014) Orthogonal rank-one matrix pursuit for low rank matrix completion, SIAM J. Sci. Comput., 37, 488–514




How to Cite

Wang J, Mo Z. Matrix Completion via Successive Low-rank Matrix Approximation. EAI Endorsed Scal Inf Syst [Internet]. 2023 Jan. 4 [cited 2023 Mar. 28];10(3):e6. Available from: