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 an overview of my work on shape constrained regression (isotonic, unimodal, step), and here is information about the fastest (in O-notation) isotonic regression algorithms known to date, for a variety of orderings and metrics.
|
Copyright © 2015-2024 Quentin F. Stout. |