[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: fixed points piecewise-linear fitting
From: |
Sergei Steshenko |
Subject: |
Re: fixed points piecewise-linear fitting |
Date: |
Sat, 17 Mar 2012 09:32:08 -0700 (PDT) |
----- Original Message -----
> From: Ben Abbott <address@hidden>
> To: Sergei Steshenko <address@hidden>
> Cc: help-octave Octave <address@hidden>
> Sent: Saturday, March 17, 2012 5:03 PM
> Subject: Re: fixed points piecewise-linear fitting
>
> 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".
My solution is poor man's brute force one.
I.e. I have a pretty good Yf initial approximation, and I have Y_step.
I have an outer loop which is iterations and an inner loop on 'k'
For each Yf(k) I try (Yf(k) + Y_step) and (Yf(k) - Y_step) and check whether my
sum(abs(Yf_interpolated - Y)) becomes smaller or not.
If it is smaller, Yf(k) is replaced with Yf(k) +/- Y_step - depending on which
of them gives smaller sum(abs(Yf_interpolated - Y)).
The outer loop is run until there is no improvement in sum(abs(Yf_interpolated
- Y)) or until number of iterations is exhausted - in my case very good fitting
is not critical. In my case I never reach iterations limit - I intentionally
make it hight; for my data I think I never have more than 200 iterations.
In my case length(Yf) == length(Xf) == 64.
Of course, I have no mathematical proof that I am reaching the global minimum
of sum(abs(Yf_interpolated - Y)). Typically sum(abs(Yf_interpolated - Y))
becomes about 2 times smaller than it was for initial Yf, i.e. in practice I
see that my algorithm improves fitting.
My dirty little secret is that probably in my case initial Yf approximation
would do :).
Regards,
Sergei.
>
- fixed points piecewise-linear fitting, Sergei Steshenko, 2012/03/17
- Re: fixed points piecewise-linear fitting, Juan Pablo Carbajal, 2012/03/17
- Re: fixed points piecewise-linear fitting, Ben Abbott, 2012/03/17
- Re: fixed points piecewise-linear fitting,
Sergei Steshenko <=
- Re: fixed points piecewise-linear fitting, Ben Abbott, 2012/03/17
- Re: fixed points piecewise-linear fitting, Sergei Steshenko, 2012/03/17
- Re: fixed points piecewise-linear fitting, Ben Abbott, 2012/03/17
- Re: fixed points piecewise-linear fitting, Juan Pablo Carbajal, 2012/03/17
- Re: fixed points piecewise-linear fitting, c., 2012/03/18
- Re: fixed points piecewise-linear fitting, Sergei Steshenko, 2012/03/18
- Re: fixed points piecewise-linear fitting, c., 2012/03/18
- Re: fixed points piecewise-linear fitting, Sergei Steshenko, 2012/03/18
- Re: fixed points piecewise-linear fitting, c., 2012/03/18
- Re: fixed points piecewise-linear fitting, Ben Abbott, 2012/03/18