关于Kaczmarz的一类加速免伪逆贪婪块方法
Accelerated Pseudo-Inverse-Free Greedy Block Methods in the Kaczmarz Algorithm Category
摘要: 块贪婪Kaczmarz方法在解决大规模一致线性系统方面取得了成功应用。然而在每次迭代步骤中，GBK方法都涉及伪逆计算，这不仅复杂化了计算并减慢了收敛速度，且不适合分布式实现。在本文中基于Sketching技术提出了两种免伪逆计算的GBK方法，分别是杠杆得分抽样免伪逆GBK方法和稀疏随机投影免伪逆GBK方法，其算法效率更加高效，收敛速度可以达到指数收敛。为了进一步加快收敛速度，我们还提出了CountSketch免伪逆重力球GBK方法、杠杆得分抽样免伪逆重力球GBK方法和稀疏随机投影免伪逆重力球GBK方法。为了验证新方法的有效性，我们进行了一些数值示例。结果表明，这些新方法在解决大规模一致线性系统方面具有很高的效率和准确性。
Abstract: The Greedy Block Kaczmarz (GBK) method has been successfully applied in solving large-scale con-sistent linear systems. However, each iteration of the GBK method involves the computation of pseudoinverses, which complicates the process, slows down convergence, and is ill-suited for dis-tributed implementations. In this paper, we introduce two free pseudoinverse GBK methods based on Sketching techniques: the Leverage Score Sampling Free Pseudoinverse GBK method and the Sparse Random Projection Free Pseudoinverse GBK method. These algorithms exhibit higher effi-ciency and can achieve exponential rates of convergence. To further accelerate convergence, we also propose the Count Sketch Free Pseudoinverse Heavy Ball GBK method, the Leverage Score Sampling Free Pseudoinverse Heavy Ball GBK method, and the Sparse Random Projection Free Pseudoinverse Heavy Ball GBK method. The effectiveness of these new methods is demonstrated through several numerical examples, showing that they are highly efficient and accurate in addressing large-scale consistent linear systems.
文章引用：颜鑫鹏, 时文雅, 郇战. 关于Kaczmarz的一类加速免伪逆贪婪块方法[J]. 应用数学进展, 2024, 13(1): 466-484. https://doi.org/10.12677/AAM.2024.131046

参考文献

[1] Byrne, C. (2003) A Unified Treatment of Some Iterative Algorithms in Signal Processing and Image Reconstruction. In-verse Problems, 20, 103-120. [Google Scholar] [CrossRef] 
[2] Chung, J., Chung, M., Slagel, J.T., et al. (2020) Sampled Limited Memory Methods for Massive Linear Inverse Problems. Inverse Problems, 36, Article ID: 054001. [Google Scholar] [CrossRef] 
[3] Leskovec, J., Rajaraman, A. and Ullman, J.D. (2020) Mining of Massive Data Sets. Cambridge University Press, Cambridge. [Google Scholar] [CrossRef] 
[4] Herman, G.T. and Davidi, R. (2008) Image Reconstruction from a Small Number of Projections. Inverse Problems, 24, Article ID: 045011. [Google Scholar] [CrossRef] [PubMed]
[5] Lyu, H., Sha, N., Qin, S., et al. (2019) Advances in Neural Information Processing Systems.
[6] Kaczmarz, S. (1937) Angenäherte Auflösung von Systemen Linearer Glei-chungen. Bulletin L’Académie Polonaise des Science, 35, 355-357.
[7] Deutsch, F. and Hundal, H. (1997) The Rate of Convergence for the Method of Alternating Projections, II. Journal of Mathematical Analysis and Applications, 205, 381-405. [Google Scholar] [CrossRef] 
[8] Galántai, A. (2005) On the Rate of Convergence of the Al-ternating Projection Method in Finite Dimensional Spaces. Journal of Mathematical Analysis and Applications, 310, 30-44. [Google Scholar] [CrossRef] 
[9] Strohmer, T. and Vershynin, R. (2009) A Randomized Ka-czmarz Algorithm with Exponential Convergence. Journal of Fourier Analysis and Applications, 15, 262-278. [Google Scholar] [CrossRef] 
[10] Needell, D. (2010) Randomized Kaczmarz Solver for Noisy Line-ar Systems. BIT Numerical Mathematics, 50, 395-403. [Google Scholar] [CrossRef] 
[11] Gower, R.M. and Richtárik, P. (2015) Randomized Iterative Methods for Linear Systems. SIAM Journal on Matrix Analysis and Applications, 36, 1660-1690. [Google Scholar] [CrossRef] 
[12] Ma, A., Needell, D. and Ramdas, A. (2015) Convergence Properties of the Randomized Extended Gauss—Seidel and Kaczmarz Methods. SIAM Journal on Matrix Analysis and Applications, 36, 1590-1604. [Google Scholar] [CrossRef] 
[13] Richtárik, P. and Takác, M. (2017) Stochastic Reformulations of Linear Systems: Accelerated Method.
[14] Liu, J. and Wright, S. (2016) An Accelerated Randomized Kaczmarz Algorithm. Mathematics of Computation, 85, 153-178. [Google Scholar] [CrossRef] 
[15] Bai, Z.-Z. and Wu, W.-T. (2018) On Relaxed Greedy Randomized Kaczmarz Methods for Solving Large Sparse Linear Systems. Applied Mathe-matics Letters, 83, 21-26. [Google Scholar] [CrossRef] 
[16] Zhang, J. and Guo, J. (2020) On Relaxed Greedy Randomized Coordinate Descent Methods for Solving Large Linear Least-Squares Problems. Applied Numerical Mathematics, 157, 372-384. [Google Scholar] [CrossRef] 
[17] Bai, Z.-Z. and Wu, W.-T. (2018) On Greedy Randomized Kaczmarz Method for Solving Large Sparse Linear Systems. SIAM Journal on Scientific Com-puting, 40, A592-A606. [Google Scholar] [CrossRef] 
[18] Du, K. and Gao, H. (2019) A New Theoretical Estimate for the Convergence Rate of the Maximal Weighted Residual Kaczmarz Algorithm. Numerical Mathematics: Theory, Methods and Applications, 12, 627-639. [Google Scholar] [CrossRef] 
[19] Elfving, T. (1980) Block-Iterative Methods for Consistent and Inconsistent Linear Equations. Numerische Mathematik, 35, 1-12. [Google Scholar] [CrossRef] 
[20] Needell, D. and Tropp, J.A. (2014) Paved with Good Intentions: Analy-sis of a Randomized Block Kaczmarz Method. Linear Algebra and Its Applications, 441, 199-221. [Google Scholar] [CrossRef] 
[21] Needell, D., Zhao, R. and Zouzias, A. (2015) Randomized Block Kaczmarz Method with Projection for Solving Least Squares. Linear Algebra and Its Applications, 484, 322-343. [Google Scholar] [CrossRef] 
[22] Niu, Y.-Q. and Zheng, B. (2020) A Greedy Block Kaczmarz Algo-rithm for Solving Large-Scale Linear Systems. Applied Mathematics Letters, 104, Article ID: 106294. [Google Scholar] [CrossRef] 
[23] Rebrova, E. and Needell, D. (2021) On Block Gaussian Sketching for the Kaczmarz Method. Numerical Algorithms, 86, 443-473. [Google Scholar] [CrossRef] 
[24] Necoara, I. (2019) Faster Randomized Block Kaczmarz Algo-rithms. SIAM Journal on Matrix Analysis and Applications, 40, 1425-1452. [Google Scholar] [CrossRef] 
[25] Moorman, J.D., Tu, T.K., Molitor, D., et al. (2021) Randomized Kacz-marz with Averaging. BIT Numerical Mathematics, 61, 337-359. [Google Scholar] [CrossRef] 
[26] Du, K., Si, W.-T. and Sun, X.-H. (2020) Randomized Extended Average Block Kaczmarz for Solving Least Squares. SIAM Journal on Scientific Computing, 42, A3541-A3559. [Google Scholar] [CrossRef] 
[27] Zouzias, A. and Freris, N.M. (2013) Randomized Extended Kaczmarz for Solving Least Squares. SIAM Journal on Matrix Analysis and Applications, 34, 773-793. [Google Scholar] [CrossRef] 
[28] Du, K. and Sun, X.-H. (2020) Pseudoinverse-Free Randomized Block It-erative Algorithms for Consistent and Inconsistent Linear Systems.
[29] 张建华, 郭静慧. 一类快速免伪逆贪婪块KACZMARZ方法[J]. 高等学校计算数学学报, 2022, 44(3): 285-298.
[30] Chen, K., Li, Q., Newton, K., et al. (2020) Structured Random Sketching for PDE Inverse Problems. SIAM Journal on Matrix Analysis and Applications, 41, 1742-1770. [Google Scholar] [CrossRef] 
[31] Pilanci, M. and Wainwright, M.J. (2017) Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence. SIAM Journal on Optimization, 27, 205-245. [Google Scholar] [CrossRef] 
[32] Mor-Yosef, L. and Avron, H. (2019) Sketching for Principal Component Regression. SIAM Journal on Matrix Analysis and Applications, 40, 454-485. [Google Scholar] [CrossRef] 
[33] Yang, Y., Pilanci, M. and Wainwright, M.J. (2017) Randomized Sketches for Kernels: Fast and Optimal Nonparametric Regression. Annals of Statistics, 45, 991-1023. [Google Scholar] [CrossRef] 
[34] Avron, H., Clarkson, K.L. and Woodruff, D.P. (2017) Faster Kernel Ridge Regression Using Sketching and Preconditioning. SIAM Journal on Matrix Analysis and Applications, 38, 1116-1138. [Google Scholar] [CrossRef] 
[35] Woodruff, D.P. (2014) Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends® in Theoretical Computer Science, 10, 1-157. [Google Scholar] [CrossRef] 
[36] Jarman, B., Yaniv, Y. and Needell, D. (2022) Online Signal Recovery via Heavy Ball Kaczmarz. Proceedings of the 2022 56th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, 31 October-2 November 2022, 276-280. [Google Scholar] [CrossRef] 
[37] Zhang, Y. and Li, H. (2021) A Count Sketch Maximal Weighted Residual Kaczmarz Method for Solving Highly Overdetermined Linear Systems. Applied Mathemat-ics and Computation, 410, Article ID: 126486. [Google Scholar] [CrossRef] 
[38] Rudi, A., Calandriello, D., Carratino, L., et al. (2018) On Fast Leverage Score Sampling and Optimal Learning. 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, 3-8 December 2018, 5672-5682.
[39] Cohen, M.B., Musco, C. and Musco, C. (2017) Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling. Proceedings of the 28th Annual ACM-SIAM Sym-posium on Discrete Algorithms, Barcelona, 16-19 January 2017, 1758-1777. [Google Scholar] [CrossRef] 
[40] Ailon, N. and Chazelle, B. (2009) The Fast John-son-Lindenstrauss Transform and Approximate Nearest Neighbors. SIAM Journal on Computing, 39, 302-322. [Google Scholar] [CrossRef] 

为你推荐