Monotone Regression: A Simple and Fast O(n) PAVA Implementation

Journal of Statistical Software, vol. 102

Abstract

Efficient coding and improvements in the execution order of the up-and-down-blocks algorithm for monotone or isotonic regression leads to a significant increase in speed as well as a short and simple O(n) implementation. Algorithms that use monotone regression as a subroutine, e.g., unimodal or bivariate monotone regression, also benefit from the acceleration. A substantive comparison with and characterization of currently available implementations provides an extensive overview of up-and-down-blocks implementations for the pool-adjacent-violators algorithm for simple linear ordered monotone regression.

Authors 1

1. Frank M. T. A. Busing corresponding Aachen

   Leiden University

   Affiliation as printed

   Leiden University