Randomized Primal-Dual Algorithm with Arbitrary Sampling: Convergence Theory and Applications to Parallel MRI

Abstract Stochastic Primal-Dual Hybrid Gradient (SPDHG) is an algorithm proposed by Chambolle et al. (SIAM J Optim 28:2783–2808) to efficiently solve a wide class of nonsmooth large-scale optimization problems. Alacaoglu et al. (SIAM J Optim 32:1288–1318, 2022) filled an important gap and proved its almost sure convergence for serial sampling. In this paper, we study the performance of SPDHG with arbitrary sampling (not necessarily serial sampling) and its applications to parallel magnetic resonance imaging (MRI), where data from different coils are randomly selected at each iteration. In order to do this, we extend the convergence result of Alacaoglu et al. and prove the almost sure convergence of SPDHG for any arbitrary sampling. We then apply SPDHG on real MRI data using a wide range of random sampling methods and compare its performance across a range of settings, including mini-batch size and step size parameters. We show that the sampling can significantly affect the convergence speed of SPDHG and that for many cases an optimal sampling can be identified.