Unimodal Regression Algorithm using Isotonic Regression

Unimodal Regression via Prefix Isotonic Regression

Abstract: This paper gives 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.

For weighted points, L_∞ isotonic and unimodal regression can be accomplished in O(n log n) time. However, the algorithm is slightly more complicated and appears in Algorithms for L_∞ Isotonic Regression, along with some other extensions.

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. The prefix algorithm is also useful when one is performing isotonic regression for an on-going time series, since it allows one to add new data with only a constant expected amount of time per new data point (for the L₂ metric).

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.

Keywords: unimodal regression, isotonic regression, median regression, umbrella ordering, minimax, least squares, monotonic, prefix operation, scan, persistent data structure, pool adjacent violators (PAV)

Complete paper. This paper appears in Computational Statistics and Data Analysis 53 (2008), p. 289-297. doi:10.1016/j.csda.2008.08.005 It was first posted on the web and submitted in 2003, but a series of absurd delays occured (one of them due to me). A preliminary version of these results appeared in ``Optimal algorithms for unimodal regression'', Computing Science and Statistics 32 (2000).

Related work: My interest in this problem arose from its use in adaptive sampling designs for dose-response optimization in phase I/II clinical trial.
Here is information on the fastest isotonic regression algorithms known to date. Here is a paper on L₁ isotonic regression, also known as isotonic median regression, one on L_∞ isotonic regression, also known as minimax, uniform, or Chebyshev isotonic regression, and one on multidimensional isotonic regression.