Unimodal Regression Algorithm using Isotonic Regression

Unimodal Regression via Prefix Isotonic Regression

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

for the L₂ metric: O(n) time,
for the L₁ metric: O(n log n) time,
for the L_∞ metric: O(n) time, though here the points must be unweighted.

Previous algorithms were solely for the L₂ metric and required Ω(n²) time. All previous algorithms used multiple calls to isotonic regression, and our major contribution is to organize these into a prefix isotonic regression, determining the regression on all initial segments. The prefix approach reduces the total time required by utilizing the solution for one initial segment to solve the next.

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

the value of the regression at x,
the range of x's for which the regression has given value y,

in O(log m) time.

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.