Slope change detection seeks to identify changes in the trends of time-ordered signals. We study the problem of fitting a multidimensional time series by continuous piecewise-linear functions with a common, continuously varying breakpoint and unrestricted slopes. We consider both the dense setting, in which every dimension may change slope, and the sparse setting, in which at most a specified number of dimensions may change slope.
Although the resulting optimization problems are nonconvex mixed-integer nonlinear programs and may have irrational optimal solutions even for rational input data, we prove that all six variants, corresponding to the absolute-error, least-squares, and maximum-error losses in the dense and sparse settings, are exactly solvable in polynomial time. In particular, optimal solutions admit polynomial-size algebraic representations and can be computed with polynomial bit complexity.
For the least-squares loss, we obtain especially efficient algorithms with computational complexities of O(JT) in the dense setting and O(J²T log J) in the sparse setting, where T denotes the number of time points and J denotes the number of dimensions.
We implement these least-squares algorithms and evaluate them on simulated data and on three real-world multidimensional time series, namely, regional surface temperatures (ERA5), hand-tracking data from a mixed-reality headset (HoloAssist), and turbofan engine sensor data (NASA C-MAPSS).
The dense algorithm solves instances with up to 100,000 dimensions and 100 time points, corresponding to 10 million observations, in less than 0.1 seconds on a laptop, while the sparse algorithm solves instances with about 1,000 dimensions and up to 240 time points in under a second.
Compared with a mixed-integer nonlinear programming (MINLP) formulation solved by Gurobi on the same instances, our algorithms are several orders of magnitude faster (approximately 8,900 to 3.4 million times) on those instances where Gurobi terminates within its default optimality tolerance of a 0.01 percent optimality gap. On larger instances, Gurobi frequently reaches a 10,000-second time limit with substantial optimality gaps.