piecewise-linear functions are splines of degree 1, which most spline fitters can be told to do.
for example can be run with
and a smoothing parameter
which you'll have to play with -- see
In Matlab, see
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.
get_residual() will get the actual sum of error^2,
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
For fitting piecewise constants, see
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:
$\qquad$ Linear splines are very sensitive to where the knots are placed
$\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:
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.