0
$\begingroup$

Let $n\in\mathbb N$. Let $\{{x_i\}}_{i=1}^{n}$ be $n$ positive real numbers. Can one think of a fast way to construct a function $f$ such that $f(x_i)=i$?

(i.e. $f$ maps $\{{x_i\}}_{i=1}^{n}$ to ${1,2,3,...,n}$. At least a way faster than Lagrange, Newton or Trigonometric-Lagrange interpolation)

Note: you can assume that $\{{x_i\}}_{i=1}^{n}$ is increasing.

  • 0
    it should be a smooth function, its purpose will be to interpolate for $x$ that does not appear in the sample set, but does not break its bounds (i.e. bigger than the minimum and smaller than the maximum). my question is purely mathematical, I'm composing an article about a new algorithm2012-12-29

2 Answers 2

1

A simple and fast function would be the function $f(y)$ as defined by

  • Do a binary search on the list of $x$'s to find the $i$ such that $x_i \leq y \leq x_{i+1}$
  • Return $i + \frac{y - x_i}{x_{i+1} - x_i}$

This won't be differentiable at each $x_i$. Similar ideas can be used to make differentiable functions, twice differentiable functions, or even infinitely differentiable functions: just replace the linear function with something suitable.

The function

$ g(x) = \begin{cases} 0 & x \leq 0 \\ e^{-1/x^2} & x > 0 \end{cases} $

is a classic building block if you really need infinitely differentiable.

0

Since you seem to be trying to do a reverse lookup on your values, I would be wary of any function that needs irrational or even non-integer coefficients. Computer roundoff will make it uncertain whether you are actually at one of your values because you will not get a true integer as a result. If you just want to know which two values you are between then that may be enough.

A single function which accounts for all your values is also likely to not have other desirable properties for interpolation, such as relatively smooth derivatives or even monotonicity. Unless this is a one-time setup and you can spend a lot of time inspecting the properties of the resulting function, I would stick with piecewise functions to interpolate on.

  • 0
    thanks. indeed, this question comes from a theoretical framework, by investigating some Gram matrices over Cameron Martin space. this will become one stage in a learning algorithm2012-12-29