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 nn weighted points our algorithm for the L2L2 metric requires only Θ(n)Θ(n) time, while for the L1L1 metric it requires Θ(nlogn) time. For unweighted points our algorithm for the L∞L∞ metric requires only Θ(n)Θ(n) time. All of these times are optimal. Previous algorithms were for the L2L2 metric and required Ω(n2)Ω(n2) 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.