Skip to content

skmatter

skmatter — scikit-matter — is a scikit-learn-compatible library of feature and sample selection methods aimed at atomistic machine learning. Farthest-point sampling is one entry in a larger catalogue that also includes CUR decomposition and several information-theoretic selectors.

For this comparison it is the idiomatic choice rather than the fastest one: a selector with fit/transform semantics that drops into an existing scikit-learn pipeline without new vocabulary. If a project already lives in that ecosystem, that convenience is worth more than a constant factor in speed.

Its selection behavior is the same greedy traversal as the other pickers, with the same guarantee.

Problem targeted

Given \(n\) vectors and a target size \(k\), farthest-point sampling approximates

\[ \max_{|S| = k} \; \min_{i \ne j \in S} \lVert x_i - x_j \rVert_2 , \]

selecting at each step the candidate whose nearest already-selected neighbor is furthest away.

Guarantee: 2-approximation. The traversal's standard bound. skmatter also exposes non-diversity selectors (CUR, PCovR-based) whose objectives are different problems entirely and are out of scope here.

Reference

At a glance
Guarantee 2-approximation (farthest-point traversal)
License BSD-3-Clause
Version 0.3.3
Released 2026-01-06
Determinism deterministic
Input vectors
Source https://scikit-matter.readthedocs.io/
Last verified 2026-07-27

Capabilities

Support: ✔ built in · ◐ reachable, but you supply the model, transform or metric · — not available

Capability Support Notes
distance metrics · L1 (Manhattan) distance —
distance metrics · L2 (Euclidean) distance ✔
distance metrics · cosine distance ◐ 1
distance metrics · caller-supplied distances —
diversity objectives · maximize the minimum separation ✔
diversity objectives · maximize the mean nearest-neighbor separation —
diversity objectives · maximize the geometric-mean nearest-neighbor separation —
diversity objectives · maximize the mean pairwise distance —
constraints beyond k · per-group counts over disjoint groups —
constraints beyond k · per-group counts over overlapping groups —
constraints beyond k · minimum and maximum counts per group —
time budget · budget expressed as an iteration count —
time budget · budget expressed as wall-clock time —
time budget · the answer improves when given more budget — 2
largest practical problem size n ≈ 105 3

  1. Reachable by L2-normalizing the vectors first: on the unit sphere, cosine distance is a monotone function of Euclidean distance, so a Euclidean picker returns the same ordering. ↩

  2. A single construction pass, so there is no budget to spend: the answer is whatever one greedy sweep produces, and waiting longer does not change it. ↩

  3. A NumPy implementation following scikit-learn conventions: no distance matrix is stored, but each pick scans all remaining candidates, so cost grows as n·k. Comfortable into the hundreds of thousands, an order below the compiled implementations. ↩