Improvement of matrix completion algorithm based on random projection

doi:10.11772/j.issn.1001-9081.2014.06.1587

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (6): 1587-1590.DOI: 10.11772/j.issn.1001-9081.2014.06.1587

Previous Articles Next Articles

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

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

王萍,蔡思佳,刘宇

天津大学理学院,天津 300072

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

Abstract

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.

摘要：

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

CLC Number:

TP391.41

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.

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

References

[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]	. Pavement defect detection algorithm with enhanced morphological perception [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	. Data augmentation method for abnormal passenger behavior in elevators based on dynamic graph convolutional network [J]. Journal of Computer Applications, 0, (): 0-0.
[3]	. Text-based person retrieval method based on multi-granularity shared semantic center association [J]. Journal of Computer Applications, 0, (): 0-0.
[4]	. Image Caption Method Based on Swin-Transformer and Multi-Scale Feature Fusion [J]. Journal of Computer Applications, 0, (): 0-0.
[5]	Keyi FU, Gaocai WANG, Man WU. Few-shot object detection method based on improved region proposal network and feature aggregation [J]. Journal of Computer Applications, 2024, 44(12): 3790-3797.
[6]	Yudong PANG, Zhixing LI, Weijie LIU, Tianhao LI, Ningning WANG. Small target detection model in overlooking scenes on tower cranes based on improved real-time detection Transformer [J]. Journal of Computer Applications, 2024, 44(12): 3922-3929.
[7]	Xin ZHAO, Xinjie LI, Jian XU, Buyun LIU, Xiang BI. Parallel medical image registration model based on convolutional neural network and Transformer [J]. Journal of Computer Applications, 2024, 44(12): 3915-3921.
[8]	. 3D object detection algorithm based on multiscale network with axial attention [J]. Journal of Computer Applications, 0, (): 0-0.
[9]	. Few-shot skin image classification model based on spatial transformation and feature distribution calibration [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Multi-target detection algorithm for traffic intersection images based on YOLOv9 [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	. Semi-supervised object detection framework guided by self-paced learning#br# [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	Yaobin ZOU, Bin ZHANG. Automatic thresholding method guided by maximizing four-directional weighted Shannon entropy [J]. Journal of Computer Applications, 2024, 44(11): 3565-3573.
[13]	Tao LIU, Shihong JU, Yimeng GAO. Small object detection algorithm from drone perspective based on improved YOLOv8n [J]. Journal of Computer Applications, 2024, 44(11): 3603-3609.
[14]	Yusheng LIU, Xuezhong XIAO. High-fidelity image editing based on fine-tuning of diffusion model [J]. Journal of Computer Applications, 2024, 44(11): 3574-3580.
[15]	Lihua HU, Xiaoping LI, Jianhua HU, Sulan ZHANG. Multi-view stereo method based on quadtree prior assistance [J]. Journal of Computer Applications, 2024, 44(11): 3556-3564.

Improvement of matrix completion algorithm based on random projection

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics