This is an idea for probably a Master's Thesis project.
We know that we can approximate functions in a minimax senses, suitably sampled, using Linear Programming.
Where:
F is the function or series to be approximated.
A is the approximant or approximating function: a linear combination of basis functions such as a0 + a1*x +a2*x^2....
E is the error where the peaks (the maxima) are to be minimized and the result will be a series of equal peaks of generally alternating sign.
The equations look like this:
The inequalities in the linear program notation might look like this:
a01 + a11*x + a21*x^2 ...... + aN1*x^N - F1
Hello Fred, there is a mathematical basis of such calculations: polynomial interpolation. The most simple case is linear interpolation though there are more complex methods including many points of interpolation to get a better fit to a certain curve. In linear interpolation, for example, according to the Unisolvence Theorem, it doesn´t matter the expression you use to interpolate, you will always obtain a same result (Ej. newton and lagrange interpolation methods), the polynomial exists and it´s unique. There are many criterias in this field you can find to compare both methods, mainly based in the error of fitting, but you need to know the original function you are trying to aproximate. Perhaps this is not what you need, but let me know if it helps, I am also concerned about this.
Eddy, Yes for polynomial interpolation I agree. In my case specifically, the basis set was different so my perspective might be a little broader. (Although it may be possible to express the same problem with equivalent polynomials .. I don't know).
What intrigues me and what I'm not capable of figuring out is this:
Given linear programming as an algorithmic approach
Given the usual Remez exchange algorithm as another
The linear programming method allows equality constraints directly.
The Remez Exchange algorithm with no modification does not.
And, our modification to the Remez exchange algorithm will allow it within certain bounds (that the equality constraint is equal to the objective function at the same point - or nearly equal at least).
It seems to me that there must be some unifying treatment that would relate the two approaches. Perhaps it's my weak understanding of linear programming that makes it not so obvious.
I certainly imagine that the equivalent of the Unisolvence Theorem applies over a broader set of basis functions and applies in the cases that I was working with. So, while the solutions may be identical, my interest is the relationship of the processes in getting there. The focus is algorithmic. The answer may be trivial and the answer may be interesting leading to some insights heretofore not illuminated. Thus a Master's project....
I think my introduction threw things off track. The last part paraphrased here is the question I asked ... or ... intended to ask:
Two different methods(linear programming with a minimax objective/formulation and the Remez Exchange algorithm) can be used to achieve the same outcome. That suggests that there's a relationship between the two.
But how does the Remez Exchange algorithm (REA)and a minimax-contructed linear program (MCLP) relate in an understandable / practical mathematical context?
(I'm not able to express the relationship in this manner).
An: .......
How are they similar? How are they different?
A1: Without modification, the REA can't impose equality contraints while the MCLP can, fairly directly. Maybe that's a big deal and maybe not.
An: ......
What further extensions of the Remez algorithm might be suggested with this illumination?
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics