Isotonic Regression for Multiple Independent Variables

Abstract

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 ₁, L ₂, and L _∞ metrics. A yet faster algorithm is given for L ₁ 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.

Appendix:  Optimal Size of Order-Embeddings

For points in 2-dimensional space the condensed rendezvous dag has Θ(nlogn) edges, and here we show that there are sets of points in 2-space for which Ω(nlogn) edges are needed. One example is the bit-reversal permutation: given integer b>0, let V be the set of 2-dimensional points {(i _b i _b−1…i ₁,i ₁ i ₂…i _b ):i _j ∈{0,1}}, i.e., a point is in V if its b-bit 2nd coordinate, in binary, is the reversal of its 1st coordinate.

Proposition 8

Let V be the b-bit bit-reversal permutation, ordered by 2-dimensional ordering. Then for any dag G, if there is an order-embedding of V into G then G has at least $\frac{1}{2}|V| \log_{2} |V|$ edges.

Proof

Note that G is not restricted to 2-dimensional ordering.

To prove this, let G=(V′,E′) be a dag and π be an order-embedding of V into G. Let k ^r denote the bit reversal of k. Then V={p(i):0≤i≤n−1}, where p(i) is the 2-dimensional point (i ^r,i) and n=2^b. Note that p(0),p(1),…,p(n−1) have been ordered by their second coordinate. Let V ₀={p(2i):0≤i<n/2} and V ₁={p(2i+1):0≤i<n/2}, i.e., V _x is those points where the highest bit of their first coordinate is x. Elements of V ₀ can precede elements of V ₁, but not vice versa. In particular, for any i, j, where 0≤i,j≤n−1, then p(i)≺p(j) if and only if i<j and either $p(j) \not\in V_{0}$ or $p(i) \not\in V_{1}$.

Vertex p(n−2)∈V ₀ is dominated by p(n−1)∈V ₁, and thus there is a path in G from π(p(n−2)) to π(p(n−1)). Let e(1) denote the first edge on this path. Since no other point dominates p(n−2), removing e(1) from E′ does not alter the fact that π preserves the 2-dimensional ordering, with the possible exception that there may be elements p(j)∈V ₀ for which p(j)≺p(n−1) but π(p(j)) no longer precedes π(p(n−1)).

Let U _i ={p(n−2j+1):1≤j≤i}⊂V ₁. By induction, for 1≤i<n/2, suppose one has found i edges E _i ={e(j):1≤j≤i} such that, for any p,q∈V, if $p \not\in V_{0}$ or $q \not\in U_{i}$, then p≺q in V if and only if π(p)≺π(q) in (V′,E′−E _i ). To find edge e(i+1), since p(n−2i−2)∈V ₀ is dominated by p(n−2i−1)∈V ₁−U _i , there is a path τ in (V′,E′−E _i ) from π(p(n−2i−2)) to π(p(n−2i−1)). Let v∈V′ be the first vertex on τ such that there is no path from v to any vertex in π(V ₀). Since the endpoint π(p(n−2i−1)) has this property v must exist, and it cannot be π(p(n−2i−2)) since there must be a path from it to π(p(n−2i))∈π(V ₀). Let e(i+1) denote the incoming edge at v in τ. This edge cannot be on any path leading to π(V ₁−U _i+1) since otherwise π(p(n−2i−2)) would be dominated by such a point, violating the order-embedding property because p(n−2i−2) is not dominated by any point in V ₁−U _i+1. Similarly, it cannot be on any path that starts in π(V ₁) since otherwise such a point would have a path to the predecessor of v in τ, and hence would have a path to the point π(p(n−2i))∈π(V ₀), which is impossible. Therefore e(i+1) is only on paths from π(V ₀) to π(U _i+1). Thus E _i+1=E _i +e(i+1) has the requisite properties for the induction.

Once E _n/2 has been determined, let E″=E′−E _n/2, i.e., n/2 edges have been removed. The dag G″=(V′,E″) has the property that if p≺q and p,q∈V ₀ or p,q∈V ₁, then π(p)≺π(q) in G″. If we further remove all edges in E″ which are not on any path from π(p) to π(q) where p,q∈V ₀ or p,q∈V ₁, then the resulting dag has the same property. Further, it has connected components, one of which contains π(V ₀) and another of which contains π(V ₀). V ₀ and V ₁ are both isomorphic to the b−1 bit-reversal permutation, and thus we can recursively remove edges from their components. The process can be repeated b times, removing n/2 edges at each stage, so there must be at least $bn/2 = \frac{1}{2}|V| \log_{2} |V|$ edges. □

A somewhat similar proof appears in [15] when there is no partial ordering on the points and G is required to be a Manhattan network, i.e., the endpoints of edges differ in exactly one coordinate.