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 m^{2}) time for the L_{2} 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 L_{1} and L_{2} metrics. In contrast, the fastest known algorithm for b-step approximation of arbitrary data takes Θ(b n^{2}) time for L_{2} and Θ((b + log n) n^{2}) time for L_{1}.
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 L_{2} was improved upon here, though that paper does not discuss L_{1}. Here is a paper on reduced isotonic regression, and general step-wise approximation, for the L_{∞} metric.
Copyright © 2012-2017 Quentin F. Stout |