Isotonic Median Regression

Isotonic Median Regression via Scaling

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

Abstract: This paper gives algorithms for determining weighted isotonic median regressions (i.e., isotonic regression using the L₁ metric) satisfying order constraints given by various ordered sets (directed acyclic graphs, aka DAGs). Let n denote the number of vertices. The algorithms show that one can determine the regression for a

rooted tree in Θ(n log n) time,
star, and complete bipartite DAG, in Θ(n) time,
2-dimensional grid in Θ(n log n) time,
bivariate data in arbitrary locations in Θ(n log² n) time,
d-dimensional data in arbitrary locations, d ≥ 3, in Θ(n² log^d n) time

These algorithms improve upon the algorithm of Angelov, Harb, Kannan, and Wang, which applies to all DAGs but takes Θ(nm + n² log n) time, where m is the number of edges. Applying theirs to d-dimensional grids, d ≥ 3, gives Θ(n² log n) time, which is the best know result to date. When there are multiple data values per point, with N total values, the regression for tree and bivariate grid orders can be determined in Θ(n log n + N log log N) time.

Most of the algorithms are based on a scaling approach which exploits the fact that L₁ regression values can always be chosen to be data values. Classification problems known as isotonic separation and isotonic minimal reassignment can also be solved via this approach, as can L₂ isotonic regression (least squares isotonic regression) when only a fixed set of values can occur.

The algorithm for 2-dimensional data with data in arbitrary locations is derived from the 2-dimensional grid algorithm by using a tree to simulate the algorithm on a large grid where locations not corresponding to actual data have weight 0. This can also be used for simulating Spouge, Wan and Wilbur's algorithm for L₂ isotonic regression for a 2-dimensional grid, giving an algorithm for L₂ regression for 2-dimensional data with arbitrary placement taking Θ(n² log n) time.

The algorithm for a DAG which is d-dimensional data in arbitrary locations, d ≥ 3, is based on first creating a new DAG with more vertices but significantly fewer edges in the worst case, and then doing median regression on the new DAG. This approach is quite different than all of the other cases for any metric, since in them the underlying DAG is not changed. This approach had earlier been used for L_∞ isotonic regression. However, at the suggestion of others, I've subsequently revised the L_∞ paper and eliminated the description of the DAG. I've moved the construction of the DAG to a new paper, multidimensional isotonic regression, and show how it can be systematically used for the L₁, L₂, and L_∞ metrics. The DAG construction in this paper will be eliminated when I do the revision of this paper, and a citation will be made to the multidimensional paper. Sorry about the confusion as pieces are being arranged into a better logical order.

Keywords: weighted isotonic median regression, nonparametric, shape constrained, L₁, partial order, DAG, tree, star, bivariate, multidimensional, classification

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, a paper on multivariate isotonic regression and a paper on unimodal regression.