Unimodal regression via prefix isotonic regression

This paper gives algorithms for determining real-valued 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 our algorithm for the L₂ metric requires only Θ(n) time, while for the L₁ metric it requires time. For unweighted points our algorithm for the L_∞ metric requires only Θ(n) time. All of these times are optimal. Previous algorithms were 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.