phenotypic.util.geometric_median#

phenotypic.util.geometric_median(points: ndarray, eps: float = 1e-06, method: Literal['weiszfeld', 'cohen'] = 'weiszfeld', matrix_free: bool | None = None, matrix_free_threshold: int = 100, verbose: bool = False, **kwargs) → Tuple[ndarray, Dict][source]#

Compute geometric median of a set of points.

Main interface to the classical Weiszfeld algorithm. The Cohen et al. (2016) nearly-linear-time routines are transcribed in this module but are not wired up, so ‘weiszfeld’ is both the default and the only method that runs.

Parameters:
  • points (ndarray) – Data points, shape (n, d)

  • eps (float) –

    Target accuracy for (1 + eps)-approximation

    Note: points within 1e-12 * max(||x||, 1) of the running estimate are treated as coincident with it. For data at a coordinate scale below ~1e-11 this collapses the whole cloud into that set and returns the mean.

  • method (Literal['weiszfeld', 'cohen']) –

    Algorithm to use: - ‘weiszfeld’: Classical Weiszfeld reweighting [default] - ‘cohen’: Cohen et al. (2016) O(nd log³(n/ε)) algorithm –

    NOT IMPLEMENTED, raises ValueError

  • matrix_free (bool | None) – For Cohen method, whether to use matrix-free Hessian. If None, automatically decides based on dimension.

  • matrix_free_threshold (int) – Dimension threshold for matrix-free mode

  • verbose (bool) – Whether to print progress information

  • **kwargs – Additional method-specific arguments

Returns:

Geometric median point, shape (d,) info: Dictionary with algorithm statistics:

  • ’iterations’: Number of iterations performed

  • ’objective’: Final objective value f(x)

  • ’converged’: Whether algorithm converged

  • ’method’: Algorithm used

  • Additional method-specific statistics

Return type:

median

Raises:

ValueError – If method is ‘cohen’ (not implemented), if method is unrecognised, or if points has the wrong shape.

Examples

Geometric median of a small point cloud:

>>> import numpy as np
>>> rng = np.random.default_rng(0)
>>> points = rng.normal(size=(100, 3))
>>> median, info = geometric_median(points, eps=1e-6)
>>> median.shape
(3,)
>>> info['method']
'weiszfeld'
>>> bool(info['converged'])
True

References

Cohen, M. B., Lee, Y. T., Miller, G., Pachocki, J., & Sidford, A. (2016). Geometric median in nearly linear time. STOC 2016.