Efficient computation of locally monotonic regression

Locally monotonic regression provides a way of smoothing signals under the smoothness criterion of local monotonicity, which sets a restriction on how often a signal may change trend (increasing to decreasing, or vice versa). So far, the applicability of locally monotonic regression has been limited by the high computational costs of the available algorithms that compute them. We present a powerful theoretical result about the nature of these regressions. As an application, we give an algorithm for the computation of lomo-3 regressions, which reduces the complexity of the task, from exponential to polynomial.