Stoffelche
04-07-2008, 06:53 AM
I have a time series for which I want to find an approximation function consisting of piece-wise linear approximations which are derived by least square method but with the additional constraint to be continously fitted.
Given observation points 1...N and a set of segmentation points s1,....,sn with s1 = 1 sn = N and si > s(i-1), n < N: For each interval [si,s(i+1] I search a linear approximation which is continously fitted to its left and right neighbor.
For a given set [s1...sn] I was able to solve this problem analytically exactly and hence numerically as solution of a set of sn+1 linear equations for the sn gradients mi and the starting point b1 (b2-bn are not free due to the continuation constraint).
But now for a given number of segments I want to find the best segmentation points: For example with N = 20 and n = 5
I can calculate the total "cost" for a solution [1,5,10,15,20] and compare it to a solution [1,7,10,13,20] both having 4 line segments. Of all these possible segmentation with n = 5 I want to find the best one.
This is kind of a multidimensional minimization problem but with a combinatorical constraint. N typically is of magnitude 100 - 200, whereas n could be between 1 - 20.
Any ideas on approaching this problem are highly welcome.
Thanks, Stefan
Given observation points 1...N and a set of segmentation points s1,....,sn with s1 = 1 sn = N and si > s(i-1), n < N: For each interval [si,s(i+1] I search a linear approximation which is continously fitted to its left and right neighbor.
For a given set [s1...sn] I was able to solve this problem analytically exactly and hence numerically as solution of a set of sn+1 linear equations for the sn gradients mi and the starting point b1 (b2-bn are not free due to the continuation constraint).
But now for a given number of segments I want to find the best segmentation points: For example with N = 20 and n = 5
I can calculate the total "cost" for a solution [1,5,10,15,20] and compare it to a solution [1,7,10,13,20] both having 4 line segments. Of all these possible segmentation with n = 5 I want to find the best one.
This is kind of a multidimensional minimization problem but with a combinatorical constraint. N typically is of magnitude 100 - 200, whereas n could be between 1 - 20.
Any ideas on approaching this problem are highly welcome.
Thanks, Stefan