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 log^{d-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 log^{d-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 L_{1} 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 L_{p} isotonic regression. The paper explains the significance of this.
Copyright © 2015-2018 Quentin F. Stout. |