Multidimensional Isotonic Regression

Isotonic Regression for Multiple Independent Variables

Quentin F. Stout
Computer Science and Engineering, University of Michigan

Abstract: This paper gives an approach for computing isotonic regressions at points in multidimensional space, with the ordering given by domination (also known as dimensional ordering, majorization, or matrix ordering). That is, given points p=(p₁,...,p_d) and q=(q₁,...,q_d) in d-dimensional space, q is said to dominate p if p_i ≤ q_i for all 1 ≤i ≤ d. Given a set of n d-dimensional points V = {v₁...v_n} where point v_i has data value y_i and weight w_i, the L_p isotonic regression of the data is a set of values ý_i that minimizes

(Σ {w_i | y_i - ý_i | ^p)^1/p : 1 ≤ i ≤ n } if 1 ≤ p < ∞
max { w_i|y_i - ý_i| : 1 ≤ i ≤ n} if p = ∞ subject to the isotonic constraint that if v_i dominates v_j, then ý_i ≥ ý_j. Typically people are interested in L₂ (least squares), L₁ (median regression), or L_∞ (mini-max error, or the uniform metric).

Note that each dimension need only be a linearly ordered set. For example, one may be height, another shoe size, and a third S < M < L < XL shirt size, where y may correspond to weight. The isotonic requirement is based on the reasonable assumption that if any two of the dimensions are held constant then an increase in the third will increase the expected weight, or, at least, not decrease it.

The paper shows how to efficiently compute the isotonic regression by embedding V into a larger directed acyclic graph (dag) G=(V∪R, E). G is bipartitie, and for all u, v ∈ V, v dominates u iff there is an r ∈ R such that (u,r), (r,v) ∈ E. Further, R and E are only slightly larger than V. Using G, algorithms are given for the L₁ and L₂ metrics which are n/poly-log n faster than previous algorithms. A yet faster algorithm is given for L₁ isotonic regression with unweighted data.

L_∞ is not unique, so algorithms are given for several different variants that have been studied. This includes the strict L_∞ isotonic regression, which is the limit, as p→∞, of L_p isotonic regression. These too are n/poly-log n faster than previous algorithms.

Some of the algorithms exploit the fact that G is not much larger than V, which others use its structure in a more central way. By using the rendezvous vertices R, operations are performed over the transitive closure more efficiently than they can be performed over the transitive closure itself.

This embedding approach had first been used for L_∞ isotonic regression. I've significantly revised that paper, and moved the approach to this paper, extending it to other metrics and to the strict L_∞ isotonic regression.

Keywords: weighted isotonic regression, monotonic, multidimensional, nonparametric, DAG, poset, order-embedding, shape-constrained

Complete paper

Related work: Here is information about the fastest isotonic regression algorithms known to date, for a variety of orderings and metrics.

Here is a paper on L_∞ isotonic regression, also known as minimax regression, one on strict L_∞ isotonic regression, one on L₁isotonic regression, also known as median regression, and one on unimodal regression.