1
$\begingroup$

I have a dataset $\{x_i, y_i\}_{i=0}^{n-1}$ where $x_0 < x_1 < \cdots x_{n-1}$ (not uniformly spaced), and, in addition $y_0 < y_1 < \cdots y_{n-1}$. So it feels natural to assume that $y_i$ are samples of an unknown monotonically increasing function.

I would like to interpolate these data, but it is very important that the interpolant be monotonically increasing. Obviously linear interpolation satisfies my requirements, but is there something smoother, with constant time or $O(\log(n))$ evaluation?

Improve this question
$\endgroup$
2
  • $\begingroup$ First of all, cause your data points are monotic in both x and y, that doesn't mean they are unknown samples of unknown monotonically increasing function. I hope you know it. By the way, There are countless smooth and monotonic functions that could be fitted precisely into your data. For example you have n data points and a (n-1)th-degree polynomial will be perfectly fitted on your data, but so what?! it's not correct to choose the regression function solely based on its mathematical properties. If you have a theory, that theory should tell you what regression function should be at the end. $\endgroup$
    – Mithridates the Great
    Sep 26, 2019 at 13:38
  • $\begingroup$ @AloneProgrammer: Note that I am not asking for a regression function, but an interpolator. $\endgroup$
    – user14717
    Sep 26, 2019 at 13:53

1 Answer 1

Reset to default
3
$\begingroup$

Piecewise Cubic Hermite Interpolating Polynomial (PCHIP) preserves monotonicity and has continuous derivatives. It can be evaluated in $O(\log(n))$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But, it requires the derivatives on the library, doesn't it? $\endgroup$
    – nicoguaro ♦
    Sep 27, 2019 at 10:36
  • 1
    $\begingroup$ The derivatives are computed so as to preserve monotonicity. The inputs are just the function values. See, for example, mathworks.com/help/matlab/ref/pchip.html $\endgroup$
    – Amit Hochman
    Sep 27, 2019 at 12:13
  • $\begingroup$ @AmitHochman: Is this the reference? doi.org/10.1137/0717021 $\endgroup$
    – user14717
    Dec 12, 2019 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.