Efficient Algorithms for Multidimensional Segmented Regression
This work addresses a fundamental problem in data analysis for applications like spatial modeling, but it is incremental as it extends existing segmented regression methods to multiple dimensions with efficiency improvements.
The authors tackled the problem of multidimensional segmented regression, where a piecewise linear function on unknown rectangles must be recovered from noisy samples, and they developed the first sample and computationally efficient algorithm for any fixed dimension, showing competitive or superior performance to state-of-the-art heuristics in experiments.
We study the fundamental problem of fixed design {\em multidimensional segmented regression}: Given noisy samples from a function $f$, promised to be piecewise linear on an unknown set of $k$ rectangles, we want to recover $f$ up to a desired accuracy in mean-squared error. We provide the first sample and computationally efficient algorithm for this problem in any fixed dimension. Our algorithm relies on a simple iterative merging approach, which is novel in the multidimensional setting. Our experimental evaluation on both synthetic and real datasets shows that our algorithm is competitive and in some cases outperforms state-of-the-art heuristics. Code of our implementation is available at \url{https://github.com/avoloshinov/multidimensional-segmented-regression}.