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

Eric Gutierrez Castillo; Claire Delplancke; Matthias Ehrhardt

doi:10.1007/s10851-025-01231-3

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

Eric Gutierrez Castillo, Claire Delplancke, Matthias Ehrhardt

EDF Lab Paris-Saclay

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	25
Journal	Journal of Mathematical Imaging and Vision
Volume	67
Issue number	3
Early online date	17 Apr 2025
DOIs	https://doi.org/10.1007/s10851-025-01231-3
Publication status	Published - 17 Apr 2025

Data Availability Statement

No datasets were generated or analysed during the current study.

Funding

MJE and CD acknowledge support from the EPSRC (EP/S026045/1). MJE is also supported by EPSRC (EP/T026693/1), the Faraday Institution (EP/T007745/1) and the Leverhulme Trust (ECF-2019-478). EBG acknowledges the Mexican Council of Science and Technology (CONACyT).

Funders	Funder number
Consejo Nacional de Humanidades, Ciencias y Tecnologías
Engineering and Physical Sciences Research Council	EP/S026045/1, EP/T026693/1
Faraday Institution	EP/T007745/1
Leverhulme Trust	ECF-2019-478

Keywords

Inverse problems
Parallel MRI
Primal-dual methods
Stochastic optimization

ASJC Scopus subject areas

Statistics and Probability
Modelling and Simulation
Condensed Matter Physics
Computer Vision and Pattern Recognition
Geometry and Topology
Applied Mathematics

Access to Document

10.1007/s10851-025-01231-3Licence: CC BY

Cite this

@article{73f0f7231f4840268a600b8271b909c5,

title = "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.",

keywords = "Inverse problems, Parallel MRI, Primal-dual methods, Stochastic optimization",

author = "{Gutierrez Castillo}, Eric and Claire Delplancke and Matthias Ehrhardt",

year = "2025",

month = apr,

day = "17",

doi = "10.1007/s10851-025-01231-3",

language = "English",

volume = "67",

journal = "Journal of Mathematical Imaging and Vision ",

issn = "0924-9907",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Randomized Primal-Dual Algorithm with Arbitrary Sampling

T2 - Convergence Theory and Applications to Parallel MRI

AU - Gutierrez Castillo, Eric

AU - Delplancke, Claire

AU - Ehrhardt, Matthias

PY - 2025/4/17

Y1 - 2025/4/17

N2 - 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.

AB - 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.

KW - Inverse problems

KW - Parallel MRI

KW - Primal-dual methods

KW - Stochastic optimization

UR - http://www.scopus.com/inward/record.url?scp=105002727862&partnerID=8YFLogxK

U2 - 10.1007/s10851-025-01231-3

DO - 10.1007/s10851-025-01231-3

M3 - Article

SN - 0924-9907

VL - 67

JO - Journal of Mathematical Imaging and Vision

JF - Journal of Mathematical Imaging and Vision

IS - 3

M1 - 25

ER -

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

Abstract

Data Availability Statement

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this