Abstract
We present approximation and exact algorithms for piecewise regression of univariate and bivariate data using fixeddegree polynomials. Specifically, given a set S of n data points (š±ā, yā),ā¦ , (š±_n, y_n) ā ā^d Ć ā where d ā {1,2}, the goal is to segment š±_iās into some (arbitrary) number of disjoint pieces Pā, ā¦ , P_k, where each piece P_j is associated with a fixeddegree polynomial f_j: ā^d ā ā, to minimize the total loss function Ī» k + ā_{i = 1}āæ (y_i  f(š±_i))Ā², where Ī» ā„ 0 is a regularization term that penalizes model complexity (number of pieces) and f: āØ_{j = 1}^k P_j ā ā is the piecewise polynomial function defined as f_{P_j} = f_j. The pieces Pā, ā¦ , P_k are disjoint intervals of ā in the case of univariate data and disjoint axisaligned rectangles in the case of bivariate data. Our error approximation allows use of any fixeddegree polynomial, not just linear functions.
Our main results are the following. For univariate data, we present a (1 + Īµ)approximation algorithm with time complexity O(n/(Īµ) log 1/(Īµ)), assuming that data is presented in sorted order of x_iās. For bivariate data, we present three results: a subexponential exact algorithm with running time n^{O(ān)}; a polynomialtime constantapproximation algorithm; and a quasipolynomial time approximation scheme (QPTAS). The bivariate case is believed to be NPhard in the folklore but we could not find a published record in the literature, so in this paper we also present a hardness proof for completeness.
BibTeX  Entry
@InProceedings{lokshtanov_et_al:LIPIcs.ESA.2021.63,
author = {Lokshtanov, Daniel and Suri, Subhash and Xue, Jie},
title = {{Efficient Algorithms for Least Square Piecewise Polynomial Regression}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {63:163:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14644},
URN = {urn:nbn:de:0030drops146443},
doi = {10.4230/LIPIcs.ESA.2021.63},
annote = {Keywords: regression analysis, piecewise polynomial, least square error}
}
Keywords: 

regression analysis, piecewise polynomial, least square error 
Collection: 

29th Annual European Symposium on Algorithms (ESA 2021) 
Issue Date: 

2021 
Date of publication: 

31.08.2021 