I essentially have a constrained curve fitting problem that I need to solve efficiently.
The following problem arises when performing practical calibration of RSSI (signal strength), providing functions that a machine can use to transform its internal reading of signal strength into the actual supplied signal strength.
The problem is, as a hard constraint, I need to represent this as a piece-wise quadratic function, specifically, 3 pieces ("segments").
My first attempt at an algorithm was as follows:
- Fit the $N$ points to a curve of degree $n+1$ ($4$ since I need $3$ segments).
- Find the inflection points of the fit, $p_0$, $p_1$.
- Gather the points in the intervals $[min, p_0), (p_0, p_1), and (p_1, max]$
- Fit the points in the intervals to quadratic curves.
- Use the quadratic curves and the segment boundaries (interval limits) to define the three segments.
The min and max are given, and this is known before-hand, so they are not part of the problem.
Clearly, this is not optimal.
- There should always be at least three points in a quadratic curve fit, but the middle segment only has 2.
- The segments should "smooth" into each other.
- The third segment has too many points in it and is just a bad fit.
Right now, I am considering fudging it, by
- Sanitizing the weirdness at the end into a something more like a slight curve (get rid of the outlier (red one in this case) be shifting it to the midpoint between the previous and next points).
- Expanding the current intervals to contain the first point of the following segment, except for the last one.
Although this is fundamentally an approximation/programming problem, I figured you mathy people might know a more rigorous way to solve this type of problem. Specifically:
Does there exist a mathematically rigorous way to sanitize outliers like I have mentioned?
Once you have sanitized data, is there a known, mathematically optimal way to cover the points with $n$ quadratic curves that is more efficient than performing a brute-force, $N \choose n$ with the least error/discontinuity approach?
As a side note, I am a programmer, not a mathematician, so advanced notation will probably be lost on me.
- For mathematical tools, I only have access to a least-squares fitter.
- For this type of calibration, there will always be 3 segments and 10+ points.
- The measure of success of the approximation is how well it fits the test points, while keeping the overall shape of the original quartic curve fit. Specifically, the concavity must be the same and the results have to be functions. i.e. there can be no best fit curves that are concave-down where the original fit was concave up (and vice versa) and no vertical lines.
- The idea of three segments and a quartic curve come from experimental data. All RSSI measurements map from measured dBFS to a known dBm for a repeater (in a radio system). All calibration points look roughly the same for this specific type of repeater (which is all we will be using this to calibrate). That is, the points will always be reasonably fit by a quartic curve and the specific curve will always look about the same. We are talking about x-values for a different repeater differing by ~ +-.5 and the y-values being exactly the same (because the y-values represent known signal strengths that we are calibrating to).