pyproximal.Sum

class pyproximal.Sum(ops: List[ProxOperator], weights: Optional[Union[ndarray[tuple[Any, ...], dtype[_ScalarT]], List[float]]] = None, niter: int = 1000, tol: float = 1e-07, use_parallel: bool = False, use_original_tau: bool = False)

Proximal operator of the sum of proximable functions using Dykstra-like algorithm.

Parameters

opslist

A list of proximable functions \(f_1, \ldots, f_m\).

weightsnp.ndarray or list or None, optional, default=None

Weights \(\sum_{i=1}^m w_i = 1, \ 0 < w_i < 1\), used when \(m > 2\), or \(m = 2\) and use_parallel=True. Defaults to None, which means \(w_1 = \cdots = w_m = \frac{1}{m}.\)

niterint, optional, default=1000

The maximum number of iterations.

tolfloat, optional, default=1e-7

Tolerance on change of the solution (used as stopping criterion). If tol=0, run until niter is reached.

use_parallelbool, optional, default=False

The parallel version is used when \(m > 2\), or \(m = 2\) and use_parallel=True.

use_original_taubool, optional, default=False

Use the original value of \(\tau\) (True) or the scaled version \(\tau_i = \tau / w_i\) (False).

See also

projection.GenericIntersectionProj

The convex projection to the intersection of convex sets using Dykstra’s algorithm.

Notes

Given two functions \(f\) and \(g\), or a set of proximable functions \(f_i\) and corresponding weights \(w_i\) for \(i=1, \ldots, m\), this class computes the proximal operator of the sum of two functions

\[\prox_{\tau (f + g)}\]

using the Dykstra-like algorithm, or of the weighted sum of functions

\[\prox_{\tau \ \sum_{i=1}^m w_i f_i}\]

using the parallel Dykstra-like algorithm.

For \(m=2\), the proximal mapping \(\prox_{\tau (f + g)}(\mathbf{x})\) of \(\mathbf{x}\) is computed by the Dykstra-like algorithm [1], [2]:

• \(\mathbf{x}^0 = \mathbf{x}, \mathbf{p}^0 = \mathbf{q}^0 = \mathbf{0}\)

• for \(k = 1, \ldots\)

  • \(\mathbf{y}^k = \prox_{\tau g}(\mathbf{x}^k + \mathbf{p}^k)\)

  • \(\mathbf{p}^{k+1} = \mathbf{p}^k + \mathbf{x}^k - \mathbf{y}^k\)

  • \(\mathbf{x}^{k+1} = \prox_{\tau f}(\mathbf{y}^k + \mathbf{q}^k)\)

  • \(\mathbf{q}^{k+1} = \mathbf{q}^k + \mathbf{y}^k - \mathbf{x}^{k+1}\)

For \(m \ge 2\), the proximal mapping \(\prox_{\tau \sum_{i=1}^m w_i f_i}(\mathbf{x})\) of \(\mathbf{x}\) is computed by the parallel Dykstra-like algorithm [3], [4], [5], where \(\sum_{i=1}^m w_i = 1, \ 0 < w_i < 1\):

• \(\mathbf{x}^0 = \mathbf{z}_1^0 = \cdots = \mathbf{z}_m^0 = \mathbf{x}\)

• for \(k = 1, \ldots\)

  • \(\mathbf{x}^{k+1} = \sum_{i=1}^{m} w_i \prox_{\tau_i f_i} (\mathbf{z}_{i}^k)\)

  • for \(i = 1, \ldots, m\)

    • \(\mathbf{z}_{i}^{k+1} = \mathbf{z}_{i}^k + \mathbf{x}^{k+1} - \prox_{\tau_i f_i} (\mathbf{z}_{i}^k)\)

Note that \(\tau_i = \tau / w_i\) if use_original_tau==False (default), otherwise \(\tau_i = \tau\).

References

1

Combettes, P.L., Pesquet, J.-C., 2011. Proximal Splitting Methods in Signal Processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, pp. 185-212. Algorithm 10.18. https://doi.org/10.1007/978-1-4419-9569-8_10

2

Bauschke, H.H., Combettes, P.L., 2008. A Dykstra-like algorithm for two monotone operators. Pacific Journal of Pitimization 4, 383-391. Theorem 3.3. http://www.ybook.co.jp/online-p/PJO/vol4/pjov4n3p383.pdf

3

Combettes, P.L., Pesquet, J.-C., 2011. Proximal Splitting Methods in Signal Processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, pp. 185-212. Algorithm 10.31. https://doi.org/10.1007/978-1-4419-9569-8_10

4

Combettes, P.L., Dũng, Đ., Vũ, B.C., 2011. Proximity for sums of composite functions. Journal of Mathematical Analysis and Applications 380, 680-688. Eq. (2.26) https://doi.org/10.1016/j.jmaa.2011.02.079

5

Combettes, P.L., 2009. Iterative Construction of the Resolvent of a Sum of Maximal Monotone Operators. Journal of Convex Analysis 16, 727-748. Theorem 4.2. https://www.heldermann.de/JCA/JCA16/JCA163/jca16044.htm

Methods

__init__(ops[, weights, niter, tol, ...])
affine_addition(v)	Affine addition
chain(g)	Chain
grad(x)	Gradient of the Moreau envelope of the function.
postcomposition(sigma)	Postcomposition
precomposition(a, b)	Precomposition
prox(**kwargs)
proxdual(**kwargs)

Examples using pyproximal.Sum

Dykstra’s algorithms

Dykstra's algorithms