Segmented regression is a statistical method that approximates a function f by a piecewise function f using noisy data samples. Min-ϵ approaches aim to reduce the regression function’s mean squared error (MSE) for a given number of kseg- ments. An optimal solution for min-ϵsegmented regression is found in O(n2) time (Bai & Perron, 1998; Yamamoto & Perron, 2013) for nsamples. For large datasets, current heuristics improve time complexity to O(nlog n) (Acharya et al., 2016) but can result in large errors, especially when ex- actly ksegments are used. We present a method for min-ϵsegmented regression that combines the scalability of top existing heuristic solutions with a statistical efficiency similar to the optimal so- lution. This is achieved by using a new method to merge an initial set of segments using precom- puted matrices from samples, allowing both merg- ing and error calculation in constant time. Our approach, using the same samples and parameter k, produces segments with up to 1,000×lower MSE compared to Acharya et al. (2016) in about 100×less runtime on datasets over 104 samples.
