# Algorithm Identification

### Background

I'm currently working with a system that has a 4-dimensional function. Currently, an algorithm is used to speed up calculation of the final value via interpolation, and two of the independent variables are used to key off lookup tables based on the remaining 2. For example, I have 4 independent variables $\alpha_i, \alpha_e, n,$ and $a_l$. There exists a function $\eta = f(\alpha_i,\alpha_e,n,a_l)$. Due to the complex nature of this function and the need to get a decent estimation in quick time, lookup tables are used. By fixing $\alpha_i$ and $\alpha_e$, tables are then built essentially providing $\eta_{\alpha_i,\alpha_e} = f(n,a_l)$.

Several such tables are built, and then a weighted interpolation is built between them for the final answer.

I.e. given 4 such tables, $\eta_{-10,0},\eta_{-20,10}, \eta_{-30,20}, \eta_{-40,30}$ and a given $(\alpha_i,\alpha_e)$, we calculate the final value based on $$\eta = w_1.\eta_{-10,0}(n,a_l) + w_2.\eta_{-20,10}(n,a_l) + w_3.\eta_{-30,20}(n,a_l) + w_4.\eta_{-40,30}(n,a_l)$$

### Example

Given a basis for our lookups: $$(\alpha_i,\alpha_e) = (-10,0);(-20,10);(-30,20);(-40,30)$$

Assuming an $(\alpha_i,\alpha_e) = (-15, 27)$.

We calculate the residuals as follows: $$r_1 = (\alpha_i - -10, \alpha_e - 0) = (-5, 27)\\ r_2 = (\alpha_i - -20, \alpha_e - 10) = (5, 17)\\ r_3 = (\alpha_i - -30, \alpha_e - 20) = (15, 7)\\ r_4 = (\alpha_i - -40, \alpha_e - 30) = (25, -3)$$

Now we calculate intermediate weights: $$v_1 = \frac{1}{r_{1,\alpha_i}^2 + r_{1,\alpha_e}^2} = 0.00132625994\\ v_2 = \frac{1}{r_{2,\alpha_i}^2 + r_{2,\alpha_e}^2} = 0.00318471337\\ v_3 = \frac{1}{r_{3,\alpha_i}^2 + r_{3,\alpha_e}^2} = 0.00364963503\\ v_4 = \frac{1}{r_{4,\alpha_i}^2 + r_{4,\alpha_e}^2} = 0.00157728706$$

The final weights are then: $$w_1 = \frac{v_1}{\sum v_i} \approx 0.136 \\ w_2 = \frac{v_2}{\sum v_i} \approx 0.327 \\ w_3 = \frac{v_3}{\sum v_i} \approx 0.375 \\ w_4 = \frac{v_4}{\sum v_i} \approx 0.162$$

### Question

Does this particular method of finding weights for the interpolation algorithm have a name? I did not design it, but I must now work with it and would like to learn more about the math behind it. The calculation of the weights seems like some sort of projection of a given vector onto a linear combination of the basis vectors using square errors, but I don't recognize it.

My goal is to know how to pick good basis vectors to give a nice interpolation knowing I'll operating over a certain range of $\alpha_i$ and $\alpha_e$, and more importantly to understand more about the properties of this particular interpolation algorithm.

Thank you for your time!

• Think of this geometrically. Each $(a_i, a_e)$ is a point in the plane. The $r$s are the vectors from your point of interest to the various known points. The $v_i$ values are the inverse of the square of the distance from the point of interest to each of the known points, and $w_i$ values are just the $v_i$ values proportionalized so that the sum is $1$. They are assuming that the contribution of each known point is proportional to the inverse of the square of the distance to the point-of-interest. – Paul Sinclair May 5 '16 at 18:04
• @PaulSinclair this makes sense, but is it commonly used method at all? After more reading today would this be a form of inverse distance weighting? – Steven Goldade May 5 '16 at 20:54
• It is inverse distance weighting, with $p = 2$. How common that is, I don't know. – Paul Sinclair May 5 '16 at 22:05
• Inverse distance weighting is a common scheme and has been used widely. The earliest algorithm (that I am aware of) that uses this scheme is the Shepard's method for bivariate interpolation that was devised in 1960s. – fang May 5 '16 at 22:25