title: Aggregate/Extrapolate sparse samples in multi-dimensional space
body: <p>Imagine there is a function which evaluates the elevation of a surface given a floating point x and y coordinate (and additional components in accordance with dimensionality):</p>
  
  <pre><code>double ComputeElevation(double x, double y, ...., double z) { }
  </code></pre>
  
  <p>This is not an analytic function and thus the derivatives cannot be computed. What I need to do is find the direction in which the surface is steepest for any given {x, y} pair. A single evaluation could be very expensive (think seconds or even minutes in worst case scenarios).</p>
  
  <p>My typical approach in the 2D case would be to sample the surface in N locations adjacent to {x, y}, then fit a curve through those samples and search the curve for the highest point, as this search does not suffer from expensive evaluation:</p>
  
  <p><img src="https://i.stack.imgur.com/OVQck.png" alt="Example of Sampling Algorithm in 2D"></p>
  
  <p>In the above image P0 is the given coordinate. {S0, S1, S2, S3} are 4 random-ishly placed samples around P0 and PM is the highest point on the curve. Thus, the vector PM-P0 is the direction of steepest ascent.</p>
  
  <p>But I have no idea how to scale this up to N dimensions, or whether there are much smarter algorithms for doing this. </p>
  
  <p>The number of dimensions is potentially quite large (dozens to hundreds), so whatever method I end up using must work when there are fewer samples than there are dimensions. I'm not looking for the exact answer, that would be impossible, but a half-way decent approximation would already be most welcome.</p>
  
  <p>ps. I'm doing this in C#, not that it matters a great deal but I don't have access to non-C# language features.</p>