regpy.solvers.linear.primal_dual

Classes

PDHG

The Primal-Dual Hybrid Gradient (PDHG) or Chambolle-Pock Algorithm

DouglasRachford

The Douglas-Rashford Splitting Algorithm

Module Contents

class regpy.solvers.linear.primal_dual.PDHG(setting, init_domain=None, init_codomain_star=None, tau=0, sigma=0, theta=-1, op_norm=None, proximal_pars_data_fidelity_conjugate=None, proximal_pars_penalty=None, compute_y=True, logging_level='INFO')[source]

Bases: regpy.solvers.general.RegSolver

The Primal-Dual Hybrid Gradient (PDHG) or Chambolle-Pock Algorithm For \(\theta=0\) this is the Arrow-Hurwicz-Uzawa algorithm.

Solves the minimization problem: \(\frac{1}{\alpha}\mathcal{S}_{g^{\delta}}(Tf)+\mathcal{R}(f)\) by solving the saddle-point problem:

\[\inf_f \sup_p [ - \langle Tf,p\rangle + \mathcal{R}(f)- \frac{1}{\alpha}\mathcal{S}_{g^{\delta}}^\ast(-\alpha p) ].\]

Here \(\mathcal{S}_{g^{\delta}}^\ast\) denotes the Fenchel conjugate functional.

Note: Due to a different sign convention for the dual variables, some signs in the iteration formula differ from the original paper and most of the literature.

Parameters:

  • setting (regpy.solvers.Setting) – The setting of the forward problem. The operator needs to be linear and “penalty.proximal” and “data_fid.conj.proximal” need to be implemented.

  • init_domain (setting.op.domain [default: None]) – The initial guess “f”. If None, it will be either initialized by 0 or using the optimality conditions in case init_codomain_star is given.

  • init_codomain_star (setting.op.codomain [default: None]) – The initial guess “p”. Initialization is analogous to init_domain.

  • tau (float [default: 0]) – The parameter to compute the proximal operator of the penalty term. Stepsize of the primal step. Must be non-negative. If 0, a positive value is selected automatically based on the operator norm and the value of sigma.

  • sigma (float [default: 0]) – The parameter to compute the proximal operator of the data-fidelity term. Stepsize of the dual step. Must be non-negative. If 0, a positive value is selected automatically based on the operator norm and the value of tau

  • theta (float [default: -1]) – Relaxation parameter. For theta==0 PDHG is the Arrow-Hurwicz-Uzawa algorithm. If -1, a suitable value is selected automatically based on the convexity parameters of penalty and data fidelity term.

  • op_norm (float [default: None]) – The operator norm of the forward operator. If None, it is computed numerically.

  • proximal_pars_data_fidelity_conjugate (dict, optional) – Parameter dictionary passed to the computation of the prox-operator of the data fidelity functional.

  • proximal_pars_penalty (dict, optional) – Parameter dictionary passed to the computation of the prox-operator of the penalty functional.

  • compute_y (boolean [True]) – If True, the images y_k=T(x_k) are computed in each iteration. As they are not needed in the algorithm, so this may considerably increase computational costs. If False, None is returned for y_k.

x_old
compute_y = True
y

The value at the current iterate. May be needed by stopping rules, but callers should handle the case when it is not available.

proximal_pars_data_fidelity_conjugate = None
proximal_pars_penalty = None
static check_applicability(setting, op_norm=None, tau=0, sigma=0, theta=-1) → tuple[dict, dict][source]
primal()[source]
dual()[source]
class regpy.solvers.linear.primal_dual.DouglasRachford(setting, init_h, tau=1, regpar=1, proximal_pars_data_fidelity=None, proximal_pars_penalty=None)[source]

Bases: regpy.solvers.general.RegSolver

The Douglas-Rashford Splitting Algorithm

Minimizes \(\mathcal{S}(Tf)+\alpha*\mathcal{R}(f)\)

Parameters:

  • setting (regpy.solvers.Setting) – The setting of the forward problem, both penalty and data fidelity need prox-operators. The operator needs to be linear. And the data_fid term contains the the operator for example data_fid = HilbertNorm(h_space=L2) * (op - data), i.e. it is mapping from the domain of the operator.

  • init_h (array_like) – The initial guess “f”. Must be in setting.op.domain.

  • tau (float , optional) – The parameter to compute the proximal operator of the penalty term. Must be positive. (Default: 1)

  • regpar (float, optional) – The regularization parameter. Must be positive. (Default: 1)

  • proximal_pars_data_fidelity (dict, optional) – Parameter dictionary passed to the computation of the prox-operator of the data fidelity functional. (Default: None)

  • proximal_pars_penalty (dict, optional) – Parameter dictionary passed to the computation of the prox-operator of the penalty functional. (Default: None))

h
tau = 1
regpar = 1
proximal_pars_data_fidelity = None
proximal_pars_penalty = None
x

The current iterate.

y

The value at the current iterate. May be needed by stopping rules, but callers should handle the case when it is not available.