http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497
MATLAB Central Newsreader  Piecewiese linear approximation function with a minimal largest error dev.
Feed for thread: Piecewiese linear approximation function with a minimal largest error dev.
enus
©19942015 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Tue, 01 Jan 2013 08:57:07 +0000
Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894600
Deyan Levski
Hello everyone,<br>
<br>
In my practice I have faced a problem where I need to perform a piecewise linear approximation of a certain mathematical function for the use in a video application. <br>
<br>
Due to some hardware restrictions I will need to split the function in a number of uniform segments and then calculate the approximation points accordingly, but in such a way that the largest error is minimized (minmax sense).<br>
<br>
Are there any existing functions that can help me with this task, I've looked at interp1 but I am afraid it is not what I am really looking for? I will be very happy if someone can guide me with some ideas or literature about this mathematical problem.<br>
<br>
<br>
Best Regards,<br>
Deyan

Tue, 01 Jan 2013 09:48:07 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894602
Bruno Luong
"Deyan Levski" <remove.this@gmail.com> wrote in message <kbu8d3$gcr$1@newscl01ah.mathworks.com>...<br>
> Hello everyone,<br>
> <br>
> In my practice I have faced a problem where I need to perform a piecewise linear approximation of a certain mathematical function for the use in a video application. <br>
> <br>
> Due to some hardware restrictions I will need to split the function in a number of uniform segments and then calculate the approximation points accordingly, but in such a way that the largest error is minimized (minmax sense).<br>
> <br>
> Are there any existing functions that can help me with this task, I've looked at interp1 but I am afraid it is not what I am really looking for? I will be very happy if someone can guide me with some ideas or literature about this mathematical problem.<br>
><br>
<br>
This problem can be formulated as linear programming, that can be solved with LINPROG.<br>
<br>
Bruno

Tue, 01 Jan 2013 14:07:08 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894611
Matt J
"Deyan Levski" <remove.this@gmail.com> wrote in message <kbu8d3$gcr$1@newscl01ah.mathworks.com>...<br>
><br>
> Due to some hardware restrictions I will need to split the function in a number of uniform segments and then calculate the approximation points accordingly, but in such a way that the largest error is minimized (minmax sense).<br>
> <br>
> Are there any existing functions that can help me with this task, I've looked at interp1 but I am afraid it is not what I am really looking for? I will be very happy if someone can guide me with some ideas or literature about this mathematical problem.<br>
================<br>
<br>
If you have Optimization Toolbox, then fminimax() might be applicable

Tue, 01 Jan 2013 17:46:08 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894618
Roger Stafford
"Deyan Levski" <remove.this@gmail.com> wrote in message <kbu8d3$gcr$1@newscl01ah.mathworks.com>...<br>
> In my practice I have faced a problem where I need to perform a piecewise linear approximation of a certain mathematical function for the use in a video application. <br>
> <br>
> Due to some hardware restrictions I will need to split the function in a number of uniform segments and then calculate the approximation points accordingly, but in such a way that the largest error is minimized (minmax sense).<br>
        <br>
As I see it, you face a difficulty in this problem. Matlab procedures which are intended to find minimum solutions require a finite set of adjustable parameters, in this case presumably the locations of all the endpoints of your line segments and their heights, and a function of these to be minimized which gives the maximum difference between the segments and your mathematical function. Unfortunately such a difference function requires the solution of another optimization problem, namely the maximum difference between your function and the underlying line segments, not at, but in between, the endpoints. To solve this directly would require not only knowing the derivative of the mathematical function but its inverse so that you can locate such maximal points easily. Otherwise you are faced with an optimization problem within another optimization problem. I hope you have a nice <br>
simple mathematical function to be fitted. Could you tell us what it is? <br>
<br>
Perhaps I have overstated the difficulties here. You might try to have some fixed number of uniformly spaced points between each pair of line segment endpoints and simply evaluate the above difference at each of these inbetween points so as to approximate the maximum you are trying to obtain. That might work but it has the flavor of a process that could be very timeconsuming computationwise.<br>
<br>
Roger Stafford

Wed, 02 Jan 2013 07:13:08 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894640
Deyan Levski
"Roger Stafford" wrote in message <kbv7d0$obt$1@newscl01ah.mathworks.com>...<br>
> "Deyan Levski" <remove.this@gmail.com> wrote in message <kbu8d3$gcr$1@newscl01ah.mathworks.com>...<br>
> > In my practice I have faced a problem where I need to perform a piecewise linear approximation of a certain mathematical function for the use in a video application. <br>
> > <br>
> > Due to some hardware restrictions I will need to split the function in a number of uniform segments and then calculate the approximation points accordingly, but in such a way that the largest error is minimized (minmax sense).<br>
>         <br>
> As I see it, you face a difficulty in this problem. Matlab procedures which are intended to find minimum solutions require a finite set of adjustable parameters, in this case presumably the locations of all the endpoints of your line segments and their heights, and a function of these to be minimized which gives the maximum difference between the segments and your mathematical function. Unfortunately such a difference function requires the solution of another optimization problem, namely the maximum difference between your function and the underlying line segments, not at, but in between, the endpoints. To solve this directly would require not only knowing the derivative of the mathematical function but its inverse so that you can locate such maximal points easily. Otherwise you are faced with an optimization problem within another optimization problem. I hope you have a nice <br>
> simple mathematical function to be fitted. Could you tell us what it is? <br>
> <br>
> Perhaps I have overstated the difficulties here. You might try to have some fixed number of uniformly spaced points between each pair of line segment endpoints and simply evaluate the above difference at each of these inbetween points so as to approximate the maximum you are trying to obtain. That might work but it has the flavor of a process that could be very timeconsuming computationwise.<br>
> <br>
> Roger Stafford<br>
<br>
Thanks Roger! Yes you have gotten me right, I want to have a fixed number of uniformly spaced segments and then evaluate the difference at each point (positions) such that the the approximation error is lowest. The function which I need to approximate is cos((pi/2)*log(x)). At this stage I would not be bothered by slow computations as long as I can make it compute correctly.<br>
<br>
Kind Regards,<br>
Deyan

Wed, 02 Jan 2013 07:41:08 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894642
Bruno Luong
"Deyan Levski" <remove.this@gmail.com> wrote in message <kc0mm4$oem$1@newscl01ah.mathworks.com>...<br>
<br>
> <br>
> Thanks Roger! Yes you have gotten me right, I want to have a fixed number of uniformly spaced segments and then evaluate the difference at each point (positions) such that the the approximation error is lowest. The function which I need to approximate is cos((pi/2)*log(x)). At this stage I would not be bothered by slow computations as long as I can make it compute correctly.<br>
<br>
As I told earlier, if the knot are fixed (regardless they are is equidistant or not) , this problem is a firstdegree splineapproximation (piecewise linear) of l_infinity norm, and can be formulated as linear programming.<br>
<br>
Bruno

Wed, 02 Jan 2013 07:48:07 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894644
Bruno Luong
BTW the leastsquare (l2) minimization of linearpicewise function can be achieved with my tool:<br>
<a href="http://www.mathworks.com/matlabcentral/fileexchange/25872freeknotsplineapproximation">http://www.mathworks.com/matlabcentral/fileexchange/25872freeknotsplineapproximation</a><br>
<br>
Bruno

Wed, 02 Jan 2013 08:48:09 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894652
Roger Stafford
"Deyan Levski" <remove.this@gmail.com> wrote in message <kc0mm4$oem$1@newscl01ah.mathworks.com>...<br>
> Thanks Roger! Yes you have gotten me right, I want to have a fixed number of uniformly spaced segments and then evaluate the difference at each point (positions) such that the the approximation error is lowest. The function which I need to approximate is cos((pi/2)*log(x)). .......<br>
        <br>
I had not caught the word 'uniform' in your original phrase "a number of uniform segments". I thought you wanted the x values of the segment endpoints to be variable as well as their y values. With uniform spacing in the function you describe it will probably be the first segment or so on the left side that will determine the minimum value you seek. The remaining linear piecewise fitting can be done in numerous ways without altering this minimum and in that sense the problem will not yield a unique solution. This is because the points of local maximum curvature of your defined function decrease as you increase x and it is curvature that will determine maximum error in fitting linear segments to the curve, the greater the curvature the greater the maximum error has to be for linear segments of fixed x width.<br>
<br>
To put it in another way, if the xwidths of the line segments are allowed to be variable and therefore smaller on the left side than those to the right, you would get a smaller overall minimum value of the maximum error  that is to say a better fit  but you will also face a more difficult problem in finding this minimum.<br>
<br>
The uniform spacing I was referring to in my previous article had to do with placing a fairly large number of intermediate uniformly spaced points between each pair of segment endpoints just for the purpose of determining an approximate maximum difference between the line segment and the curve, as opposed to solving for the point where the derivative is equal to the segment's slope.<br>
<br>
I still think this method with numerous intermediate points might be a good way to solve the harder problem with nonuniform spacing of line segment endpoints' xwidths permitted. With uniform spacing of line segment endpoints the problem becomes relatively easy but rather unsatisfactory in its arbitrariness.<br>
<br>
Roger Stafford

Wed, 02 Jan 2013 09:06:08 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894654
Roger Stafford
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kc0oak$dm$1@newscl01ah.mathworks.com>...<br>
> As I told earlier, if the knot are fixed (regardless they are is equidistant or not) , this problem is a firstdegree splineapproximation (piecewise linear) of l_infinity norm, and can be formulated as linear programming.<br>
> <br>
> Bruno<br>
        <br>
Bruno, we seem to be looking at Deyan's problem from two different aspects. You are saying that given an L_infinity norm the problem can be solved as a linear programming problem and you may well be right. I have been saying that its primary difficulty lies in calculating this L_infinity norm since it involves not just the differences at the segment endpoints which would involve a finite number of variables but the differences occurring between these endpoints where an infinite continuum of points are involved. That is why I spoke of the inverse of derivatives or numerous intermediate points. Please correct me if I am mistaken.<br>
<br>
Roger Stafford

Wed, 02 Jan 2013 10:43:07 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894658
Bruno Luong
"Roger Stafford" wrote in message <kc0ta0$ftf$1@newscl01ah.mathworks.com>...<br>
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kc0oak$dm$1@newscl01ah.mathworks.com>...<br>
> > As I told earlier, if the knot are fixed (regardless they are is equidistant or not) , this problem is a firstdegree splineapproximation (piecewise linear) of l_infinity norm, and can be formulated as linear programming.<br>
> > <br>
> > Bruno<br>
>         <br>
> Bruno, we seem to be looking at Deyan's problem from two different aspects. You are saying that given an L_infinity norm the problem can be solved as a linear programming problem and you may well be right. I have been saying that its primary difficulty lies in calculating this L_infinity norm since it involves not just the differences at the segment endpoints which would involve a finite number of variables but the differences occurring between these endpoints where an infinite continuum of points are involved. That is why I spoke of the inverse of derivatives or numerous intermediate points. Please correct me if I am mistaken.<br>
<br>
Right Roger, I assume the function to be approximated is somehow discretized. <br>
<br>
Let see if Deyan can confirm if he absolutely wants a continuous version or not.<br>
<br>
Bruno

Wed, 02 Jan 2013 14:08:07 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894670
Deyan Levski
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <br>
> > > <br>
> > > Bruno<br>
> >         <br>
> > Bruno, we seem to be looking at Deyan's problem from two different........<br>
><br>
..... Right Roger, I assume the function to be approximated is somehow discretized. <br>
> <br>
> Let see if Deyan can confirm if he absolutely wants a continuous version or not.<br>
> <br>
> Bruno<br>
<br>
Thanks Bruno and Roger for all your discussions over my problem. Indeed the function to be approximated is discretized. The function's ends are finite and lie between one and two (1<X<2) and in addition the input accuracy should be enough to be within 16 bits of resolution. So far I am not quite confident with all the maths standing behind firstorder spline approximations, and I am hoping to soon find a solution to be able to continue over my work.

Wed, 02 Jan 2013 18:43:09 +0000
Re: Piecewiese linear approximation function with a minimal largest error dev.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/325497#894705
Bruno Luong
"Deyan Levski" <remove.this@gmail.com> wrote in message <br>
> <br>
> Thanks Bruno and Roger for all your discussions over my problem. Indeed the function to be approximated is discretized. The function's ends are finite and lie between one and two (1<X<2) and in addition the input accuracy should be enough to be within 16 bits of resolution. So far I am not quite confident with all the maths standing behind firstorder spline approximations, and I am hoping to soon find a solution to be able to continue over my work.<br>
<br>
Let define:<br>
f(x) := cos((pi/2)*log(x))<br>
<br>
A discretization of abscissa as knots of the linear piece wise.<br>
x(i) := 1 + i*dx; i = 0, 2, .... n+1; dx = (21) / (n+1);<br>
and y(i) = unknown value of linearpw function at x(i).<br>
<br>
Given A = { a_j in [1,2] } a set of abscissa.<br>
<br>
The pw function can be written as matrix<br>
g(j) = pw(a_j) = A * y. (exercice)<br>
<br>
You want to find y(i) sunch that<br>
<br>
min_y max_i  f(a_j)  g(j) .<br>
<br>
This can be transformed into LP, by introducing slack variables u and v, and define vectors<br>
z = [y; u; v].<br>
<br>
min ( u + v ), subject to:<br>
f(a_j) + u = A*y<br>
f(a_j)  v = A*y<br>
u >= 0<br>
v >= 0<br>
<br>
Write this system in term of z, and use LINPROG to solve it, then you are done.<br>
<br>
Bruno