Computer Science ›› 2014, Vol. 41 ›› Issue (4): 13-20.

Previous Articles     Next Articles

Research Progress in Matrix Completion Algorithms

SHI Jia-rong,ZHENG Xiu-yun and ZHOU Shui-sheng   

  • Online:2018-11-14 Published:2018-11-14

Abstract: As an important development of compressed sensing theory,matrix completion and recovery has been a new and remarkable technique for signal and image processing.This paper made a survey on the latest research progress in matrix completion algorithms.Firstly,it analyzed several main algorithms to nuclear norm minimization model,and elabo-rated their iterative procedure and principle.Secondly,it discussed low-rank matrix factorization model of matrix completion and listed the corresponding new algorithms emerged in recent years.Then it complemented other versions derived from the above two models and pointed out the solving methods.In numerical experiments,performance comparisons were made on the main algorithms to matrix completion.Finally,it gave future research direction and focus for matrix completion algorithms.

Key words: Matrix completion,Low-rank,Nuclear norm minimization,Low-rank matrix factorization,Compressed sen-sing,Low-rank matrix recovery

[1] Donoho D.Compressed sensing [J].IEEE Transactions on Information Theory,2006,52(4):1289-1306
[2] Candès E J,Michael W.An introduction to compressive sam-pling [J].IEEE Signal Processing Magazine,2008,25(2):21-30
[3] Candès E J,Tao T.The power of convex relaxation:Near-optimal matrix completion [J].IEEE Transactions on Information Theory,2010,56(5):2053-2080
[4] Candès E J,Plan Y.Matrix completion with noise [J].Procee-dings of the IEEE,2010,98(6):925-936
[5] 史加荣,郑秀云,魏宗田,等.低秩矩阵恢复算法综述[J].计算机应用研究,2013,30(6):1601-1605
[6] Chen P.Optimization algorithms on subspaces:revisiting mis-sing data problem in low-rank matrix [J].International Journal of Computer Vision,2008,80(1):125-142
[7] Vidal R,Tron R,Hartley R.Multiframe motion segmentationwith missing data using PowerFactorization and GPCA [J].International Journal of Computer Vision,2008,79(1):85-105
[8] Ji Hui,Liu Chao-qiang,Shen Zuo-wei,et al.Robust video denoising using low rank matrix completion [C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR).2010:1791-1798
[9] Jing Guo-dong,Shi Yun-hui,Yin Bao-cai.Image super-resolution reconstruction based on sparse representation and low-rank matrix completion [J].Journal of Information & Computational Science,2012,9(13):3859-3866
[10] Rennie D M,Srebro N.Fast maximum margin matrix factorization for collaborative prediction [C]∥Proceedings of International Conference on Machine Learning(ICML).2005:713-719
[11] Cabral R S,Torre F D,Costeira J P,et al.Matrix completion for multi-label image classification[C]∥Proceedings of Neural Information Processing Systems (NIPS).2011:190-198
[12] Keshavan R H,Oh S.OptSpace:A gradient descent algorithm on the Grassman manifold for matrix completion [EB/OL].http://arxiv.org/pdf/0910.5260v2.pdf,2009
[13] Balzano L,Nowak R,Recht B.Online identification and tracking of subspaces from highly incomplete information [C]∥Procee-dings of Annual Allerton Conference on Communication,Control,and Computing.2010:704-711
[14] Liu Zhang,Hansson A,Vandenberghe L.Nuclear norm system identification with missing inputs and outputs [EB/OL].http://www.ee.ucla.edu/~vandenbe/publications/subspace.pdf,2012
[15] Recht B,Fazel M,Parrilo P A.Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization [J].SIAM Review,2010,52(3):471-501
[16] Fazel M.Matrix rank minimization with applications [D].Stanford University,2002
[17] Liu Zhang,Vandenberghe L.Interior-point method for nuclear norm approximation with application to system identification [J].SIAM Journal on Matrix Analysis and Applications,2009,31(3):1235-1256
[18] Cai Jian-feng,Candès E J,Shen Zuo-wei.A singular valuethresholding algorithm for matrix completion [J].SIAM Journal on Optimization,2010,20(4):1956-1982
[19] Hu Yao,Zhang De-bing,Liu Jun,et al.Accelerated singular va-lue thresholding for matrix completion [C]∥Proceedings of ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.2012:298-306
[20] Cai Jian-feng,Osher S.Fast singular value thresholding without singular value decomposition[J].Methods and Applications of Analysis,2013,20(4):335-352
[21] Donald Goldfarb D,Ma Shi-qian.Convergence of fixed-pointcontinuation algorithms for matrix rank minimization [J].Foundations of Computational Mathematics,2011,1(2):183-210
[22] Ma Shi-qian,Goldfarb D,Chen Li-feng.Fixed point and Bregman iterative methods for matrix rank minimization [J].Mathematical Programming,2011,128(1/2):321-353
[23] Toh K C,Yun S.An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems [J].Pacific Journal of Optimization,2010,6:615-640
[24] Lin Zhou-chen,Chen Min-ming,Ma Yi,et al.The augmentedLagrange multiplier method for exact recovery of corrupted low-rank matrices [EB/OL].http:// arxiv.org/pdf/1009.5055,2010
[25] Chen Cai-hua,He Bing-sheng,Yuan Xiao-ming.Matrix completion via an alternating direction method[J].IMA Journal of Numerical Analysis,2012,2(1):227-245
[26] Yang Jun-feng,Yuan Xiao-ming.Linearized augmented La-grangian and alternating direction methods for nuclear norm minimization [J].Mathematics of Computation,2013,82(281):301-329
[27] Keshavan R H,Montanari A,Sewoong Oh.Matrix completion from a few entries[J].IEEE Transactions on Information Theory,2010,56(6):2980-2998
[28] Dai Wei,Kerman E,Milenkovic O.A geometric approach to low-rank matrix completion [J].IEEE Transactions on Information Theory,2012,58(1):237-247
[29] Boumal N,Absil P A.RTRMC:A Riemannian trust-regionmethod for low-rank matrix completion[C]∥Proceedings of Neural Information Processing Systems (NIPS).2011
[30] Jain P,Meka R,Dhillon I.Guaranteed rank minimization via singular value projection[EB/OL].http://arxiv.org/abs/0909.5457,2009
[31] Wen Zai-wen,Yin Wo-tao,Zhang Yin.Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm[J].Mathematical Programming Computation,2012,4(4):333-361
[32] Zhang De-bing,Hu Yao,Ye Jie-ping,et al.Matrix completion by truncated nuclear norm regularization[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR).2012:2192-2199
[33] Nie Fei-ping,Huang H,Ding C.Low-rank matrix recovery viaefficient schatten p-norm minimization[C]∥Proceedings of AAAI Conference on Artificial Intelligence.2012:655-661
[34] Lee K,Bresler Y.ADMiRA:Atomic decomposition for minimum rank approximation[J].IEEE Transactions on Information Theo-ry,2010,56(9):4402-4416
[35] Cai T T,Zhou Wen-xin.Matrix completion via max-norm constrained optimization [EB/OL].http:// arxiv.org/pdf/1303.0341v1.pdf,2013
[36] Recht B,Christopher Re C.Parallel stochastic gradient algo-rithms for large-scale matrix completion [EB/OL].http://pages.cs.wisc.edu/~brecht/papers/11.Rec.Re.IPGM.pdf,2013
[37] 史加荣,焦李成,尚凡华.不完全非负矩阵分解的加速算法[J].电子学报,2011,9(2):291-295
[38] Xu Yang-yang,Yin Wo-tao,Wen Zai-wen,et al.An alternating direction algorithm for matrix completion with nonnegative factors [J].Frontiers of Mathematics in China,2012,7(2):365-384
[39] 尚凡华.基于低秩结构学习数据表示[D].西安:西安电子科技大学,2012
[40] Mazumder R,Hastie T,Tibshirani R.Spectral regularization algorithms for learning large incomplete matrices[J].Journal of Machine Learning Research,2010,1:2287-2322
[41] Mohan K,Fazel M.Iterative reweighted algorithms for matrix rank minimization [J].Journal of Machine Learning Research,2012,3:3441-3473
[42] Xin Yu,Tommi Jaakkola T.Primal-Dual methods for sparseconstrained matrix completion[J].Journal of Machine Learning Research-Proceedings Track,2012,2:1323-1331
[43] Liu Ji,Musialski P,Wonka P,et al.Tensor completion for estimating missing values in visual data[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,5(1):208-220
[44] Signoretto M,Van de Plas,R,De Moor B,et al.Tensor versus matrix completion:a comparison with application to spectral data[J].IEEE Signal Processing Letters,2011,18(7):403-406
[45] 史加荣,焦李成,尚凡华.张量补全算法及其在人脸识别中的应用[J].模式识别与人工智能,2011,4(2):255-261
[46] Julià C,Sappa A D,Lumbreras F,et al.Rank estimation in mis-sing data matrix problems[J].Journal of Mathematical Imaging and Vision,2011,39:140-160

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!