Contributed code

Stochastic PDHG

Contributed by Dr. Matthias Ehrhardt.

class ccpi.contrib.optimisation.algorithms.spdhg.spdhg(f, g, A, x=None, y=None, z=None, tau=None, sigma=None, prob=None, A_norms=None, fun_select=None)[source]

Computes a saddle point with a stochastic PDHG.

This means, a solution (x*, y*), y* = (y*_1, …, y*_n) such that

(x*, y*) in arg min_x max_y sum_i=1^n <y_i, A_i> - f*[i](y_i) + g(x)

where g : X -> IR_infty and f[i] : Y[i] -> IR_infty are convex, l.s.c. and proper functionals. For this algorithm, they all may be non-smooth and no strong convexity is assumed.

f : list of functions
Functionals Y[i] -> IR_infty that all have a convex conjugate with a proximal operator, i.e. f[i].convex_conj.prox(sigma[i]) : Y[i] -> Y[i].
g : function
Functional X -> IR_infty that has a proximal operator, i.e. g.prox(tau) : X -> X.
A : list of functions
Operators A[i] : X -> Y[i] that possess adjoints: A[i].adjoint
x : primal variable, optional
By default equals 0.
y : dual variable, optional
Part of a product space. By default equals 0.
z : variable, optional
Adjoint of dual variable, z = A^* y. By default equals 0 if y = 0.
tau : scalar / vector / matrix, optional
Step size for primal variable. Note that the proximal operator of g has to be well-defined for this input.
sigma : scalar, optional
Scalar / vector / matrix used as step size for dual variable. Note that the proximal operator related to f (see above) has to be well-defined for this input.
prob : list of scalars, optional
Probabilities prob[i] that a subset i is selected in each iteration. If fun_select is not given, then the sum of all probabilities must equal 1.
A_norms : list of scalars, optional
Norms of the operators in A. Can be used to determine the step sizes tau and sigma and the probabilities prob.
fun_select : function, optional
Function that selects blocks at every iteration IN -> {1,…,n}. By default this is serial sampling, fun_select(k) selects an index i in {1,…,n} with probability prob[i].

[CERS2018] A. Chambolle, M. J. Ehrhardt, P. Richtarik and C.-B. Schoenlieb, Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications. SIAM Journal on Optimization, 28(4), 2783-2808 (2018) http://doi.org/10.1007/s10851-010-0251-1

[E+2017] M. J. Ehrhardt, P. J. Markiewicz, P. Richtarik, J. Schott, A. Chambolle and C.-B. Schoenlieb, Faster PET reconstruction with a stochastic primal-dual hybrid gradient method. Wavelets and Sparsity XVII, 58 (2017) http://doi.org/10.1117/12.2272946.

[EMS2018] M. J. Ehrhardt, P. J. Markiewicz and C.-B. Schoenlieb, Faster PET Reconstruction with Non-Smooth Priors by Randomization and Preconditioning. (2018) ArXiv: http://arxiv.org/abs/1808.07150

__init__(f, g, A, x=None, y=None, z=None, tau=None, sigma=None, prob=None, A_norms=None, fun_select=None)[source]

Initialize self. See help(type(self)) for accurate signature.

__weakref__

list of weak references to the object (if defined)

Return Home