We should consider implementing a recently proposed Stochastic Primal-Dual Hybrid Gradient Method (SPDHG) outlined here, which would be a stochastic version of the ODL Primal-Dual Hybrid Gradient (PDHG) algorithm.

SPDHG combines the PDHG method with a randomized dual decomposition strategy (somewhat reminiscent of ART, Kaczmarz, and OSEM, which operate in the primal) and PDHG arises as a special (and suboptimal) case of SPDHG. Authors prove convergence for a wide range of random samplings and they prove rigorous iteration complexity bounds for standard and accelerated variants.