AAAI Publications, Thirtieth AAAI Conference on Artificial Intelligence

Font Size: 
Accelerating Random Kaczmarz Algorithm Based on Clustering Information
Yujun Li, Kaichun Mo, Haishan Ye

Last modified: 2016-02-21


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.


Kaczmarz algorithm; consistent linear equation system; matrix block

Full Text: PDF