Nearly-Isotonic Regression

We consider the problem of approximating a sequence of data points with a “nearly-isotonic,” or nearly-monotone function. This is formulated as a convex optimization problem that yields a family of solutions, with one extreme member being the standard isotonic regression fit. We devise a simple algorithm to solve for the path of solutions, which can be viewed as a modified version of the well-known pool adjacent violators algorithm, and computes the entire path in O(n log n) operations (n being the number of data points). In practice, the intermediate fits can be used to examine the assumption of monotonicity. Nearly-isotonic regression admits a nice property in terms of its degrees of freedom: at any point along the path, the number of joined pieces in the solution is an unbiased estimate of its degrees of freedom. We also extend the ideas to provide “nearly-convex” approximations.