Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Can you clarify what you mean faster than Lagrange? It seems quite straightforward to write out the polynomial representation. Do you mean that, if we were given $x_i=i$, then we should simply have written down $f(x) = x$ directly, instead of numerous multiplcations? –  Calvin Lin Dec 29 '12 at 14:41
    
I mean, computationally efficient way. Like $O(n)$. But Lagrange is $O(nlog^2n)$, and even this with Fourier transforms (taken from cs.iastate.edu/~cs577/handouts/interpolate.pdf) –  Troy McClure Dec 29 '12 at 14:43
    
The fastest way is the pointwise definition $f(x_i) := i$. You need to be more specific; do you ned a polynomial answer? A smooth, increasing function? Are you trying to write a computer program to compute the function $x_i \to i$ (and only care about those input values)? If the latter, then your question is probably best asked on a programming site, but the standard answer would be "use a hash table". –  Hurkyl Dec 29 '12 at 15:09
    
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 algorithm –  Troy McClure Dec 29 '12 at 15:12
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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 algorithm –  Troy McClure Dec 29 '12 at 15:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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