[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Efficient randomized block Kaczmarz method for linear feasibility

  • Published:
Calcolo Aims and scope Submit manuscript

Abstract

The randomized Kaczmarz and Motzkin algorithms are commonly employed as iterative techniques for solving systems of linear inequalities in the form of \(Ax\le b\). Briskman and Needell (J Math Imaging Vis 52:385–396, 2015) extended the randomized block Kaczmarz algorithm to handle systems of mixed equalities and inequalities. In this paper, we introduce a family of average block Kaczmarz algorithms that leverage a subset of the constraints at each step and employ an adaptive stepsize to efficiently solve systems of linear inequalities. Unlike the block Kaczmarz method proposed by Briskman and Needell, our algorithms possess the advantageous property of linear convergence to a solution for a given system of linear inequalities, without the necessity of computing pseudoinverse matrices. Moreover, the parallel implementation of our algorithm provides additional acceleration, making it well-suited to tackle real-world problems involving large-scale systems of linear inequalities. Numerical experiments conducted using randomly generated and real-world test instances, including classification with support vector machines and Netlib LP, confirm the efficiency of our proposed algorithm, which significantly reduces the required computational time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Data availability

No data was used for the research described in the article.

References

  1. Herman, G.T., Lent, A.: Iterative reconstruction algorithms. Comput. Biol. Med. 6(4), 273–294 (1976)

    Article  Google Scholar 

  2. Khachiyan, L.G.: On the exact solution of systems of linear inequalities and linear programming problems. USSR Comput. Math. Math. Phys. 22(4), 239–242 (1982)

    Article  Google Scholar 

  3. Cichocki, A., Ramirez-Angulo, J., Unbehauen, R.: Architectures for analog VLSI implementation of neural networks for solving linear equations with inequality constraints. In: Proceedings of IEEE International Symposium Circuits and Systems, vol. 3, pp. 1529–1532 (1992)

  4. Xia, Y., Wang, J., Hung, D.L.: Recurrent neural networks for solving linear inequalities and equations. IEEE Trans. Circuits Syst. I Fundam. Theory Appl. 46(4), 452–462 (1999)

    Article  MathSciNet  Google Scholar 

  5. Ho, Y.-C., Kashyap, R.L.: An algorithm for linear inequalities and its applications. IEEE Trans. Comput. EC 14(5), 683–688 (1965)

    Article  Google Scholar 

  6. Warmack, R.E., Gonzalez, R.C.: An algorithm for the optimal solution of linear inequalities and its application to pattern recognition. IEEE Trans. Comput. C–22(12), 1065–1075 (1973)

    Article  MathSciNet  Google Scholar 

  7. Castillo, E., Conejo, A.J., Eva Pruneda, R., Solares, C.: Observability in linear systems of equations and inequalities: applications. Comput. Oper. Res. 34(6), 1708–1720 (2007)

    Article  MathSciNet  Google Scholar 

  8. Castillo, E., Pruneda, R.E., Solares, C., Mínguez, R.: Interpreting linear systems of equalities and inequalities: application to the water supply problem. Numer. Linear Algebra Appl. 13, 361–397 (2006)

    Article  MathSciNet  Google Scholar 

  9. Agmon, S.: The relaxation method for linear inequalities. Can. J. Math. 6, 382–392 (1954)

    Article  MathSciNet  Google Scholar 

  10. Motzkin, T.S., Schoenberg, I.J.: The relaxation method for linear inequalities. Can. J. Math. 6, 393–404 (1954)

    Article  MathSciNet  Google Scholar 

  11. Goffin, J.L.: On the finite convergence of the relaxation method for solving systems of inequalities. PhD thesis, Operations Research Center, Univ. of California, Berkeley (1971)

  12. Goffin, J.L.: The relaxation method for solving systems of linear inequalities. Math. Oper. Res. 5(3), 388–414 (1980)

    Article  MathSciNet  Google Scholar 

  13. Goffin, J.L.: On convergence rates of subgradient optimization methods. Math. Program. 13(1), 329–347 (1977)

    Article  MathSciNet  Google Scholar 

  14. Censor, Y.: Row-action methods for huge and sparse systems and their applications. SIAM Rev. 23(4), 444–446 (1981)

    Article  MathSciNet  Google Scholar 

  15. Nutini, J., Sepehry, B., Laradji, I., Koepke, M.S., Virani, A.: Convergence rates for greedy Kaczmarz algorithms, and faster randomized Kaczmarz rules using the orthogonality graph. In: Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, pp. 547– 556 ( 2016)

  16. Censor, Y., Elfving, T.: New methods for linear inequalities. Linear Algebra Appl. 42, 199–211 (1982)

    Article  MathSciNet  Google Scholar 

  17. Merzlyakov, Y.I.: On a relaxation method of solving systems of linear inequalities. USSR Comput. Math. Math. Phys. 2(3), 504–510 (1963)

    Article  Google Scholar 

  18. Daniel, J.W.: Remarks on perturbations in linear inequalities. SIAM J. Numer. Anal. 12(5), 770–772 (1975)

    Article  MathSciNet  Google Scholar 

  19. Hu, H., Wang, Q.: On approximate solutions of infinite systems of linear inequalities. Linear Algebra Appl. 114–115, 429–438 (1989)

    Article  MathSciNet  Google Scholar 

  20. Spingarn, J.E.: A primal-dual projection method for solving systems of linear inequalities. Linear Algebra Appl. 65, 45–62 (1985)

    Article  MathSciNet  Google Scholar 

  21. Leventhal, D., Lewis, A.S.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35(3), 641–654 (2010)

    Article  MathSciNet  Google Scholar 

  22. De Loera, J.A., Haddock, J., Needell, D.: A sampling Kaczmarz–Motzkin algorithm for linear feasibility. SIAM J. Sci. Comput. 39(5), 66–87 (2017)

    Article  MathSciNet  Google Scholar 

  23. Morshed, M.S., Islam, M.S., Noor-E-Alam, M.: Accelerated sampling Kaczmarz–Motzkin algorithm for the linear feasibility problem. J. Glob. Optim. 77, 361–382 (2020)

    Article  MathSciNet  Google Scholar 

  24. Morshed, M.S., Islam, M.S., Noor-E-Alam, M.: Sampling Kaczmarz–Motzkin method for linear feasibility problems: generalization and acceleration. Math. Program. 194, 719–779 (2022)

    Article  MathSciNet  Google Scholar 

  25. Briskman, J., Needell, D.: Block Kaczmarz method with inequalities. J. Math. Imaging Vis. 52, 385–396 (2015)

    Article  MathSciNet  Google Scholar 

  26. Needell, D., Tropp, J.A.: Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra Appl. 441, 199–221 (2014)

    Article  MathSciNet  Google Scholar 

  27. Necoara, I.: Faster randomized block Kaczmarz algorithms. SIAM J. Matrix Anal. Appl. 40(4), 1425–1452 (2019)

    Article  MathSciNet  Google Scholar 

  28. Moorman, J.D., Tu, T.K., Molitor, D., Needell, D.: Randomized Kaczmarz with averaging. BIT 61(1), 337–359 (2021)

    Article  MathSciNet  Google Scholar 

  29. Hoffman, A.J.: On approximate solutions of systems of linear inequalities. J. Res. Natl. Bur. Stand. 49(4), 263–265 (1952)

    Article  MathSciNet  Google Scholar 

  30. Robinson, S.M.: Bounds for error in the solution set of a perturbed linear program. Linear Algebra Appl. 6, 69–81 (1973)

    Article  MathSciNet  Google Scholar 

  31. Klatte, D., Thiere, G.: Error bounds for solutions of linear equations and inequalities. Math. Methods Oper. Res. 41(2), 191–214 (1995)

    Article  MathSciNet  Google Scholar 

  32. Güler, O., Hoffman, A.J., Rothblum, U.G.: Approximations to solutions to systems of linear inequalities. SIAM J. Matrix Anal. Appl. 16(2), 688–696 (1995)

    Article  MathSciNet  Google Scholar 

  33. Zheng, X.Y., Ng, K.F.: Hoffman’s least error bounds for systems of linear inequalities. J. Glob. Optim. 30, 391–403 (2004)

    Article  MathSciNet  Google Scholar 

  34. Pierra, G.: Decomposition through formalization in a product space. Math. Program. 28(1), 96–115 (1984)

    Article  MathSciNet  Google Scholar 

  35. Bauschke, H.H., Combettes, P.L., Kruk, S.G.: Extrapolation algorithm for affine-convex feasibility problems. Numer. Algorithm 41(3), 239–274 (2006)

    Article  MathSciNet  Google Scholar 

  36. Miao, C.-Q., Wu, W.-T.: On greedy randomized average block Kaczmarz method for solving large linear systems. J. Comput. Appl. Math. 413, 114372 (2022)

    Article  MathSciNet  Google Scholar 

  37. Zhu, L., Lei, Y., Xie, J.: A greedy randomized average block projection method for linear feasibility problems (2022)

  38. Bai, Z.-Z., Wu, W.-T.: On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput. 40(1), 592–606 (2018)

    Article  MathSciNet  Google Scholar 

  39. Guan, Y.-J., Li, W.-G., Xing, L.-L., Qiao, T.-T.: A note on convergence rate of randomized Kaczmarz method. Calcolo 57(3), 1–11 (2020)

    Article  MathSciNet  Google Scholar 

  40. Calafiore, G., Ghaoui, L.E.: Optimization Models. Cambridge University Press, Cambridge (2014)

    Book  Google Scholar 

  41. The Netlib Linear Programming Library. https://www.netlib.org/lp/data

  42. UCI Machine Learning Repository: Iris dataset. https://archive.ics.uci.edu/dataset/53/iris

  43. UCI Machine Learning Repository: Breast cancer Wisconsin (diagnostic) dataset. https://archive.ics.uci.edu/dataset/17

  44. UCI Machine Learning Repository: Default of credit card clients dataset. https://archive.ics.uci.edu/dataset/350

  45. Zhang, Y., Li, H.: Block sampling Kaczmarz–Motzkin methods for consistent linear systems. Calcolo 58, 39 (2021)

    Article  MathSciNet  Google Scholar 

  46. Zhang, Y., Li, H.: Randomized block subsampling Kaczmarz–Motzkin method. Linear Algebra Appl. 667, 133–150 (2023)

    Article  MathSciNet  Google Scholar 

  47. Richtárik, P., Takáč, M.: Stochastic reformulations of linear systems: algorithms and convergence theory. SIAM J. Matrix Anal. Appl. 41(2), 487–524 (2020)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors would like to thank all reviewers and editors for their constructive comments, which help greatly improve the paper.

Funding

This work was supported by the National Natural Science Foundation of China (Grant No. 12071196).

Author information

Authors and Affiliations

  1. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou, 730070, People’s Republic of China

    Yu-Qi Niu

  2. School of Mathematics and Statistics, Lanzhou University, Lanzhou, 730000, People’s Republic of China

    Yu-Qi Niu & Bing Zheng

Authors
  1. Yu-Qi Niu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bing Zheng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bing Zheng.

Ethics declarations

Conflict of interest

There are no conflict of interest.

Ethics approval

Not applicable.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Niu, YQ., Zheng, B. Efficient randomized block Kaczmarz method for linear feasibility. Calcolo 62, 4 (2025). https://doi.org/10.1007/s10092-024-00628-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10092-024-00628-7

Keywords

Mathematics Subject Classification

Search

Navigation