基于子空间阈值追踪的矩阵修补算法

doi:10.11896/j.issn.1002-137X.2018.06.034

计算机科学 ›› 2018, Vol. 45 ›› Issue (6): 193-196.doi: 10.11896/j.issn.1002-137X.2018.06.034

基于子空间阈值追踪的矩阵修补算法

王智^1,2, 王建军¹, 王文东²

西南大学数学与统计学院重庆400715¹;
西南大学计算机与信息科学学院重庆400715²

收稿日期:2017-05-07 出版日期:2018-06-15 发布日期:2018-07-24
作者简介:王智(1982-),男,博士生,主要研究方向为机器学习、低秩矩阵修补,E-mail:chiw@swu.edu.cn(通信作者);王建军(1976-),男,博士,教授,博士生导师,主要研究方向为机器学习、低秩矩阵修补、压缩感知、逼近论;王文东(1988-),男,博士生,主要研究方向为低秩矩阵修补、压缩感知
基金资助:
本文受国家自然科学基金(61673015),西南大学实验研究项目(SYJ2016024)资助

Matrix Completion Algorithm Based on Subspace Thresholding Pursuit

WANG Zhi^1,2, WANG Jian-jun¹, WANG Wen-dong²

School of Mathematics and Statistics,Southwest University,Chongqing 400715,China¹;
College of Computer & Information Science,Southwest University,Chongqing 400715,China²

Received:2017-05-07 Online:2018-06-15 Published:2018-07-24

摘要/Abstract

摘要： 低秩矩阵修补是机器学习和数据分析中的核心问题,被广泛应用于协同过滤、降维处理、多任务学习和模式识别等领域。针对ADMiRA算法存在收敛速度慢、易陷入局部最优等缺陷,通过在SP算法的每次迭代过程中引入SVP算法,提出一种基于子空间阈值追踪的矩阵修补算法。其利用SVP算法快速收敛的特性,提升了SP算法的收敛速度,且能得到更优的解。仿真实验验证了所提算法的性能。

关键词: ADMiRA算法, SP算法, SVP算法, 低秩矩阵修补, 局部收敛性

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

中图分类号:

TP181

王智, 王建军, 王文东. 基于子空间阈值追踪的矩阵修补算法[J]. 计算机科学, 2018, 45(6): 193-196. https://doi.org/10.11896/j.issn.1002-137X.2018.06.034

WANG Zhi, WANG Jian-jun, WANG Wen-dong. Matrix Completion Algorithm Based on Subspace Thresholding Pursuit[J]. Computer Science, 2018, 45(6): 193-196. https://doi.org/10.11896/j.issn.1002-137X.2018.06.034

参考文献

[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.

相关文章 15

[1]	程章桃, 钟婷, 张晟铭, 周帆. 基于图学习的推荐系统研究综述 Survey of Recommender Systems Based on Graph Learning 计算机科学, 2022, 49(9): 1-13. https://doi.org/10.11896/jsjkx.210900072
[2]	熊丽琴, 曹雷, 赖俊, 陈希亮. 基于值分解的多智能体深度强化学习综述 Overview of Multi-agent Deep Reinforcement Learning Based on Value Factorization 计算机科学, 2022, 49(9): 172-182. https://doi.org/10.11896/jsjkx.210800112
[3]	齐秀秀, 王佳昊, 李文雄, 周帆. 基于概率元学习的矩阵补全预测融合算法 Fusion Algorithm for Matrix Completion Prediction Based on Probabilistic Meta-learning 计算机科学, 2022, 49(7): 18-24. https://doi.org/10.11896/jsjkx.210600126
[4]	高振卓, 王志海, 刘海洋. 嵌入典型时间序列特征的随机Shapelet森林算法 Random Shapelet Forest Algorithm Embedded with Canonical Time Series Features 计算机科学, 2022, 49(7): 40-49. https://doi.org/10.11896/jsjkx.210700226
[5]	孙晓寒, 张莉. 基于评分区域子空间的协同过滤推荐算法 Collaborative Filtering Recommendation Algorithm Based on Rating Region Subspace 计算机科学, 2022, 49(7): 50-56. https://doi.org/10.11896/jsjkx.210600062
[6]	刘卫明, 安冉, 毛伊敏. 基于聚类和WOA的并行支持向量机算法 Parallel Support Vector Machine Algorithm Based on Clustering and WOA 计算机科学, 2022, 49(7): 64-72. https://doi.org/10.11896/jsjkx.210500040
[7]	周慧, 施皓晨, 屠要峰, 黄圣君. 基于主动采样的深度鲁棒神经网络学习 Robust Deep Neural Network Learning Based on Active Sampling 计算机科学, 2022, 49(7): 164-169. https://doi.org/10.11896/jsjkx.210600044
[8]	苏丹宁, 曹桂涛, 王燕楠, 王宏, 任赫. 小样本雷达辐射源识别的深度学习方法综述 Survey of Deep Learning for Radar Emitter Identification Based on Small Sample 计算机科学, 2022, 49(7): 226-235. https://doi.org/10.11896/jsjkx.210600138
[9]	于滨, 李学华, 潘春雨, 李娜. 基于深度强化学习的边云协同资源分配算法 Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning 计算机科学, 2022, 49(7): 248-253. https://doi.org/10.11896/jsjkx.210400219
[10]	王宇飞, 陈文. 基于DECORATE集成学习与置信度评估的Tri-training算法 Tri-training Algorithm Based on DECORATE Ensemble Learning and Credibility Assessment 计算机科学, 2022, 49(6): 127-133. https://doi.org/10.11896/jsjkx.211100043
[11]	洪志理, 赖俊, 曹雷, 陈希亮, 徐志雄. 基于遗憾探索的竞争网络强化学习智能推荐方法研究 Study on Intelligent Recommendation Method of Dueling Network Reinforcement Learning Based on Regret Exploration 计算机科学, 2022, 49(6): 149-157. https://doi.org/10.11896/jsjkx.210600226
[12]	陈章辉, 熊贇. 基于解耦-检索-生成的图像风格化描述生成模型 Stylized Image Captioning Model Based on Disentangle-Retrieve-Generate 计算机科学, 2022, 49(6): 180-186. https://doi.org/10.11896/jsjkx.211100129
[13]	徐辉, 康金梦, 张加万. 基于特征感知的数字壁画复原方法 Digital Mural Inpainting Method Based on Feature Perception 计算机科学, 2022, 49(6): 217-223. https://doi.org/10.11896/jsjkx.210500105
[14]	许杰, 祝玉坤, 邢春晓. 机器学习在金融资产定价中的应用研究综述 Application of Machine Learning in Financial Asset Pricing:A Review 计算机科学, 2022, 49(6): 276-286. https://doi.org/10.11896/jsjkx.210900127
[15]	罗俊仁, 张万鹏, 陆丽娜, 陈璟. 即时策略博弈在线对抗规划方法综述 Survey on Online Adversarial Planning for Real-time Strategy Game 计算机科学, 2022, 49(6): 287-296. https://doi.org/10.11896/jsjkx.210600168

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于子空间阈值追踪的矩阵修补算法

Matrix Completion Algorithm Based on Subspace Thresholding Pursuit

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0