基于随机化技术的低秩矩阵分解方法

Low-Rank Matrix Factorization Methods Based on Randomization Technique

摘要

针对传统低秩矩阵分解方法处理大规模数据时,普遍存在运算效率低、内存资源消耗过高、分解精度不足的问题,基于CUR分解核心理论,结合随机采样和优化策略,提出列随机分解、列-行随机分解两种新的随机低秩矩阵分解方法.通过优化算法随机性设计,引入专项优化迭代策略,有效改良了传统算法的运算缺陷.对比实验结果表明,两种方法相较于传统分解方法,具有更优的计算效率、更快的收敛速度,同时抗噪声鲁棒性显著提升,有效完善了大规模数据低秩分解的技术体系,为海量数据处理提供了高效、稳定的新方案,也为机器学习、数据挖掘等相关领域的工程应用提供了可靠的技术支撑.

Abstract

Aiming at the problems that the traditional low-rank matrix factorization methods commonly suffered from low computational efficiency, excessive memory consumption, and insufficient decomposition accuracy when handling large-scale data, based on the core theory of CUR decomposition, combined with random sampling and optimization strategies, we proposed two new random low-rank matrix factorization methods: column random factorization and column-row random factorization. By optimizing the algorithmic randomness design, we introduced dedicated iterative optimization strategies, effectively improving the operational deficiencies of traditional algorithms. The comparative experimental results show that, compared with traditional decomposition methods, the two proposed methods have superior computational efficiency, faster convergence speed, and significantly enhanced noise robustness. They effectively refine the technical framework of low-rank decomposition for large-scale data, provide efficient and stable new solution for massive data processing, as well as reliable technical support for engineering applications in related fields such as machine learning and data mining.

关键词

低秩矩阵分解 / 随机低秩分解 / CUR分解

Key words

low-rank matrix factorization / random low-rank factorization / CUR decomposition

参考文献

[1] 杜世强, 石玉清, 马明, 等. L_3/2正则化图非负矩阵分解算法[J]. 吉林大学学报(理学版), 2014, 52(5):1007-1013.

[2] (Du S Q, Shi Y Q, Ma M, et al. L_3/2 Regularized Graph Non-negative Matrix Factorization[J]. Journal of Jilin University (Science Edition), 2014, 52(5): 1007-1013.)

[3] Syed F I, Muther T, Dahaghi A K, et al. Low-Rank Tensors Applications for Dimensionality Reduction of Complex Hydrocarbon Reservoirs[J]. Energy, 2022, 244: 122680-1-122680-13.

[4] Wang R, Yu L J, Fang H T, et al. Cyclic Correlation Density Decomposition Based on a Sparse and Low-Rank Model for Weak Fault Feature Extraction of Rolling Bearings[J]. Measurement, 2022, 198: 111393-1-111393-17.

[5] Halko N, Martinsson P G, Tropp J A. Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions[J]. SIAM Review, 2011, 53(2): 217-288.

[6] Yang Z R, Hao T L, Dikmen O, et al. Clustering by Nonnegative Matrix Factorization Using Graph Random Walk[J]. Advances in Neural Information Processing Systems, 2012, 25: 1-9.

[7] Hamm K, Huang L. Perspectives on CUR Decompositions[J]. Applied and Computational Harmonic Analysis, 2020, 48(3): 1088-1099.

[8] Cai H Q, Hamm K, Huang L, et al. Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation[J]. IEEE Signal Processing Letters, 2020, 28: 116-120.

[9] Cai H Q, Hamm K, Huang L, et al. Robust CUR Decomposition: Theory and Imaging Applications[J]. SIAM Journal on Imaging Sciences, 2021, 14(4): 1472-1503.

[10] Drineas P, Mahoney M W, Muthukrishnan S. Relative-Error CUR Matrix Decompositions[J]. SIAM Journal on Matrix Analysis and Applications, 2008, 30(2): 844-881.

[11] Kannan R, Vempala S. Randomized Algorithms in Numerical Linear Algebra[J]. Acta Numerica, 2017, 26: 95-135.

[12] El Alaoui A, Mahoney M W. Fast Randomized Kernel Methods with Statistical Guarantees [EB/OL]. (2014-11-02)[2025-02-01]. https://arxiv.org/abs/1411.0306.

[13] 袁柳洋, 汪大为, 贾世会, 等. 一种新的广义鲁棒主成分分析模型及其图像去噪应用[J]. 系统科学与数学, 2024, 44(12):3511-3523.

[14] (Yuan L Y, Wang D W, Jia S H, et al. A New Generalized Robust Principal Component Analysis Model and Its Application to Image Denoising[J]. Journal of Systems Science and Mathematical Sciences, 2024, 44(12): 3511-3523.)

[15] Joukovsky B, Eldar Y C, Deligiannis N. Interpretable Neural Networks for Video Separation: Deep Unfolding RPCA with Foreground Masking[J]. IEEE Transactions on Image Processing, 2023, 33: 108-122.

[16] Wang J, Zhu L, Dai T, et al. Low-Rank and Sparse Matrix Factorization with Prior Relations for Recommender Systems[J]. Applied Intelligence, 2021, 51: 3435-3449.

[17] Cai H Q, Liu J, Yin W. Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection[J]. Advances in Neural Information Processing Systems, 2021, 34: 16977-16989.

[18] Tong T, Ma C, Chi Y J. Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent[J]. Journal of Machine Learning Research, 2021, 22(150): 1-63.

[19] Liu H Y, Foygel B R. Between Hard and Soft Thresholding: Optimal Iterative Thresholding Algorithms[J]. Information and Inference: A Journal of the IMA, 2020, 9(4): 899-933.

[20] Cai H Q, Cai J F, Wei K. Accelerated Alternating Projections for Robust Principal Component Analysis[J]. Journal of Machine Learning Research, 2019, 20(20): 1-33.

基金资助

国家自然科学基金(62072312)

国家自然科学基金(62372302)