Quentin F. Stout
University of Michigan
Abstract: This paper gives optimal algorithms for determining univariate unimodal regressions, that is, for determining the optimal regression which is increasing and then decreasing. Such regressions arise in a wide variety of applications. They are shape-constrained nonparametric regressions, closely related to isotonic regression.
For unimodal regression on n weighted points given in increasing abscissa order, the algorithms require only
We also provide algorithms for pointwise evaluations. That is, after the prefix isotonic regressions have been constructed, then for the isotonic regression on the first m values, 0 < m ≤ n, one can determine
Note: for weighted points, L∞ isotonic and unimodal regression can be accomplished in O(n log n) time. However, the algorithm is somewhat more complicated and will be published in a subsequent paper, along with some other extensions.
Keywords: unimodal regression, isotonic regression, median regression, minimax, least squares, monotonic, prefix operation, scan, persistent data structure, pool adjacent violators (PAV)Complete paper. A preliminary version of these results appeared in ``Optimal algorithms for unimodal regression'', Computing Science and Statistics 32 (2002).
My interest in this problem arose from its use in adaptive sampling designs for dose-response optimization in phase I/II clinical trial.
![]() |
Copyright © 2005-2008 Quentin F. Stout |