RANDOM INTERPOLATION
Frequently Asked Questions

[These are the frequently asked/received questions together with our answers. If you have a question, please e-mail it to us and we shall post the response here, shared with all our visitors.]

Question: It is not clear whether the interpolated f(x,y) at given input x1, y1 also equals the given input f1 since the influence of the dirac delta function stretches to infinity based on the equation provided at the web site. Please explain.
Answer: In theory, the delta width values of x, y are approaching zero.Therefore, the interpolated f(x,y) at given input x1, y1 is approaching thevalue of the given input f1. Note that in practical, numerical calculation,the delta width values would be small but finite and the interpolated f(x,y)at x1, y1 can be made within 1% of the given input f1, by adjusting thevalue of delta width accordingly. Please check this property out onour web site (RDIC).
Question: Your interpolation method is known in the neural network community as 'normalized radial basis functions' and in the statistics community as the 'Nadaraya-Watson estimator'. Do you have an estimate on the convergence of the method ? How does it depend on the dimension and the smoothness of the function to interpolate ?
Answer: Our method starts with an identity integral (which is analogous to Reproducing Kernel Hilbert Space -RKHS method) and its derivation depends on Monte-Carlo method. The error analysis of our method can be produced analytically. The estimate on the convergence of our method has shown that the convergence depends on two terms: (a) bias term; (b) random error term. The bias term depends on the dimension as where M' is the number of sample data points used in the interpolation and n is the dimension, and the random error term is inversely proportional to the square root of M' and independent of the dimension. Both terms are independent of the smoothness of the function to interpolate. Please download our supplementary material in Microsoft WORD file, or in PDF file, regarding "accuracy and convergence" issues.
Question: Based on the interpolants derived at RDIC, you essentially have presented "a Kernel regression estimator with a modified Cauchy probability density". Is this correct?
Answer: Our method starts with (Eq. A) and (Eq. A-1) on the Introduction page. (Eq. A) uses the concept of Dirac delta function and (Eq. A-1) is the "computable" variant of (Eq. A). The derivation of interpolant formula is established via Monte-Carlo integration. The form of the interpolant found at RDIC indeed looks the same as "a Nadaraya-Watson estimator with a modified Cauchy kernel". However, the error analysis of our interpolants is different from the kernel regression method. More on this issue, please read the supplementary material (See the previous question and answer). In addition, the width (bandwidth) selection in our method has followed a different algebraic process.
Question:Your interpolant (which is basically a kernel weighing of observations) has some positiveaspects: the interpolated values are linear combinations of the observations, whereobservations nearby get larger weights than observations far away. But the standard kernel regression method covers that property too and well. What advantage can the Dirac-Monte Carlo method deliver, while kernel regression can not?
Answer: In 2-D and 3-D space, Dirac-Monte Carlo method can easily produce interpolants for polar, spherical and cylindrical coordinate systems. These coordinates are non-Cartesian. The major advantages of having these interpolants are: (a) to deal with interpolation applications which are better treated by non-Cartesian coordinates (These interpolants shall provide efficientsolutions for global weather study, mining industry, earthgravity and magnetic field survey, as well as geometric surfacereconstruction.); (b) to deal with non-convex domain (For example, between two concentric circles or two concentric spherical surfaces, L-shape corridor, etc. Currently, there are no interpolants/estimators thatcan do this correctly.).
Question: Why are you using Cauchy distribution, and not Gaussian distribution, for the approximation of Dirac delta function?
Answer: In nonparametric kernel regression literature, Cauchy kernel has beenshunned by researchers because mean and variance, or higher moments in thiscase, are not defined for the unbounded domain. But the long tail of Cauchykernel is a desired, needed property to give long-range influence andsensitivity in high dimension space for applications with bounded domainsupport. We shall employ Gaussian distribution to approximate Dirac delta function for later study.
Question: Can your interpolant handle an anisotropic kernel smoothing case? That is, the weights assigned to each point in the smoothing not only depends on the distance of the point to but also itsdirection to a studied location.
Answer: Our interpolant provides a simple nonparametric kernel smoothing treatment which does notdepend on "distance" but on the "coordinate separation". The user needs toprovide 2 width values in order to do interpolation in 2-D. Though themethod posted on the site deals with Cartesian coordinates, it isstraightforward to be extended to polar coordinates if desired.
Question: How to “optimally” select the bandwidth parameters when using your interpolant? Please explain. Can your software automate this process?
Answer: Our method does not follow the standard approach of deriving nonparametric kernel regression estimator. In addition, It does not use Mean-Square-Error (MSE) to obtain the optimized bandwidth values. Our approach is to find out the first-cut values of bandwidth (analytically simple, download at: http://www.fanginc.com/texas2.doc). Then we fine tune the width value (generally reducing the first-cut value) so that the reproduced function values at input locations of global maximum and minimum are within a few percent (about 5% roughly) of the prescribed, input values. Overly reducing the width value to match the prescribed values, say less than 1%, is not recommended because it will cause large variation and less smoothness of the interpolated function values. This fine-tuning part can be automated, if needed. Our program on the web site is "rudimentary" and for demo only, and the entire interpolation center will be upgraded in the very near future.
Question:Can your interpolant be applied to "time interpolation" applications? If yes, how do you explain the function at a point in the past be influenced by a weighted contribution from a point in the future?
Answer: The answer is "yes". If you agree that there is a functionwhich depends on "time" within an interval, say, between t1 and t2, then itis ok to have function at a future time t3 to give "weighted contribution "to the interpolated value at a past time t4. Of course, t3 and t4 are bothwithin the interval defined between t1 and t2. One reason for us to say so is that if you make a Taylor's series expansion of the function at t3, andif it is convergent, it is ok mathematically to use the function expansionfor time value greater than t3 or smaller than t3. In a way of speaking,"causality" does not play a role here. Currently, we are planning to use interpolant to do communication signal reconstruction in the timedomain.
Question:It seems that your methodology is applicable to "the problem of interpolation on a circle, which is essentially a single variable, one-dimension case" because the circle has a fixed radius and any point on the circle is defined by the azimuthal angle value. Now, the azimuthal angle covers the domain values from 0 to 2π radians. If there is a sample given at the location with azimuthal angle, say 0.043 radians (about 5 degrees) and the requested location with azimuthal angle at, say 3.054 radians (about 350 degrees) or equivalently -0.087 radians (-10 degrees), then according to your "coordinate separation" weighting scheme you will have two possible separation values, one with (0.043-3.054) and the other with (0.043+0.087). Logically, one expects the smaller separation 0.13 radians (15 degrees) will be the correct one to use in your interpolation formula because the other value -3.011 radians (-345 degrees) can hardly contribute any weighting value. However, negative angle values are not within the domain values between 0 and 2π. Please clarify and resolve this "double-value" ambiguity here.
Answer: Please download the answer.
Question: Is it possible to provide the pseudo-code of the Algorithm for your higher dimensional interpolation? Pseudo-code type algorithm which is typically found in Numerical Analysis books.
Answer: We do not have pseudo-code available for our program. If you tell us your need regarding the dimension you need and the domain values of your variables, we may be able to provide a software demo version for you. In the near future, our software shall be available in the commercial market.
Question: If you try your own sample case (2-dimension) with x1=6 and x2=6, it will givethe truth value ~250 and your wrong result ~187.Do you call this an interpolation?
Answer: Please note that we only used 12 randomly located input data for the interpolation. The errorassociated with the interpolant is documented in supplementary material. The more input data are used, the better the final answer willbe.
Question: I wanted to have some technical information regarding the interpolationalgorithm. I am looking for an interpolation algorithm of five dimensions. That is, y = f(x1, x2, x3, x4, x5) and written in java.
Answer: Please visit our web site at: http://www.fanginc.com/main.htm to findout technical information on our interpolation algorithm. Contact us foradditional data if needed. Our algorithm can easily accommodate 5 variables. We shall provide a Java version of our program at a later time.
Question: What are the guidelines to decide which delta width value to use to give better interpolated results?
Answer: Please read the supplementary material to find out how to calculate the optimized delta width for your applications.
However, there is one characteristics of our method which should be pointed out. As can be seen in our interpolant, it is basically a ratio of "numerator" over "denominator", and both are in the form of summation of rational functions. If the position to be interpolated has one coordinate value very close or equal to the same coordinate value of any given input locations and if delta width is a small value, then the interpolated function value will have a direct impact by the given input function value. In other words, for example if the input location (x=a, y=b) for 2D case has the input function value F₀, then any interpolated locations within or close to x=a ± or y=b ± (That is, a narrow but long "cross" centered at x=a, y=b in the problem domain.) will yield values strongly influenced by F₀ value. In this situation, the user should use a larger delta width value, and it will remove this "artifact" feature in the interpolation process. Generally speaking, the artifact will not show up by use of the optimized delta width value found in our method. As a final remark, it is emphasized that the user needs to be aware of this long-range dependence effect.
Question: Do we use the same delta width value(s) to obtain all the interpolated values across the whole problem domain? How to find delta width values for more than one dimension?
Answer: The delta width value found in our analysis has been optimized for the entire domain. However, It can be further fine-tuned if there is any specific goal to study the neighborhoods of sample input locations. Read the supplementary material for finding more info about delta width values in multi-dimension space as well as non-square problem domains.
Question:
Answer:

[More to come.....]

Return to RDIC opening page