<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

Data publikacji: 22 kwi 2017

Zakres stron: 129 - 149

Otrzymano: 01 sty 2015

Przyjęty: 01 mar 2015

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

Słowa kluczowe
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

Data publikacji: 22 kwi 2017

Zakres stron: 129 - 149

Otrzymano: 01 sty 2015

Przyjęty: 01 mar 2015

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

Słowa kluczoweRandomized 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.

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