Re: fixed points piecewise-linear fitting

[Ben Abbott]

On Mar 17, 2012, at 12:32 PM, Sergei Steshenko wrote:

> From: Ben Abbott <address@hidden>
>> 
>> 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
> 
> Well, in my case it's just sum(abs(Yf_interpolated - Y)), not 
> sum((Yf_interpolated - Y).^2).
> 
> I don't understand your "A linear solution would work".

I mean that linear least squares can be used to solve this problem.

Ben