Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Piecewiese linear approximation function with a minimal largest error dev.

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Deyan Levski

Date: 1 Jan, 2013 08:57:07

Message: 1 of 12

Hello everyone,

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.

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).

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.


Best Regards,
Deyan

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Bruno Luong

Date: 1 Jan, 2013 09:48:07

Message: 2 of 12

"Deyan Levski" <remove.this@gmail.com> wrote in message <kbu8d3$gcr$1@newscl01ah.mathworks.com>...
> Hello everyone,
>
> 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.
>
> 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).
>
> 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.
>

This problem can be formulated as linear programming, that can be solved with LINPROG.

Bruno

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Matt J

Date: 1 Jan, 2013 14:07:08

Message: 3 of 12

"Deyan Levski" <remove.this@gmail.com> wrote in message <kbu8d3$gcr$1@newscl01ah.mathworks.com>...
>
> 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).
>
> 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.
================

If you have Optimization Toolbox, then fminimax() might be applicable

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Roger Stafford

Date: 1 Jan, 2013 17:46:08

Message: 4 of 12

"Deyan Levski" <remove.this@gmail.com> wrote in message <kbu8d3$gcr$1@newscl01ah.mathworks.com>...
> 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.
>
> 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).
- - - - - - - - -
  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
simple mathematical function to be fitted. Could you tell us what it is?

  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 in-between 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 time-consuming computationwise.

Roger Stafford

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Deyan Levski

Date: 2 Jan, 2013 07:13:08

Message: 5 of 12

"Roger Stafford" wrote in message <kbv7d0$obt$1@newscl01ah.mathworks.com>...
> "Deyan Levski" <remove.this@gmail.com> wrote in message <kbu8d3$gcr$1@newscl01ah.mathworks.com>...
> > 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.
> >
> > 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).
> - - - - - - - - -
> 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
> simple mathematical function to be fitted. Could you tell us what it is?
>
> 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 in-between 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 time-consuming computationwise.
>
> Roger Stafford

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.

Kind Regards,
Deyan

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Bruno Luong

Date: 2 Jan, 2013 07:41:08

Message: 6 of 12

"Deyan Levski" <remove.this@gmail.com> wrote in message <kc0mm4$oem$1@newscl01ah.mathworks.com>...

>
> 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.

As I told earlier, if the knot are fixed (regardless they are is equidistant or not) , this problem is a first-degree spline-approximation (piece-wise linear) of l_infinity norm, and can be formulated as linear programming.

Bruno

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Bruno Luong

Date: 2 Jan, 2013 07:48:07

Message: 7 of 12

BTW the least-square (l2) minimization of linear-picewise function can be achieved with my tool:
http://www.mathworks.com/matlabcentral/fileexchange/25872-free-knot-spline-approximation

Bruno

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Roger Stafford

Date: 2 Jan, 2013 08:48:09

Message: 8 of 12

"Deyan Levski" <remove.this@gmail.com> wrote in message <kc0mm4$oem$1@newscl01ah.mathworks.com>...
> 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)). .......
- - - - - - - - -
  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.

  To put it in another way, if the x-widths 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.

  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.

  I still think this method with numerous intermediate points might be a good way to solve the harder problem with non-uniform spacing of line segment endpoints' x-widths permitted. With uniform spacing of line segment endpoints the problem becomes relatively easy but rather unsatisfactory in its arbitrariness.

Roger Stafford

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Roger Stafford

Date: 2 Jan, 2013 09:06:08

Message: 9 of 12

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kc0oak$dm$1@newscl01ah.mathworks.com>...
> As I told earlier, if the knot are fixed (regardless they are is equidistant or not) , this problem is a first-degree spline-approximation (piece-wise linear) of l_infinity norm, and can be formulated as linear programming.
>
> Bruno
- - - - - - - - -
  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.

Roger Stafford

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Bruno Luong

Date: 2 Jan, 2013 10:43:07

Message: 10 of 12

"Roger Stafford" wrote in message <kc0ta0$ftf$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kc0oak$dm$1@newscl01ah.mathworks.com>...
> > As I told earlier, if the knot are fixed (regardless they are is equidistant or not) , this problem is a first-degree spline-approximation (piece-wise linear) of l_infinity norm, and can be formulated as linear programming.
> >
> > Bruno
> - - - - - - - - -
> 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.

Right Roger, I assume the function to be approximated is somehow discretized.

Let see if Deyan can confirm if he absolutely wants a continuous version or not.

Bruno

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Deyan Levski

Date: 2 Jan, 2013 14:08:07

Message: 11 of 12

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> > >
> > > Bruno
> > - - - - - - - - -
> > Bruno, we seem to be looking at Deyan's problem from two different........
>
..... Right Roger, I assume the function to be approximated is somehow discretized.
>
> Let see if Deyan can confirm if he absolutely wants a continuous version or not.
>
> Bruno

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 first-order spline approximations, and I am hoping to soon find a solution to be able to continue over my work.

Subject: Piecewiese linear approximation function with a minimal largest error dev.

From: Bruno Luong

Date: 2 Jan, 2013 18:43:09

Message: 12 of 12

"Deyan Levski" <remove.this@gmail.com> wrote in message
>
> 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 first-order spline approximations, and I am hoping to soon find a solution to be able to continue over my work.

Let define:
f(x) := cos((pi/2)*log(x))

A discretization of abscissa as knots of the linear piece wise.
x(i) := 1 + i*dx; i = 0, 2, .... n+1; dx = (2-1) / (n+1);
and y(i) = unknown value of linear-pw function at x(i).

Given A = { a_j in [1,2] } a set of abscissa.

The pw function can be written as matrix
g(j) = pw(a_j) = A * y. (exercice)

You want to find y(i) sunch that

min_y max_i | f(a_j) - g(j) |.

This can be transformed into LP, by introducing slack variables u and v, and define vectors
z = [y; u; v].

min ( u + v ), subject to:
f(a_j) + u = A*y
f(a_j) - v = A*y
u >= 0
v >= 0

Write this system in term of z, and use LINPROG to solve it, then you are done.

Bruno

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us