一种用于求解高度超定线性系统的计数草图随机平均块Kaczmarz方法
A Count Sketch Randomized Average Block Kaczmarz Method for Solving Highly Overdetermined Linear Systems
摘要: 受计数草图对Kaczmarz方法加速效果的启发，文章将计数草图与随机平均块Kaczmarz方法相结合，得出了一种求解高度超定线性系统的新方法。为了验证新方法的可行性，进行了大量数值实验。数值实验表明，在相同精度下，新方法在计算时间上表现良好。
Abstract: Inspired by the acceleration effect of the count sketch on the Kaczmarz method, this paper combines the count sketch with the randomized average block Kaczmarz method to derive a new method for solving highly overdetermined linear systems. To verify the feasibility of the new method, a large number of numerical experiments were conducted. The numerical experiments show that, under the same precision, the new method performs well in terms of computing time.
文章引用：姜昊辰. 一种用于求解高度超定线性系统的计数草图随机平均块Kaczmarz方法[J]. 应用数学进展, 2025, 14(2): 244-250. https://doi.org/10.12677/aam.2025.142067

参考文献

[1] Karczmarz, S. (1937) Angenaherte Auflosung von Systemen Linearer Gleichungen. Bulletin International de l’Académie Polonaise des Sciences et des Lettres, 35, 355-357.
[2] Popa, C. and Zdunek, R. (2004) Kaczmarz Extended Algorithm for Tomographic Image Reconstruction from Limited-Data. Mathematics and Computers in Simulation, 65, 579-598. [Google Scholar] [CrossRef] 
[3] Abdelazeem, M. and Gobashy, M.M. (2016) A Solution to Unexploded Ordnance Detection Problem from Its Magnetic Anomaly Using Kaczmarz Regularization. Interpretation, 4, SH61-SH69. [Google Scholar] [CrossRef] 
[4] Pasqualetti, F., Carli, R. and Bullo, F. (2012) Distributed Estimation via Iterative Projections with Application to Power Network Monitoring. Automatica, 48, 747-758. [Google Scholar] [CrossRef] 
[5] Elfving, T. (1980) Block-Iterative Methods for Consistent and Inconsistent Linear Equations. Numerische Mathematik, 35, 1-12. [Google Scholar] [CrossRef] 
[6] Woodruff, D.P. (2014) Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends in Theoretical Computer Science, 10, 1-157.
[7] Meng, X. and Mahoney, M.W. (2013) Low-Distortion Subspace Embeddings in Input-Sparsity Time and Applications to Robust Linear Regression. Proceedings of the Forty-Fifth annual ACM symposium on Theory of Computing, Palo Alto, 2-4 June 2013, 91-100. [Google Scholar] [CrossRef] 
[8] Zhang, Y. and Li, H. (2021) A Count Sketch Maximal Weighted Residual Kaczmarz Method for Solving Highly Overdetermined Linear Systems. Applied Mathematics and Computation, 410, Article ID: 126486. [Google Scholar] [CrossRef] 
[9] Necoara, I. (2019) Faster Randomized Block Kaczmarz Algorithms. SIAM Journal on Matrix Analysis and Applications, 40, 1425-1452. [Google Scholar] [CrossRef] 
[10] Needell, D. and Tropp, J.A. (2014) Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method. Linear Algebra and its Applications, 441, 199-221. [Google Scholar] [CrossRef] 

为你推荐