Linear-Time Segmented Regression

We present a linear-time algorithm for min-$ϵ$ segmented regression, which fits a piecewise-linear function with a prescribed number of segments $k$ to a given dataset while minimizing the residual sum of squares. Such learning settings arise in many applications, including the general compression of time series data, the detection of economic indicators, or the identification of abrupt shifts in climate data. Exact solutions can be obtained via dynamic programming. However, the runtime scales quadratically with the dataset size. Recently, a greedy approach based on merging and subsequently fine-tuning segments has been proposed, which achieves a log-linear runtime in the number of data points. In this work, we propose an approach based on a greedy splitting and fine-tuning of segments, which exhibits a linear runtime with respect to the dataset size. In our experiments, we assess the runtime behavior and the achieved quality of our scheme and compare the results with dynamic programming and the recently proposed greedy approach, using both synthetic and real-world data. Our results indicate that our method scales linearly in practice, runs faster than the competing heuristic, and matches the exact solutions more often than the other approximation scheme.