Accelerating Random Kaczmarz Algorithm Based on Clustering Information

Authors

  • Yujun Li Shanghai Jiao Tong University
  • Kaichun Mo Shanghai Jiao Tong University
  • Haishan Ye Shanghai Jiao Tong University

DOI:

https://doi.org/10.1609/aaai.v30i1.10217

Keywords:

Kaczmarz algorithm, consistent linear equation system, matrix block

Abstract

Kaczmarz algorithm is an efficient iterative algorithm to solve overdetermined consistent system of linear equations. During each updating step, Kaczmarz chooses a hyperplane based on an individual equation and projects the current estimate for the exact solution onto that space to get a new estimate.Many vairants of Kaczmarz algorithms are proposed on how to choose better hyperplanes.Using the property of randomly sampled data in high-dimensional space,we propose an accelerated algorithm based on clustering information to improve block Kaczmarz and Kaczmarz via Johnson-Lindenstrauss lemma. Additionally, we theoretically demonstrate convergence improvement on block Kaczmarz algorithm.

Downloads

Published

2016-02-21

How to Cite

Li, Y., Mo, K., & Ye, H. (2016). Accelerating Random Kaczmarz Algorithm Based on Clustering Information. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10217

Issue

Section

Technical Papers: Machine Learning Methods