Re: fixed points piecewise-linear fitting

[Ben Abbott]

On Mar 17, 2012, at 7:43 AM, Sergei Steshenko wrote:

> Hello,
> 
> strictly speaking, it's not an Octave-specific question, but an algorithmic 
> one.
> 
> Suppose there is a measured function Y(X). In Octave terms X is a vector with 
> N elements.
> 
> Suppose there are fixed points Xf such that
> 
> X(1) <= Xf(1)
> Xf(end) <= X(end).
> 
> The Xf points are more sparse than X.
> 
> 
> The Xf points are fixed, i.e. one can't change them as he/she pleases.
> 
> The goal is to find piecewise-linear function Yf(Xf) which best fits Y(X).
> 
> I.e. for each two Xf(k), Xf(k+1) pair of points to find a piece of straight 
> line defined by Yf(k), Yf(k+1)pair of points such that the whole Yf fits Y 
> pretty well.
> 
> Best fitting I'm interested in is according to minimum of sum(abs(Y - 
> Yf_interpolated)). The Yf_interpolated is linear interpolated Yf on X, so 
> dimensions of Y and Yf_interpolated match.
> 
> 
> I did some quick web searching and my impression is that there is no 
> universally adopted algorithm for this task, but there is a number solutions, 
> including some for R-language.
> 
> I myself wrote a straightforward brute force implementation which works 
> pretty well and acceptably fast for me.
> 
> Anyway, I'm writing this Email in the hope to be educated by the community - 
> maybe there are already more elegant wheels than the one I've invented.
> 
> Thanks,
>   Sergei.


I don't have an answer, but if I understand what you're looking for, I'd be 
interested in a solution as well.

You desire solution for Yf that produces a least squares error between Y and 
Yf_interpolated?

Where ...

        Yf_interpolated = interp1 (Xf, Yf, X, "linear");

... and you'd like the solution that minimizes ...

        sum ((Yf_interpolated - Y).^2)

A linear solution would work. It would also be nice to extend the solution to 
allow for a piece-wise continuous quadratic solution. It would also be 
beneficial to allow the order of the polynomial pieces to be specified.

I think this would make a nice addition to piece-wise polynomial functions 
already included in Octave.

If you like the idea, please enter this on the task list.

        https://savannah.gnu.org/task/?group=octave

... and attached your current version so that those interested can suggest 
changes.

Ben