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 an overview of my work on shape constrained regression (isotonic, unimodal, step).
|
Copyright © 2012-2021 Quentin F. Stout |