<abstract xmlns="http://www.w3.org/1999/xhtml"> We show that the Sparse Kaczmarz method is a particular instance of the coordinate gradient method applied to an unconstrained dual problem corresponding to a regularized ℓ1-minimization problem subject to linear constraints. Based on this observation and recent theoretical work concerning the convergence analysis and corresponding convergence rates for the randomized block coordinate gradient descent method, we derive block versions and consider randomized ordering of blocks of equations. Convergence in expectation is thus obtained as a byproduct. By smoothing the ℓ1-objective we obtain a strongly convex dual which opens the way to various acceleration schemes.</abstract>

We show that the Sparse Kaczmarz method is a particular instance of the coordinate gradient method applied to an unconstrained dual problem corresponding to a regularized ℓ1-minimization problem subject to linear constraints. Based on this observation and recent theoretical work concerning the convergence analysis and corresponding convergence rates for the randomized block coordinate gradient descent method, we derive block versions and consider randomized ordering of blocks of equations. Convergence in expectation is thus obtained as a byproduct. By smoothing the ℓ1-objective we obtain a strongly convex dual which opens the way to various acceleration schemes.

Randomized Sparse Block Kaczmarz as Randomized Dual Block-Coordinate Descent

Image and Pattern Analysis Group, Department of Mathematics and Computer Science, University of Heidelberg, Speyerer Str. 6, 69115 Heidelberg,

Analele ştiinţifice ale Universităţii "Ovidius" Constanţa. Seria Matematică

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Randomized Sparse Block Kaczmarz as Randomized Dual Block-Coordinate Descent"}

We show that the Sparse Kaczmarz method is a particular instance of the coordinate gradient method applied to an unconstrained dual problem corresponding to a...

Randomized Sparse Block Kaczmarz as Randomized Dual Block-Coordinate Descent

Published Online: Apr 22, 2017

Page range: 129 - 149

Received: Jan 01, 2015

Accepted: Mar 01, 2015

DOI: https://doi.org/10.1515/auom-2015-0052

Keywords
Randomized block-coordinate descent, underdetermined system of linear equations, compressed sensing, sparse Kaczmarz solver, linearized Bregman method, convex duality, convex programming, limited-data tomography

© 2017

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Randomized Sparse Block Kaczmarz as Randomized Dual Block-Coordinate Descent

Published Online: Apr 22, 2017

Page range: 129 - 149

Received: Jan 01, 2015

Accepted: Mar 01, 2015

DOI: https://doi.org/10.1515/auom-2015-0052

KeywordsRandomized block-coordinate descent, underdetermined system of linear equations, compressed sensing, sparse Kaczmarz solver, linearized Bregman method, convex duality, convex programming, limited-data tomography

© 2017

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Keywords
Randomized block-coordinate descent, underdetermined system of linear equations, compressed sensing, sparse Kaczmarz solver, linearized Bregman method, convex duality, convex programming, limited-data tomography