随机低秩逼近算法在推荐系统中的应用

基金项目: 上海工程技术大学大学生创新训练计划资助项目(CX2021008)

Application of randomized low-rank approximation algorithm in recommendation system

a.
School of Mechanical and Automotive Engineering
b.
School of Air Transportation and School of Flying
c.
School of Mathematics, Physics and Statistics, Shanghai University of Engineering Science, Shanghai 201620, China

摘要: 针对推荐系统中数据量越来越大，其对应的矩阵填充问题算法效率有待提升. 基于随机算法策略以及高效数据访问要求，提出一种新的求解矩阵填充问题的算法，并借助Matlab软件实现该算法. 数值试验结果表明，该算法在效率上可提升30%左右.
- 奇异值分解 /
- 随机算法 /
- 低秩逼近 /
- 推荐系统
Abstract: In view of the problem that with increasing large amount of datas in a recommendation system, the computing efficiency of its corresponding matrix completion algorithms need to be improved. Based on randomized algorithm strategy and efficient data access requirements, a new algorithm for solving matrix completion problem was proposed, and the Matlab software was employed to realize the algorithm. The numerical experiment result shows that the new algorithm can speed up the computing efficiency of original one by about 30%.
- singular value decomposition (SVD) /
- randomized algorithm /
- low-rank approximation /
- recommendation system

表 1 矩阵填充问题的比较

Table 1. Comparison of matrix completion problems

下载: 导出CSV

[1]	王越, 程昌正. 协同过滤算法在电影推荐中的应用[J] . 兵器装备工程学报,2014(5):86 − 88.
[2]	王元涛. Netflix数据集上的协同过滤算法[D]. 北京: 清华大学, 2009.
[3]	冯栩, 李可欣, 喻文健, 等. 基于随机奇异值分解的快速矩阵补全算法及其应用[J] . 计算机辅助设计与图形学学报,2017(12):2343 − 2348.
[4]	FENG Y H, XIAO J W, GU M. Flip-flop spectrum-revealing QR Factorization and its applications on singular value decomposition[J] . Electronic Transactions on Numerical Analysis,2019,51:469 − 494.
[5]	LARSEN R M. Lanczos bidiagonalization with partial reorthogonalization[J] . DAIMI Report Series,1999,27(537):1 − 101. doi: 10.7146/dpb.v27i537.7070
[6]	DRINEAS P, KANNAN R, MAHONEY M W. Fast Monte Carlo algorithms for matrices II: computing a low-rank approximation to a matrix[J] . SIAM Journal on Computing,2006,36(1):158 − 183. doi: 10.1137/S0097539704442696
[7]	TROPP J A, YURTSEVER A, UDELL M, et al. Practical sketching algorithms for low-rank matrix approximation[J] . SIAM Journal on Matrix Analysis and Applications,2017,38(4):1454 − 1485. doi: 10.1137/17M1111590
[8]	LIN Z C, CHEN M M, MA Y. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[EB/OL]. (2013-10-18)[2021-01-18]. http://arxiv.org/pdf/1009.5055v3.pdf.