Optimal Algorithms for Unimodal Regression
Quentin F. Stout · 2000
This paper gives optimal algorithms for determining realvalued 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 a form of shape-constrained nonparametric regression, closely related to isotonic regression. For the L 2 metric our algorithm requires only \\Theta(n) time for regression on n points, while for the L 1 metric it requires \\Theta(n log n) time. Previous algorithms only considered the L 2 metric and required \\Omega\\Gamma n 2 ) time. All previous algorithms used multiple calls to isotonic regression, and our major contribution is to organize these into a prefix isotonic regression, whereby one computes the regression on all initial segments. The prefix approach utilizes the solution for one initial segment to aid in the solution of the next, which considerably reduces the total time required. Our prefix isotonic regression algorithm for t...