(Years later)
piecewise-linear functions are splines of degree 1, which most spline fitters can be told to do.
scipy.interpolate.UnivariateSpline
for example can be run with k=1
and a smoothing parameter s
,
which you'll have to play with -- see
scipy-interpolation-with-univariate-splines .
In Matlab, see
how-to-choose-knots .
Added: finding optimal knots is not easy, because there can be many local optima.
Instead, you give UnivariateSpline a target s
, sum of error^2,
and let it determine the number of knots.
After fitting, get_residual()
will get the actual sum of error^2,
and get_knots()
the knots.
A small change in s
may change the knots a lot, especially in high noise -- ymmv.
The plot shows fits to a random piecewise-linear function + noise for various s
.
For fitting piecewise constants, see
Step detection.
Can that be used for pw linear ? Don't know; starting off by differentiating noisy data
will increase the noise, wrong.
Other testfunctions, and/or links to papers or code, would be welcome.
A couple of links:
piecewise-linear-regression-with-knots-as-parameters
$\qquad$ Linear splines are very sensitive to where the knots are placed
knot-selection-for-cubic-regression-splines
$\qquad$ This is a tricky problem and most people just select the knots by trial and error.
$\qquad$ One approach which is growing in popularity is to use penalized regression splines instead.
Added March 2014:
Dynamic programming
is a general method for problems with nested subproblems like this:
optimal k lines
= optimal k - 1 lines up to some x
+ cost of the last line x to the end
over x (all x in theory, nearby x in practice)
Dynamic programming is very clever, but can it beat brute force + heuristics for this task ?
See the excellent course notes by Erik Demaine under
MIT 6.006 Intro to algorithms
also google segmented linear regression
also John Henry syndrome.
