基于随机投影技术的矩阵填充算法的改进

doi:10.11772/j.issn.1001-9081.2014.06.1587

计算机应用 ›› 2014, Vol. 34 ›› Issue (6): 1587-1590.DOI: 10.11772/j.issn.1001-9081.2014.06.1587

基于随机投影技术的矩阵填充算法的改进

王萍,蔡思佳,刘宇

天津大学理学院,天津 300072

收稿日期:2013-12-06 修回日期:2014-01-23 发布日期:2014-07-02 出版日期:2014-06-01
通讯作者: 王萍
作者简介:王萍(1967-),女,辽宁海城人,教授,博士,CCF会员,主要研究方向: 图像处理、模式识别;蔡思佳(1988-),男,湖南常德人,硕士研究生,主要研究方向: 图像处理;刘宇(1990-),男,河北保定人,主要研究方向: 图像处理。
基金资助:
重庆市科委基础与前沿研究项目

Improvement of matrix completion algorithm based on random projection

WANG Ping,CAI Sijia,LIU Yu

School of Science, Tianjin University, Tianjin 300072, China

Received:2013-12-06 Revised:2014-01-23 Online:2014-07-02 Published:2014-06-01
Contact: WANG Ping
Supported by:
National Natural Science Foundation

摘要/Abstract

摘要：

利用随机投影加速技术将高维矩阵的奇异值分解(SVD)投影到一个低维子空间上进行,可以减少SVD消耗的时间。定义了奇异值随机投影压缩算子,取代之前的奇异值压缩算子,并用这个算子改进了定点连续(FPC)算法得到FPCrp算法。对改进前后的算法进行了大量实验,结果表明:随机投影技术能够在保持算法鲁棒性和精度的同时,节省50%以上的时间。因此,基于随机投影技术的矩阵填充算法更适合求解大规模问题。

Abstract:

Using random projection acceleration technology to project the Singular Value Decomposition (SVD) of higher dimensional matrices onto a lower subspace can reduce the time consumption of SVD. The singular value random projection compression operator was defined to replace the singular value compression operator, then it was used to improve the Fixed Point Continuation (FPC) algorithm and got FPCrp algorithm. Lots of experiments were conducted on the original algorithm and the improved one. The results show that the random projection technology can reduce more than 50% time consumption of the FPC algorithm, while maintaining its robustness and precision. The modified matrix completion algorithm based on random projection technology is effective in solving large scale problems.

中图分类号:

TP391.41

王萍蔡思佳刘宇. 基于随机投影技术的矩阵填充算法的改进[J]. 计算机应用, 2014, 34(6): 1587-1590.

WANG Ping CAI Sijia LIU Yu. Improvement of matrix completion algorithm based on random projection[J]. Journal of Computer Applications, 2014, 34(6): 1587-1590.

参考文献

[1]FAZEL M, HINDI H, BOYD S. A rank minimization heuristic with application to minimum order system approximation[C]// Proceedings of the 2001 American Control Conference. Evanston, IL:American Automatic Control Council, 2001,6:4734-4739.
[2]LINIAL N, LONDON E, RABINOVICH Y. The geometry of graphs and some of its algorithmic applications[J]. Combinatorica, 1995, 15(2):215-245.
[3]CANDS E, RECHT B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9(6):717-772.
[4]CAI J, CANDS E, SHEN Z. A singular value thresholding algorithm for matrix completion[J].SIAM Journal on Optimization, 2010, 20(4):1956-1982.
[5]MA S, GOLDFARB D, CHEN L. Fixed point and Bregman iterative methods for matrix rank minimization[J]. Mathematical Programming, 2011, 128(1):321-353.
[6]LIN Z, GANESH A, WRIGHT J, et al. Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix[EB/OL].[2012-03-25].http://yima.csl.uiuc.edu/psfile/rpca algorithms.pdf.
[7]CHEN C, HE B, YUAN X. Matrix completion via an alternating direction method[J]. IMA Journal of Numerical Analysis, 2012, 32(1):227-245.
[8]LEWIS A. The mathematics of eigenvalue optimization[J]. Mathematical Programming, 2003, 97(1):155-176.
[9]WATSON G. Characterization of the subdifferential of some matrix norms[J]. Linear Algebra and its Applications, 1992, 170:33-45.
[10]BECK A, TEBOULLE M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(1):183-202.
[11]WRIGHT J, GANESH A, RAO S, et al. Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization[EB/OL].[2012-04-12].http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/robust pca.pdf.
[12]NESTEROV Y. A method of solving a convex programming problem with convergence rate O(1/k2)[C]// Soviet Mathematics Doklady. Providence: American Mathematical Society,1983,27:372-376.
[13]VEMPALA S. The random projection method[M]. Providence: American Mathematical Society,2004:1-6.

[1]	张佳慧李晓明张嘉祥. 强化形态感知的路面缺陷检测算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	况世雄姚俊波陆佳炜王琪冰肖刚. 基于动态图卷积网络的电梯乘客异常行为数据增强方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[3]	康斌陈斌王俊杰李昱林赵军智咸伟志. 基于多粒度共享语义中心关联的文本到人物检索方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[4]	王子怡李卫军刘雪洋丁建平刘世侠苏易礌. 基于Swin Transformer与多尺度特征融合的图像描述方法#br# [J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	付可意, 王高才, 邬满. 基于改进区域提议网络和特征聚合小样本目标检测方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3790-3797.
[6]	庞玉东, 李志星, 刘伟杰, 李天昊, 王宁宁. 基于改进实时检测Transformer的塔机上俯视场景小目标检测模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3922-3929.
[7]	赵欣, 李鑫杰, 徐健, 刘步云, 毕祥. 基于卷积神经网络与Transformer并行的医学图像配准模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3915-3921.
[8]	颜承志陈颖钟凯高寒. 基于多尺度网络与轴向注意力的3D目标检测算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[9]	王静刘嘉星宋婉莹薛嘉兴丁温欣. 基于空间变换和特征分布校准的小样本皮肤图像分类模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	廖炎华鄢元霞潘文林. 基于YOLOv9的交通路口图像的多目标检测算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	谢斌红剌颖坤张英俊张睿. 自步学习指导下的半监督目标检测框架[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	邹耀斌, 张彬. 四向加权香农熵最大化导向的自动阈值分割方法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3565-3573.
[13]	刘涛, 鞠事宏, 高一萌. 基于改进YOLOv8n的无人机视角下小目标检测算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3603-3609.
[14]	刘雨生, 肖学中. 基于扩散模型微调的高保真图像编辑[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3574-3580.
[15]	胡立华, 李小平, 胡建华, 张素兰. 基于四叉树先验辅助的多视图立体方法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3556-3564.

基于随机投影技术的矩阵填充算法的改进

Improvement of matrix completion algorithm based on random projection

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics