2
$\begingroup$

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.

I have a list of calibration test points, that need to be curve-fitted, that look something like this: Raw test points

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:

  1. Fit the $N$ points to a curve of degree $n+1$ ($4$ since I need $3$ segments).
  2. Find the inflection points of the fit, $p_0$, $p_1$.
  3. Gather the points in the intervals $[min, p_0), (p_0, p_1), and (p_1, max]$
  4. Fit the points in the intervals to quadratic curves.
  5. 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.

After doing the initial fit and finding the inflection points (the x values, at least), we have: Quartic curve fit plus inflection points

However, following this algorithm produces the following curves: enter image description here

Clearly, this is not optimal.

  1. There should always be at least three points in a quadratic curve fit, but the middle segment only has 2.
  2. The segments should "smooth" into each other.
  3. The third segment has too many points in it and is just a bad fit.

Heuristically, I think the segments should look more like this: heur

Right now, I am considering fudging it, by

  1. 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).
  2. Expanding the current intervals to contain the first point of the following segment, except for the last one.

Following the fudging approach above, I would get something like this for this example: Fudged data

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:

  1. Does there exist a mathematically rigorous way to sanitize outliers like I have mentioned?

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

Constraints:

  1. For mathematical tools, I only have access to a least-squares fitter.
  2. For this type of calibration, there will always be 3 segments and 10+ points.

Context

  1. 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.
  2. 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).
$\endgroup$
  • $\begingroup$ I might be missing something, but why can't you use splines? $\endgroup$ – Yuriy S Dec 27 '17 at 23:26
  • 1
    $\begingroup$ @Yuriy S... I agree, more precisely quadratic splines (not cubic splines that are more usual). $\endgroup$ – Jean Marie Dec 27 '17 at 23:28
  • $\begingroup$ I should probably have noted that I only have access to a least-squares fitter, and, yes, with this type of calibration, there will always be exactly 3 segments. $\endgroup$ – rationalcoder Dec 27 '17 at 23:36
  • $\begingroup$ I feel like this question needs more context still. What is the measure of success in this approximation problem? From the practical point of view, what is this function supposed to do, and what kind of errors are allowed? What kind of input data is expected, since it's not likely to be exactly the same as in the example above? $\endgroup$ – Yuriy S Dec 27 '17 at 23:42
  • $\begingroup$ @YuriyS I guess you are right. I just wanted to keep as much engineering out as possible. I will try to add some more context. $\endgroup$ – rationalcoder Dec 27 '17 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.