|
|
Pure Mathematics 2024
Cholesky分解的单Pass随机算法
|
Abstract:
对于大规模数据矩阵，数据的读取成本远高于算法本身的成本；对存储在磁盘外部的流型数据，往往只有一次读取数据的机会。而以往的Cholesky分解的随机算法都至少需要读取输入数据两次，难以满足实际应用中的低成本需求。本文基于矩阵分解的单pass随机算法研究，提出了Cholesky分解的单pass随机算法，并给出了该算法的误差上界，最后通过数值实验验证了该算法的可行性以及有效性。
For large-scale data matrices, the cost of data reading is much higher than the cost of algorithms. For streaming data stored outside the disk, there is only one chance to read the data. In the past, the randomized algorithm of Cholesky decomposition needed to read the original data at least twice, which was difficult to meet the low-cost requirements in practical applications. Based on the research of single-pass randomized algorithm with matrix decomposition, a single-pass randomized algorithm based on Cholesky decomposition is proposed, and the error upper bound of the algorithm is given, and finally the feasibility and effectiveness of the algorithm are verified by numerical experiments.
| [1] | 李庆扬, 王能超, 易大义. 数值分析[M]. 第5版. 武汉: 华中科技大学出版社, 2018. |
| [2] | Higham, N.J. (2002) Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9780898718027 |
| [3] | Gu, M. and Miranian, L. (2004) Strong Rank Revealing Cholesky Factorization. Electronic Transactions on Numerical Analysis, 17, 76-92. |
| [4] | Xiao, J.W. and Gu, M. (2016) Spec-trum-Revealing Cholesky Factorization for Kernel Methods. Proceedings of the 16th IEEE International Conference on Data Mining, Barcelona, 12-15 December 2016, 1293-1298.
https://doi.org/10.1109/ICDM.2016.0175 |
| [5] | Li, H. and Yin, S. (2020) Single-Pass Randomized Algorithms for LU Decomposition. Linear Algebra and Its Applications, 595, 101-122. https://doi.org/10.1016/j.laa.2020.03.001 |
| [6] | Halko, N., Martinsson, P.G. and Tropp, J.A. (2011) Finding Structure with Randomness: Probabilities Algorithms for Constructing Approximate Matrix Decompositions. SIAM Review, 53, 217-288. https://doi.org/10.1137/090771806 |
| [7] | Tropp, J.A., Yurtsever, A., Udell, M. et al. (2018) More Practical Skeching Algorithms for Low-Rank Matrix Approximation. Statistics Department, Caltech, Pasade-na. |
| [8] | Tropp, J.A., Yurtsever, A., Udell, M. et al. (2019) Streaming Low-Rank Matrix Approximation with an Ap-plication to Scientific Simulation. SIAM Journal on Scientific Computing, 41, A2430-A2463. https://doi.org/10.1137/18M1201068 |
| [9] | Litvak, A.E., Pajor, A. and Rudelson, M. (2005) Smallest Singular Value of Random Matrices and Geometry of Random Polytopes. Advances in Mathematics, 195, 491-523. https://doi.org/10.1016/j.aim.2004.08.004 |
| [10] | Shabat, G., Shmueli, Y., Aizenbud, Y., et al. (2018) Randomized LU Decomposition. Applied and Computational Harmonic Analysis, 44, 246-272. https://doi.org/10.1016/j.acha.2016.04.006 |
| [11] | Gu, M. (2015) Subspace Iteration Randomization and Singular Value Problems. SIAM Journal on Scientific Computing, 37, A1139-A1173. https://doi.org/10.1137/130938700 |
