Quentin F. Stout

Computer Science and Engineering, University of Michigan

**Abstract:**
This paper gives algorithms for determining
L_{∞} isotonic regressions satisfying order constraints
on a partially ordered set, specified via a directed acyclic graph (DAG).
At each vertex there is a value and a nonnegative weight.
We examine an algorithm's time and properties of the regressions it
produces.
The reason that the properties are examined is because the nonuniqueness
of the isotonic regression can result in some undesirable behavior.

For a DAG with *n* vertices and *m* edges we give an
algorithm taking Θ(m log n) time.
However, this algorithm is not monotonic, in that there can be functions
f and g where pointwise f ≥ g, but the isotonic regression produced
for f is not pointwise ≥ the regression produced for g.
Further, it is based on parametric search, which is infeasible.

Algorithms are also given to determine unimodal regression for an undirected tree, for isotonic regressions where the regression values must come from a specified set, and for isotonic regressions when the number of different weights, or number of different values, is much smaller than the number of vertices. An algorithm is also given for isotonic regression on a rooted tree, where the value of a parent must be the largest value of its children. We call this ``river isotonic regression'' since it is similar to the naming convention for rivers.

The fastest algorithm mentioned above can produce Max, the regression
which is pointwise the largest of any L_{∞} isotonic
regression, and can produce Min, the pointwise minimum.
In addition to the prefix algorithm, other regressions considered
are ``basic'' and ``strict''. The former is the most commonly
studied one, but people have rarely addressed the fact that it
is nontrivial to compute for weighted data.
The prefix approach simplifies this somewhat.
The latter is discussed more thoroughly in the paper on
strict L_{∞} isotonic regression.
Strict regression is the "best best" L_{∞} isotonic regression.
It is the limit, as p → ∞, of L_{p} isotonic regression.
It has a strong property concerning the number of vertices with large
regression errors (see the paper for a precise statement).
The prefix approach has a somewhat weaker property in that it minimizes the
number of vertices with maximal error.
The basic approach also has this property.
At the other end of the spectrum, at any vertex, one or both of
Max and Min have the worst error among all isotonic regressions.

**Keywords:** isotonic regression, unimodal regression, monotonic,
nonparametric, shape constrained, prefix isotonic regression,
minimax error, L_{∞}, uniform metric, Chebyshev metric,
partial order, DAG, linear order, tree order

**Complete paper**.
This is a major revision of an earlier version from 2008.
The prior approach to multidimensional data, based on constructing a
new DAG which has a more succinct representation of the ordering,
has been moved to
Isotonic Regression for Multiple Independent Variables, which also applies the approach to L_{1} and
L_{2} metrics.

**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 L_{1} isotonic regression (also known as isotonic median regression),
isotonic regression for multiple independent variables,
isotonic regression with a fixed number of level sets, and
unimodal regression.
The paper on L_{1} isotonic regression also includes new algorithms
for L_{p} isotonic regression, 1 < p < ∞.
These are based on using a sequence of L_{1} binary-valued isotonic
regressions.
For L_{2} several of these improve upon prior results, which is
somewhat surprising since it is the case that has been studied the most.

Copyright © 2008-2016 Quentin F. Stout. |