Writing

status: pre-print · PDF · related crate: gcm-lcm

Given samples of a function on \([a,b]\), the greatest convex minorant (GCM) is the largest convex function lying below them, and the least concave majorant (LCM) is its concave dual. This note develops an algorithm to compute both, with an eye toward use as a convex (or concave) function approximator in stochastic-process problems.

The idea is crystallized and the construction is rigorous, but 3 years ago I thought I had more to elicit (e.g. an online, single-pass variant). I am releasing it here so the companion crate gcm-lcm rests on a stated foundation rather than folklore. It needs endorsement before it can go to arXiv.org; when that happens, this link will point there instead.

@misc{radcliffe_gcmlcm,
  author = {Radcliffe, Andrew J.},
  title  = {An O(n) algorithm to construct the greatest convex minorant and least concave majorant},
  year   = {2023},
  note   = {pre-print},
  howpublished = {\url{https://andrewjradcliffe.github.io/writing/}}
}