title: inverse interpolation of multidimensional grids
body: <p>I am working on a project of interpolating sample data <code>{(x_i,y_i)}</code> where the input domain for <code>x_i</code> locates in 4D space and output <code>y_i</code> locates in 3D space. I need generate two look up tables for both directions. I managed to generate the <code>4D -&gt; 3D</code> table. But the <code>3D -&gt; 4D</code> 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 <code>3D -&gt; 3D</code> mapping, which are not suitable for this case. Thank you!</p>
  
  <hr>
  
  <p>To answer the questions of Spektre:</p>
  
  <p><code>X(3D) -&gt; Y(4D)</code> is the case <code>1X -&gt; nY</code></p>
  
  <p>I want to generate a table that for any given <code>X</code>, we can find the value for <code>Y</code>. The sample data is not occupy all the domain of <code>X</code>. But it's fine, we only need accuracy for point inside the domain of sample data. For example, we have sample data like <code>{(x1,x2,x3) -&gt;(y1,y2,y3,y4)}</code>. It is possible we also have a sample data <code>{(x1,x2,x3) -&gt; (y1_1,y2_1,y3_1,y4_1)}</code>. But it is OK. We need a table for any <code>(a,b,c)</code> in space <code>X</code>, it corresponds to ONE <code>(e,f,g,h)</code> in space <code>Y</code>. There might be more than one choice, but we only need one. (Sorry for the symbol confusing if any)</p>
  
  <p>One possible way to deal with this: Since I have already established a smooth mapping from <code>Y-&gt;X</code>, I can use Newton's method or any other method to reverse search the point <code>y</code> for any given <code>x</code>. 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.</p>
  
  <p>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.</p>