Fitting and analyzing data with convex-area-wise linear regression models

This paper introduces a new type of regression methodology named as Convex-Area-Wise Linear Regression(CALR), which separates given datasets by disjoint convex areas and fits different linear regression models for different areas. This regression model is highly interpretable for its close-form local models and boundaries, and it is able to interpolate any given finite datasets even when the underlying relationship between explanatory and response variables are non-linear and discontinuous. In order to construct CALR models for given datasets, accurate algorithms and an incremental algorithm are proposed under different assumptions. The analysis of correctness and time complexity of the algorithms are given, indicating that the problem can be solved in $$o(n^2)$$ o ( n 2 ) time accurately when the input datasets have some special features, or be solved in $$O(T(n_s)+n(M+d^2))$$ O ( T ( n s ) + n ( M + d 2 ) ) time incrementally using an $$n_s$$ n s -size initial subset to construct initial accurate model.