Abstract | ||
---|---|---|
In this paper, we propose a modification that speeds up the convergence of the randomized Kaczmarz algorithm for systems of linear equations with sparse solutions. The speedup is achieved by projecting every iterate onto a weighted row of the linear system while maintaining the random row selection criteria of Strohmer and Vershynin. While the Kaczmarz algorithm and its variants can only find solutions to overdetermined linear systems, our algorithm surprisingly succeeds in finding sparse solutions to underdetermined linear systems as well. Our numerical experiments demonstrate the accelerated convergence in the overdetermined case as well as the sparse recovery capabilities of our approach in the underdetermined case. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1109/GlobalSIP.2013.6736958 | Global Conference Signal and Information Processing |
Keywords | Field | DocType |
convergence of numerical methods,iterative methods,random processes,randomised algorithms,convergence,iterative methods,linear equations,numerical analysis,overdetermined linear systems,random row selection criteria,sparse randomized Kaczmarz algorithm,sparse recovery capabilities,sparse solutions,underdetermined linear systems,weighted row | Overdetermined system,Underdetermined system,System of linear equations,Linear system,Iterative method,Sparse approximation,Algorithm,Kaczmarz method,Mathematics,Speedup | Conference |
ISSN | Citations | PageRank |
2376-4066 | 1 | 0.37 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hassan Mansour | 1 | 349 | 34.12 |
Özgür Yilmaz | 2 | 685 | 51.36 |