This paper gives algorithms for determining isotonic regressions for weighted data at a set of points P in multidimensional space with the standard componentwise ordering. The approach is based on an order-preserving embedding of P into a slightly larger directed acyclic graph (dag) G, where the transitive closure of the ordering on P is represented by paths of length 2 in G. Algorithms are given which, compared to previous results, improve the time by a factor of $\tilde{\varTheta}(|P|)$ for the L 1, L 2, and L ? metrics. A yet faster algorithm is given for L 1 isotonic regression with unweighted data. L ? isotonic regression is not unique, and algorithms are given for finding L ? regressions with desirable properties such as minimizing the number of large regression errors.
['Quentin F. Stout']
Isotonic Regression for Multiple Independent Variables