Computer Science ›› 2018, Vol. 45 ›› Issue (6): 193-196.doi: 10.11896/j.issn.1002-137X.2018.06.034

• Artificial Intelligence • Previous Articles     Next Articles

Matrix Completion Algorithm Based on Subspace Thresholding Pursuit

WANG Zhi1,2, WANG Jian-jun1, WANG Wen-dong2   

  1. School of Mathematics and Statistics,Southwest University,Chongqing 400715,China1;
    College of Computer & Information Science,Southwest University,Chongqing 400715,China2
  • Received:2017-05-07 Online:2018-06-15 Published:2018-07-24

Abstract: Low rank matrix completion is the most basic problem in machine learning and data analysis.It plays a key role in solving many important problems,such as collaborative filtering,dimensionality reduction,multi-task learning and pattern recognition.Focusing on the problems that the ADMiRA mayhave a slow convergence rate and easily fall into local optimal drawbacks,this paper proposed a new algorithm by adding SVP into SP’s every iteration.Through making use of SVP’s advantage of quick convergence,the proposed algorithm improves SP’s convergence speed,and gets better result.This algorithm was implemented and tested on several simulated datasets and image datasets.Experiments reveal very encouraging results in terms of the found quality of solution and the required processing time.

Key words: ADMiRA, Local convergence, Low rank matrix completion, SP, SVP

CLC Number: 

  • TP181
[1]RENNIE J,SREBRO N.Fast maximum margin matrix factorization for collaborative prediction[C]//22th International Conference on Machine Learning (ICML).2005:713-719.
[2]KILIAN Q W,LAWRENCE K S.Unsupervised learning of image manifolds by semidefinite programming[C]//IEEE Con-ference on Computer Vision and Pattern Recognition,2004:988-995.
[3]ARGYRIOU A,EVGENIOU T,PONTIL M.Convex multi-task feature learning[J].Machine Learning,2008,73(3):243-272.
[4]ARGYRIOU A,EVGENIOU T,PONTIL M.Convex multi-task feature learning[C]//Proceedings of the Neural Information Processing Systems Conference (NIPS).2006:41-48.
[5]FAZEL M.Matrix Rank Minimization with Applications[D].California:Stanford University,2002.
[6]CAI J F,EMMANUEL J C,SHEN Z W.A singular value thresholding algorithmfor matrix completion[J].SIAM Journal on Optimization,2010,20(4):1956-1982.
[7]JI S,YE J. An accelerated gradient method for trace norm minimization[C]//26th International Conference on Machine Lear-ning (ICML).2009:457-464.
[8]LIU J J,SUN D,TOH K C.An implementable proximal point algorithmic framework for nuclear norm minimization[J].Mathe-matical Programming,2012,133(1):399-436.
[9]TOH K C,YUN S.An accelerated proximal gradient algorithm for nuclear norm regularized leastsquares problems[J].Pacific Journal of Optimization,2010,6(3):615-640.
[10]SHAI S S,GONEN A,SHAMIR O.Large-scale convex minimization with a low-rankconstraint[C]//28th International Conference on Machine Learning(ICML).2011:329-336.
[11]WANG Z,LAI M J,LU Z S,et al.Orthogonal rank-one matrix pursuit for low-rank matrix completion[J].SIAM Journal on Scientific Computing,2015,37(1):488-514.
[12]ZHANG X H,DALE S,YU Y L.Accelerated training for matrix-norm regularization:A boosting approach[C]//Proceedings of the Neural Information Processing Systems Conference (NIPS).2012:2906-2914.
[13]MARTIN J,MAREK S.A simple algorithm for nuclear norm regularized problems[C]//27th International Conference on Machine Learning (ICML).2010:471-478.
[14]LEE K,BRESLER Y.Admira:atomic decomposition for minimum rank approximation[J].IEEE Transactions on Information Theory,2010,56(9):4402-4416.
[15]MEKA R,JAIN P,DHILLON I S.Guaranteed Rank Minimization via Singular Value Projection[C]//Proceedings of the Neural Information Processing Systems Conference (NIPS).2010:937-945.
[16]TANNER J,WEI K.Normalized iterative hard thresholding for matrix completion[J].SIAM Journal on Scientific Computing,2010,35(5):4402-4416.
[17]DEANNA N,JOEL A T.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis,2009,26(3):301-321.
[18]DAI W,MILENKOVIC O.Subspace pursuit for compressive sensing signal reconstruction[J].IEEE Transactions on Information Theory,2009,55(5):2230-2249.
[19]SONG C B,XIA S T,LIU X J.Subspace Thresholding Pursuit:A Reconstruction Algorithm for Compressed Sensing[C]//IEEE International Symposium on Information Theory (ISIT).2015:536-540.
[1] ZHANG Jia, DONG Shou-bin. Cross-domain Recommendation Based on Review Aspect-level User Preference Transfer [J]. Computer Science, 2022, 49(9): 41-47.
[2] ZHOU Lian-bing, ZHOU Xiang-zhen, CUI Xue-rong. Compressed Image Encryption Scheme Based on Dual Two Dimensional Chaotic Map [J]. Computer Science, 2022, 49(8): 344-349.
[3] LI Xia, MA Qian, BAI Mei, WANG Xi-te, LI Guan-yu, NING Bo. RIIM:Real-Time Imputation Based on Individual Models [J]. Computer Science, 2022, 49(8): 56-63.
[4] WEI Kai-xuan, FU Ying. Re-parameterized Multi-scale Fusion Network for Efficient Extreme Low-light Raw Denoising [J]. Computer Science, 2022, 49(8): 120-126.
[5] TAN Ying-ying, WANG Jun-li, ZHANG Chao-bo. Review of Text Classification Methods Based on Graph Convolutional Network [J]. Computer Science, 2022, 49(8): 205-216.
[6] ZHANG Lu-ping, XU Fei. Survey on Spiking Neural P Systems with Rules on Synapses [J]. Computer Science, 2022, 49(8): 217-224.
[7] LIU Gao-cong, LUO Yong-ping, JIN Pei-quan. Accelerating Persistent Memory-based Indices Based on Hotspot Data [J]. Computer Science, 2022, 49(8): 26-32.
[8] LI Rong-fan, ZHONG Ting, WU Jin, ZHOU Fan, KUANG Ping. Spatio-Temporal Attention-based Kriging for Land Deformation Data Interpolation [J]. Computer Science, 2022, 49(8): 33-39.
[9] SHAN Yong-feng, JIANG Rui, XU You-yun, LI Da-peng. Power Consumption Scheme Oriented to Full-duplex Multi-relay Cooperative SWIPT Networks [J]. Computer Science, 2022, 49(7): 280-286.
[10] PAN Zhi-yong, CHENG Bao-lei, FAN Jian-xi, BIAN Qing-rong. Algorithm to Construct Node-independent Spanning Trees in Data Center Network BCDC [J]. Computer Science, 2022, 49(7): 287-296.
[11] HUANG Jue, ZHOU Chun-lai. Frequency Feature Extraction Based on Localized Differential Privacy [J]. Computer Science, 2022, 49(7): 350-356.
[12] SUN Xiao-han, ZHANG Li. Collaborative Filtering Recommendation Algorithm Based on Rating Region Subspace [J]. Computer Science, 2022, 49(7): 50-56.
[13] ZENG Zhi-xian, CAO Jian-jun, WENG Nian-feng, JIANG Guo-quan, XU Bin. Fine-grained Semantic Association Video-Text Cross-modal Entity Resolution Based on Attention Mechanism [J]. Computer Science, 2022, 49(7): 106-112.
[14] XU Ming-ke, ZHANG Fan. Head Fusion:A Method to Improve Accuracy and Robustness of Speech Emotion Recognition [J]. Computer Science, 2022, 49(7): 132-141.
[15] MENG Yue-bo, MU Si-rong, LIU Guang-hui, XU Sheng-jun, HAN Jiu-qiang. Person Re-identification Method Based on GoogLeNet-GMP Based on Vector Attention Mechanism [J]. Computer Science, 2022, 49(7): 142-147.
Full text



No Suggested Reading articles found!