  Optimizing strongly convex functions subject to linear constraints is a
fundamental problem with numerous applications. In this work, we propose a
block (accelerated) randomized Bregman-Kaczmarz method that only uses a block
of constraints in each iteration to tackle this problem. We consider a dual
formulation of this problem in order to deal in an efficient way with the
linear constraints. Using convex tools, we show that the corresponding dual
function satisfies the Polyak-Lojasiewicz (PL) property, provided that the
primal objective function is strongly convex and verifies additionally some
other mild assumptions. However, adapting the existing theory on coordinate
descent methods to our dual formulation can only give us sublinear convergence
results in the dual space. In order to obtain convergence results in some
criterion corresponding to the primal (original) problem, we transfer our
algorithm to the primal space, which combined with the PL property allows us to
get linear convergence rates. More specifically, we provide a theoretical
analysis of the convergence of our proposed method under different assumptions
on the objective and demonstrate in the numerical experiments its superior
efficiency and speed up compared to existing methods for the same problem.
