L Isotonic Regression for Linear, Multidimensional, and Tree Orders

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


Abstract: Algorithms are given for determining L isotonic regression of weighted data where the independent set is n vertices in multidimensional space or in a rooted tree. For a linear order, or, more generally, a grid in multidimensional space, an optimal algorithm is given, taking Θ(n) time. For vertices at arbitrary locations in d-dimensional space a Θ(n logd-1 n) algorithm employs iterative sorting to yield the functionality of a multidimensional structure while using only Θ(n) space. A Θ(n) time algorithm is also given for rooted trees. These improve upon previous algorithms by Ω(log n). The algorithms utilize a new non-constructive feasibility test on a rendezvous graph, with bounded error envelopes at each vertex.

The same techniques can be used to solve other multidimensional problems involving domination (component-wise ordering)such as the empirical cumulative distribution function. It can also produce the transitive closure in Θ(n logd-1 n + K) time, where K is the number of edges in the transitive closure.

Keywords: L infinity isotonic regression, monotonic, shape constrained nonparametric regression, linear order, chain order, multidimensional grid, tree order, rendezvous graph, domination, coordinate-wise ordering, minimax error, uniform metric, Chebyshev metric

Complete paper. arXiv 1507.02226

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

Here are papers on L1 isotonic regression (also known as isotonic median regression), isotonic regression for multiple independent variables, L isotonic regression for arbirary dags; isotonic regression with a fixed number of level sets, and unimodal regression. Here is a paper on "strict" L isotonic regression, which is the limit, as p → ∞, of Lp isotonic regression. The paper explains the significance of this.

Quentin's Home Copyright © 2015-2017 Quentin F. Stout.