API Reference

In this page, we describes each API provided from the fpmlib package. Here, \(\mathbb{R}\) denotes the set of all float values and \(\mathbb{R}^N\) denotes the set of all ndarray instances whose shape is [N]. The standard inner product \(\langle\cdot,\cdot\rangle:\mathbb{R}^N\times\mathbb{R}^N\to\mathbb{R}\) corresponds to \(\mathtt{numpy.inner}(\cdot,\cdot)\) in implementation, and its induced norm \(\|x\|:=\langle x,x\rangle^\frac{1}{2}\) for given ndarray vector \(x\) corresponds to \(\mathtt{numpy.linalg.norm}(x)\).

Types appearing in fpmlib package

fpmlib module is provided with object-oriented design using the abstract base classes infrastructure (abc package). fpmlib.typing module provides the abstract base classes used to express each class provided in fpmlib package. The following items are automatically loaded when fpmlib package is imported.

class fpmlib.typing.FixedPointMap

Bases: collections.abc.Callable, collections.abc.Container

An abstract base class that expresses a mapping \(T\) from a Hilbert space \(H\) onto itself. This is a superclass of all mappings provided from the fpmlib package.

abstract __call__(x: numpy.ndarray) → numpy.ndarray

Map the given point \(x\in H\) to \(T(x)\).

abstract __contains__(x: Any) → bool

Return True if the given point \(x\) is a fixed point of this mapping \(T\), that is, \(x\in\mathrm{Fix}(T):=\{u\in H:T(u)=u\}\). Otherwise, return False.

__weakref__

list of weak references to the object (if defined)

abstract property ndim

Number of vector dimensions which this mapping deal with. If the value is None, this mapping accepts any vector in arbitrary dimension.

class fpmlib.typing.NonexpansiveMap

Bases: fpmlib.typing.FixedPointMap

An abstract base class that expresses a nonexpansive mapping, that is, a mapping \(T:H\to H\) which satisfies \(\|T(x)-T(y)\|\le\|x-y\|\) for any \(x, y\in H\).

class fpmlib.typing.FirmlyNonexpansiveMap

Bases: fpmlib.typing.NonexpansiveMap

An abstract base class that expresses a firmly nonexpansive mapping, that is, a mapping \(T:H\to H\) which satisfies \(\|T(x)-T(y)\|^2+\|(\mathrm{Id}-T)(x)-(\mathrm{Id}-T)(y)\|^2\le\|x-y\|^2\) for any \(x, y\in H\).

class fpmlib.typing.MetricProjection

Bases: fpmlib.typing.FirmlyNonexpansiveMap

An abstract base class that expresses a metric projection onto some nonempty, closed, convex subset of \(H\), that is, a mapping \(T:H\to H\) which satisfies \(T(x)\in\mathrm{Fix}(T)\) and \(\|T(x)-x\|=\inf_{y\in\mathrm{Fix}(T)}\|x-y\|\) for any \(x\in H\).

Metric projections

There are some convex sets onto which the metric projections can be computed explicitly. fpmlib.projections module provides them. The following items are automatically loaded when fpmlib package is imported.

class fpmlib.projections.Box(lb: Union[numpy.ndarray, float, None] = None, ub: Union[numpy.ndarray, float, None] = None)

Bases: fpmlib.typing.MetricProjection

The metric projection onto the orthotope defined with its lower and upper bound of each dimension. For given \((\mathbf{lb}_i)_{i=1}^N\in\mathbb{R}^N\) and \((\mathbf{ub}_i)_{i=1}^N\in\mathbb{R}^N\), the fixed point set of the created mapping \(T\) is

\[\mathrm{Fix}(T)=\{(x_i)_{i=1}^N\in\mathbb{R}^N:\mathbf{lb}_i\le x_i\le\mathbf{ub}_i\ (i=1,2,\ldots,N)\}.\]

For any ndarray vector \(x\), \(T(x)\) is equivalent to \(\mathtt{np.clip}(x, \mathbf{lb}, \mathbf{ub})\).

Parameters

• lb – An ndarray vector whose element expresses the lower bound corresponding to each dimension. If a float value is specified, it is dealt with as the vector whose all elements are set as the given value. If None is specified, the fixed point set of the created mapping is unbounded below.

• ub – An ndarray vector whose element expresses the upper bound corresponding to each dimension. If a float value is specified, it is dealt with as the vector whose all elements are set as the given value. If None is specified, the fixed point set of the created mapping is unbounded above.

property ndim

Number of vector dimensions which this mapping deal with. If the value is None, this mapping accepts any vector in arbitrary dimension.

class fpmlib.projections.HalfSpace(w: numpy.ndarray, d: float)

Bases: fpmlib.typing.MetricProjection

The metric projection \(P_H\) onto the closed half-space

\[H:=\{x\in\mathbb{R}^N:\langle w, x\rangle\le d\},\]

where \(w\in\mathbb{R}^N\setminus\{0\}\) and \(d\in\mathbb{R}\).

Parameters

• w – An ndarray vector which defines the half-space as its parameter \(w\).

• d – A float value which defines the half-space as its parameter \(d\).

property ndim

Number of vector dimensions which this mapping deal with. If the value is None, this mapping accepts any vector in arbitrary dimension.

class fpmlib.projections.Ball(c: numpy.ndarray, r: float)

Bases: fpmlib.typing.MetricProjection

The metric projection \(P_B\) onto the closed ball with center \(c\in\mathbb{R}^N\) and radius \(r\in\mathbb{R}\), that is

\[B:=\{x\in\mathbb{R}^N:\|x-c\|\le r\}.\]

Parameters

• c – An ndarray vector which expresses the center of the closed ball.

• r – A float value which expresses the radius of the closed ball.

property ndim

Number of vector dimensions which this mapping deal with. If the value is None, this mapping accepts any vector in arbitrary dimension.

Nonexpansive mappings

The following items are automatically loaded when fpmlib package is imported.

class fpmlib.nonexpansive.Intersection(maps: Iterable[fpmlib.typing.NonexpansiveMap])

Bases: fpmlib.typing.NonexpansiveMap

A nonexpansive mapping whose fixed point set coincides with the intersection of the fixed point sets of given nonexpansive mappings. The generated mapping computes the barycenter of each point transformed by given mappings, i.e., for given \(T_i\ (i=1,2,\ldots,K)\) and for any \(x\in H\), it computes

\[T(x):=\frac{1}{K}\sum_{i=1}^K T_i(x).\]

This construction method is based on Propositions 4.9 and 4.47 in [Bauschke2017].

Parameters

maps – A list of nonexpansive mappings.

property ndim

Number of vector dimensions which this mapping deal with. If the value is None, this mapping accepts any vector in arbitrary dimension.

class fpmlib.nonexpansive.Composition(maps: Iterable[fpmlib.typing.NonexpansiveMap])

Bases: fpmlib.typing.NonexpansiveMap

A nonexpansive mapping whose fixed point set coincides with the intersection of the fixed point sets of given nonexpansive mappings. The generated mapping is the composition of given mappings, i.e., for given \(T_i\ (i=1,2,\ldots,K)\), it is defined by

\[T:=T_1\circ T_2\circ \ldots \circ T_K.\]

Except for the last element, each element in parameter maps must be FirmlyNonexpansiveMap. If the intersection of the fixed point sets of given nonexpansive mappings is empty, __contains__ operator may not return a correct value. This construction method is based on Propositions 4.9 and 4.49 in [Bauschke2017].

Parameters

maps – A list of nonexpansive mappings.

property ndim

Number of vector dimensions which this mapping deal with. If the value is None, this mapping accepts any vector in arbitrary dimension.

Algorithms

The following items are automatically loaded when fpmlib package is imported.

fpmlib.algorithms.find(T: fpmlib.typing.NonexpansiveMap, x0: numpy.ndarray, method: str = 'Krasnoselskii-Mann', tol: float = 1e-07, options: Dict[str, Any] = {}) → numpy.ndarray

Find a fixed point of given nonexpansive mapping.

Parameters

• T – A nonexpansive mapping whose fixed point is desired to be found.

• x0 – An initial point.

• method –

  Name of method to be used. We can use one of the following:

  Halpern

  Halpern’s algorithm ([Halpern1967]). This method finds the nearest fixed point to the initial point, i.e., \(x^\star\in\mathrm{Fix}(T)\) such that \(\|x^\star-x_0\|=\inf_{x\in\mathrm{Fix}(T)}\|x-x_0\|\).

  Hishinuma2015

  Accelerated Krasnosel’skii-Mann algorithm based on conjugate gradient method ([Hishinuma2015]).

  Krasnoselskii-Mann (default)

  Krasnosel’skii-Mann algorithm ([Krasnoselskii1955], [Mann1953]).

• tol – Error tolerance, i.e., for the obtained solution \(x^\star\), \(\|x^\star-T(x^\star)\|<\mathtt{tol}\) will be guaranteed.

• options –

  A dictionary passed to the solver. We can give the following parameters:

  maxiter: int

  Maximum number of iterations.

  steps: Iterable[float]

  A step size sequence. When method = 'Krasnoselskii-Mann' or its variant method = 'Hishinuma2015', it is used as the sequence \(\{\alpha_k\}\subset(0, 1)\) for the Krasnosel’skii-Mann iteration \(x_{k+1}:=x_k+\alpha_k(T(x_k)-x_k)\ (k\in\mathbb{N})\). When method = 'Halpern', it is used as the sequence \(\{\lambda_k\subset(0, 1)\}\) for the Halpern’s iteration \(x_{k+1}:=\lambda_k x_0+(1-\lambda_k)T(x_k)\).

  beta: Iterable[float]

  A step size sequence to be used as an acceleration parameter. When method = 'Hishinuma2015', it is passed to Algorithm 3.1 in [Hishinuma2015] as the parameter \(\{\beta_n\}\).

Returns

the obtained solution.

fpmlib.contracts module

This module provides functions for the validation of the use of fpmlib package.

fpmlib.contracts.check_fixed_point_map(o: Any, ndim: Optional[int] = None) → None

Check if the given argument is an instance of FixedPointMap class.

Parameters

• o – An object to be validated.

• ndim – A number of vector dimensions which is expected as acceptable one to the given map. If None is specified, this function will not validate the acceptable number of dimension to the given map.

fpmlib.contracts.check_nonexpansive_map(o: Any, ndim: Optional[int] = None) → None

Check if the given argument is an instance of NonexpansiveMap class.

Parameters

• o – An object to be validated.

• ndim – A number of vector dimensions which is expected as acceptable one to the given map. If None is specified, this function will not validate the acceptable number of dimension to the given map.

fpmlib.contracts.check_firmly_nonexpansive_map(o: Any, ndim: Optional[int] = None) → None

Check if the given argument is an instance of FirmlyNonexpansiveMap class.

Parameters

• o – An object to be validated.

• ndim – A number of vector dimensions which is expected as acceptable one to the given map. If None is specified, this function will not validate the acceptable number of dimension to the given map.

fpmlib.contracts.check_metric_projection(o: Any, ndim: Optional[int] = None) → None

Check if the given argument is an instance of MetricProjection class.

Parameters

• o – An object to be validated.

• ndim – A number of vector dimensions which is expected as acceptable one to the given map. If None is specified, this function will not validate the acceptable number of dimension to the given map.