inverse interpolation of multidimensional grids

Question

I am working on a project of interpolating sample data {(x_i,y_i)} where the input domain for x_i locates in 4D space and output y_i locates in 3D space. I need generate two look up tables for both directions. I managed to generate the 4D -> 3D table. But the 3D -> 4D one is tricky. The sample data are not on regular grid points, and it is not one to one mapping. Is there any known method to treat this situation? I did some search online, but what I found is only for 3D -> 3D mapping, which are not suitable for this case. Thank you!

---

To answer the questions of Spektre:

X(3D) -> Y(4D) is the case 1X -> nY

I want to generate a table that for any given X, we can find the value for Y. The sample data is not occupy all the domain of X. But it's fine, we only need accuracy for point inside the domain of sample data. For example, we have sample data like {(x1,x2,x3) ->(y1,y2,y3,y4)}. It is possible we also have a sample data {(x1,x2,x3) -> (y1_1,y2_1,y3_1,y4_1)}. But it is OK. We need a table for any (a,b,c) in space X, it corresponds to ONE (e,f,g,h) in space Y. There might be more than one choice, but we only need one. (Sorry for the symbol confusing if any)

One possible way to deal with this: Since I have already established a smooth mapping from Y->X, I can use Newton's method or any other method to reverse search the point y for any given x. But it is not accurate enough, and time consuming. Because I need do search for each point in the table, and the error is the sum of the model error with the search error.

So I want to know it is possible to find a mapping directly to interpolate the sample data instead of doing such kind of search in 3.

Answer 1

1. You are looking for projections/mappings

   as you mentioned you have projection X(3D) -> Y(4D) which is not one to one in your case so what case it is (1 X -> n Y) or (n X -> 1 Y) or (n X -> m Y) ?

2. you want to use look-up table

   I assume you just want to generate all X for given Y the problem with non (1 to 1) mappings is that you can use lookup table only if it has

   • all valid points
   • or mapping has some geometric or mathematic symmetry (for example distance between points in X and Yspace is similar,and mapping is continuous)

   You can not interpolate between generic mapped points so the question is what kind of mapping/projection you have in mind?

3. First the 1->1 projections/mappings interpolation

   1. if your X->Y projection mapping is suitable for interpolation

      then for 3D->4D use tri-linear interpolation. Find closest 8 points (each in its axis to form grid hypercube) and interpolate between them in all 4 dimensions

   2. if your X<-Y projection mapping is suitable for interpolation

      then for 4D->3D use quatro-linear interpolation. Find closest 16 points (each in its axis to form grid hypercube) and interpolate between them in all 3 dimensions.

4. Now what about 1->n or n->m projections/mappings

   That solely depends on the projection/mapping properties which I know nothing of. Try to provide an example of your datasets and adding some image would be best.

[edit1] 1 X <- n Y

I still would use quatro-linear interpolation. You still will need to search your Y table but if you group it like 4D grid then it should be easy enough.

1. find 16 closest points in Y-table to your input Y point

   These points should be the closest points to your Y in each +/- direction of all axises. In 3D it looks like this:

   

   • red point is your input Y point
   • blue points are the found closest points (grid) they do not need to be so symmetric as on image .

   Please do not want me to draw 4D example that make sense :) (at least for sober mind)

2. interpolation

   find corresponding X points. If there is more then one per point chose the closer one to the others ... Now you should have 16 X points and 16+1 Y points. Then from Y points you need just to calculate the distance along lines from your input Y point. These distances are used as parameter for linear interpolations. Normalize them to <0,1> where

   • 0 means 'left' and 1 means 'right' point
   • 0.5 means exact middle

   You will need this scalar distance in each of Y-domain dimension. Now just compute all the X points along the linear interpolations until you get the corresponding red point in X-domain.

   With tri-linear interpolation (3D) there are 4+2+1=7 linear interpolations (as on image). For quatro-linear interpolation (4D) there are 8+4+2+1=15 linear interpolations.

3. linear interpolation

   X = X0 + (X1-X0)*t
   

   • X is interpolated point
   • X0,X1 are the 'left','right' points
   • t is the distance parameter <0,1>