Optimal Reduced Isotonic Regression

Janis Hardwick     Quentin F. Stout
University of Michigan


Abstract: Isotonic regression is a shape-constrained nonparametric regression in which the ordinate is a nondecreasing function of the abscissa. The regression outcome is an increasing step function. For an initial set of n points, the number of steps in the isotonic regression, m, may be as large as n. As a result, the full isotonic regression has been criticized as overfitting the data or making the representation too complicated. So-called "reduced" isotonic regression constrains the outcome to be a specified number of steps, b. The fastest previous algorithm for determining an optimal reduced isotonic regression takes Θ(n+ b m2) time for the L2 metric. However, researchers have found this to be too slow and have instead used approximations. Here we reduce the time to Θ(n + b m log m) for the L1 and L2 metrics. In contrast, the fastest known algorithm for b-step approximation of arbitrary data takes Θ(b n2) time for L2 and Θ((b + log n) n2) time for L1.

Keywords: isotonic regression algorithms, reduced isotonic regression, histogram, segmentation, monotonic, piecewise constant approximation, step function, isotonic data, dynamic programming

Complete paper. Proc. Interface 2012: The Future of Statistical Computing


NOTE: The work in this paper on L2 was improved upon here, though that paper does not discuss L1. Here is a paper on reduced isotonic regression, and general step-wise approximation, for the L metric.

Quentin Stout homepage Copyright © 2012-2017 Quentin F. Stout