Motivated by the count sketch maximal weighted residual Kaczmarz (CS-MWRK) method presented by Zhang and Li (Appl. Math. Comput., 410, 126486), we combine the count sketch tech with the maximal weighted residual Kaczmarz Method with Oblique Projection (MWRKO) constructed by Wang, Li, Bao and Liu (arXiv: 2106.13606) to develop a new method for solving highly overdetermined linear systems. The convergence rate of the new method is analyzed. Numerical results demonstrate that our method performs better in computing time compared with the CS-MWRK and MWRKO methods.
KeywordsCount SketchOblique ProjectionKaczmarz MethodLinear System
Strohmer, T. and Vershynin, R. (2009) A Randomized Kaczmarz Algorithm with Exponential Convergence. Journal of Fourier Analysis and Applications, 15, Article No. 262. https://doi.org/10.1007/s00041-008-9030-4
Niu, Y.Q. and Zheng, B. (2020) A Greedy Block Kaczmarz Algorithm for Solving Large-Scale Linear Systems. Applied Mathematics Letters, 104, Article ID: 106294. https://doi.org/10.1016/j.aml.2020.106294
Nutini, J., Sepehry, B., Laradji, I., Schmidt, M., Koepke, H. and Virani, A. (2016) Convergence Rates for Greedy Kaczmarz Algorithms, and Faster Randomized Kaczmarz Rules Using the Orthogonality Graph. arXiv:1612.07838.
Eldar, Y. and Needell, D. (2011) Acceleration of Randomized Kaczmarz Method via the Johnson-Lindenstrauss Lemma. Numerical Algorithms, 58, 163-177. https://doi.org/10.1007/s11075-011-9451-z
Eggermont, P.P.B., Herman, G.T. and Lent, A. (1981) Iterative Algorithms for Large Partitioned Linear Systems, with Applications to Image Reconstruction. Linear Algebra and Its Applications, 40, 37-67. https://doi.org/10.1016/0024-3795(81)90139-7
Elble, J.M., Sahinidis, N.V. and Vouzis, P. (2010) GPU Computing with Kaczmarz’s and Other Iterative Algorithms for Linear Systems. Parallel Computing, 36, 215-231. https://doi.org/10.1016/j.parco.2009.12.003
Lorenz, D.A., Wenger, S., Schopfer, F. and Magnör, M. (2014) A Sparse Kaczmarz Solver and a Linearized Bregman Method for Online Compressed Sensing. 2014 IEEE International Conference on Image Processing, Paris, 27-30 October 2014, 1347-1351. https://doi.org/10.1109/ICIP.2014.7025269
McCormick, S.F. (1977) The Methods of Kaczmarz and Row Orthogonalization for Solving Linear Equations and Least Squares Problems in Hilbert Space. Indiana University Mathematics Journal, 26, 1137-1150. https://doi.org/10.1512/iumj.1977.26.26090
Bai, B.Z. and Wu, W.T. (2018) On Greedy Randomized Kaczmarz Method for Solving Large Sparse Linear Systems. SIAM Journal on Scientific Computing, 40, A592-A605. https://doi.org/10.1137/17M1137747
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. https://doi.org/10.4208/nmtma.OA-2018-0039
Boutsidis, C., Drineas, P. and Magdon-Ismail, M. (2014) Near-Optimal Column-Based Matrix Reconstruction. SIAM Journal on Computing, 43, 687-717. https://doi.org/10.1137/12086755X
Woodruff, D.P. (2014) Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends in Theoretical Computer Science, 10, 1-157.
Charikar, M., Chen, K. and Farach-Colton, M. (2002) Finding Frequent Items in Data Streams. International Colloquium on Automata, Languages, and Programming 2002, Málaga, 8-13 July 2002, 693-703. https://doi.org/10.1007/3-540-45465-9_59
Thorup, M. and Zhang, Y. (2012) Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation. SIAM Journal on Computing, 41, 293-331. https://doi.org/10.1137/100800774
Zhang, Y.J. and Li, H.Y. (2021) A Count Sketch Maximal Weighted Residual Kaczmarz Method for Solving Highly Overdetermined Liner Systems. Applied Mathematics and Computation, 410, Article ID: 126486. https://doi.org/10.1016/j.amc.2021.126486
Clarkson, K.L. and Woodruff, D.P. (2017) Low-Rank Approximation and Regression in Input Sparsity Time. Journal of the ACM, 63, Article No. 54. https://doi.org/10.1145/3019134
Wu, N.C. and Xiang, H. (2021) Semiconvergence Analysis of the Randomzied Row Iterative Method and Its Extended Variants. Numerical Linear Algebra with Applications, 28, Article No. e2334. https://doi.org/10.1002/nla.2334
Gower, R.M., Molitor, D., Moorman, J. and Needell, D. (2021) On Adaptive Sketch-and-Projection for Solving Linear Systems. SIAM Journal on Matrix Analysis and Applications, 42, 954-989. https://doi.org/10.1137/19M1285846
Gower, R.M. and Richtárik, P. (2015) Randomized Iterative Methods for Linear Systems. SIAM Journal on Matrix Analysis and Applications, 36, 1660-1690. https://doi.org/10.1137/15M1025487
Li, W.G., Wang, Q.F., Bao, W.B. and Liu, L. (2021) On Kaczmarz Methods with Oblique Projection for Solving Large Overdetermined Lienar Systems. arXiv: 2106.13368.
Popa, C., Preclik, T., Köstler, H. and Rüde, U. (2012) On Kaczmarz’s Projection Iteration as a Direct Solver for Linear Least Squares Problems. Linear Algebra and its Applications, 436, 389-404. https://doi.org/10.1016/j.laa.2011.02.017
Popa, C. (2012) Projection algorithms Classical Results and Developments. Lap Lambert Academic Publishing, Saarbrücken.
Wang, F., Li, W.G., Bao, W.B. and Liu, L. (2021) Greedy Randomzied and Maximal Weighted Residual Kaczmarz Methods with Oblique Projection, arXiv: 2106.13606.
Zhang, J.H. and Guo, J.H. (2020) On Relaxed Greedy Randomized Coordinate Descent Methods for Solving Large Linear Least-Squares Problems. Applied Numerical Mathematics, 157, 372-384. https://doi.org/10.1016/j.apnum.2020.06.014
Davis, T.A. and Hu, Y. (2011) The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38, Article No. 1. https://doi.org/10.1007/s11075-021-01104-x
Wu, W.T. (2021) On Two-Subspace Randomized Extended Kaczmarz Method for Solving Large Linear Least-Squares Problems. Numerical Algorithms, 89, 1-31. https://doi.org/10.1007/s11075-021-01104-x
Needell, D. and Ward, R. (2013) Two-Subspace Projection Method for Coherent Overdetermined Systems. Journal of Fourier Analysis and Applications, 19, 256-269. https://doi.org/10.1007/s00041-012-9248-z
Chen, J.Q. and Huang, Z.D. (2022) On a Fast Deterministic Block Kaczmarz Method for Solving Large-Scale Linear Systems. Numerical Algorithms, 89, 1007-1029. https://doi.org/10.1007/s11075-021-01143-4
Necoara, I. (2019) Faster Randomzied Block Kaczmarz Algorithms. SIAM Journal on Matrix Analysis and Applications, 40, 1425-1452. https://doi.org/10.1137/19M1251643
Du, K., Si, W.T. and Sun, X.H. (2020) Randomized Extended Average Block Kaczmarz for Solving Least Squares. SIAM Journal on Matrix Analysis and Applications, 42, A3541-A3559. https://doi.org/10.1137/20M1312629
Li, W., Yin, F., Liao, Y.M. and Huang, G.X. (2021) A Geometric Gaussian Kaczmarz Method for Large Scaled Consistent Linear Equations. Journal of Applied Mathematics and Physics, 9, 2954-2665. https://doi.org/10.4236/jamp.2021.911189
Liao, Y., Yin, F. and Huang, G.X. (2021) A Relaxed Greedy Block Kaczmarz Method for Solving Large Consistent Linear Systems. Journal of Applied Mathematics and Physics, 9, 3032-3044. https://doi.org/10.4236/jamp.2021.912196