Abstract: This paper considers the problem of determining L_∞ isotonic regressions satisfying order constraints given by a partially ordered set. One of the techniques used is to first solve the prefix isotonic regression problem, where for every element x in the partial order, you determine the regression error for the isotonic regression on x and all of its predecessors. This problem can be solved by visiting the nodes in an ordering given by topological sorting. Given the error it is then easy to find an isotonic regression with that error, again using topological sorting and finishing in Θ(m) time. (Note that for L_∞ the optimal isotonic regression is often not unique.)

The algorithms show how to compute the isotonic regressions in

• Θ(m log n) time when the partial order is given as a directed acyclic graph with n vertices and m edges.
• Θ(m) time when the regression values are restricted to the integers or a given finite set and the solution to the unrestricted problem is known. A slightly slower algorithm, taking Θ(m log s) time, is given for when the set has s elements and the unrestricted solution is not known.
• Θ(n log n) time when the ordering is linear. Solving the prefix regression problem allows one to find the unimodal regression in the same time bound. This continues the approach used in Unimodal Regression via Prefix Isotonic Regression.
• Θ(n log n) time when the ordering is a tree.
• Θ(n log^d n) time when the ordered set is a set of n points in d-dimensional space with ordering given by domination. I.e., if p=(p₁,...,p_d) and q=(q₁,...,q_d) are points in d-dimensional space, then p precedes q if p_i ≤ q_i for all 1 ≤ i ≤ d. Domination ordering is also known as dimensional ordering or majorization.

For d-dimensional points, if they form a grid, rather than just being in arbitrary positions, then the result for general orderings shows the regression can be found in Θ(n log n) time, though parametric search is required. If the points are in arbitrary positions then the natural representation of the ordering can require Θ(n²) edges, and hence the time would be Ω(n²). The time listed above is achieved by a technique which does not explicitly use every edge, but rather uses them implicitly.

If the data is unweighted then the prefix isotonic regression can easily be found in Θ(m) time for any ordering, and Θ(n log^d-1 n) time for points in d-dimensional space.

Keywords: isotonic regression, nonparametric, shape constrained, unimodal regression, envelope, prefix isotonic regression, minimax error, L_∞, uniform metric, Chebyshev metric, partial order, domination, linear order, rooted tree, multidimensional divide-and-conquer

Complete paper. This is a major revision of an earlier version from 2008. The title has been changed slightly, adding the ``Algorithms for'', and the algorithm for multidimensional data is completely different. The prior approach to multidimensional data, not based on solving the prefix problem, has been moved to a different paper, ``An approach to computing multidimensional isotonic regression'', which also applies the approach to L₁ and L₂ metrics.

Copyright © 2008-2009 Quentin F. Stout.