Andrew Que Sites list Photos
Projects Contact
Main
    The first day of class for the spring semester.  Although not attending classes, I showed up to being cookies for Altered Reality.

3 comments have been made.

From Liz (liz-photography.livejournal.com)

WI84

February 03, 2008 at 12:29 AM

so you are a cookie then? if so what kind? I know you can't help your spelling at all but that turned out rather amusing.

From Andrew Que (http://www.DrQue.net/)

Wisconsin, USA

February 06, 2008 at 7:46 AM

Hey... that's pretty good for a guy who could barely breath all week!

From Andrew Que (http://www.DrQue.net/)

The Garage, Wisconsin, USA

March 16, 2008 at 7:53 PM

Gosh, I look like I'm in that picture two times.

January 23, 2008

Polynomial interpolation

   Interpolation is a method in which the values of unknown data are filled using known data. It is basically making an educated guessing--hypnotising. I've used interpolation a number of times in the field and today I'm going to write a little about it.
   I've most often used linear interpolation. This is the easiest to implement and when filling in small gaps of data, quite sufficient.  For larger gaps between data, one method is polynomial interpolation.



    Here we have two singles, both missing 98% of the real data. The first chart uses linear interpolation to fill in the gaps. The second uses polynomial interpolation. The real signal is in green and the interpolated signal is in red.  The black dots denote locations where data is present.  Note that most of the green is covered because both systems of interpolation reconstruct the signal fairly well. However, aside from the ends, the polynomial interpolation is a much closer fit. This is evident when closely examining a segment of the chart.



    Here is the same function, but zoomed into a specific area. The linear interpolation's weak fit is much more apparent, where the polynomial interpolation is pretty much a perfect fit.

Here is the equation for polynomial interpolation:

This expands to:


    What this equation does is predict any new point with the existing point using all of the data from the existing points.  This function creates a polynomial that intercepts each of the known points.  Since this is a polynomial and all polynomials are continuous function, a value of y can be obtained for any value x.
It looks messy, but as source code turns into a couple of nested for-loops.
//---------------------------------------------------------------------------
// Polynomial Interpolate
//---------------------------------------------------------------------------
function PolynomialInterpolate$x $Data )
{
   
$y 0.0;
   foreach ( 
$Data as $Y_Index => $Y_DataPoint )
   {
     
$y_n $Y_DataPoint"y" ];
     
$x_n $Y_DataPoint"x" ];

     
$Numerator   1.0;
     
$Denominator 1.0;
     foreach ( 
$Data as $X_Index => $X_DataPoint )
     {
       if ( 
$Y_Index == $X_Index )
         continue;

       
$Numerator   *= $x $X_DataPoint"x" ];
       
$Denominator *= $x_n $X_DataPoint"x" ];
     }

     
$y += ( $Numerator $Denominator ) * $y_n;
   }

   return 
$y;
}
   Because of the multiplication and division, the process is fairly CPU intensive. And the more data points, the longer this interpolation takes.
   Polynomial interpolation can end up producing significantly worse results then linear interpolation when there are not enough data points.

Using a 5 Hz single


Using a 7 Hz single

Using a 7 Hz single
    The above charts show polynomial interpolation without enough sample points to discern the frequencies. Note how the interpolation still passes through each of the data points, but can become radically different between sample points. Linear interpolation actually ends up making a better fit under these conditions.  Notice how the ends of the function are worse then the middle.  This seems typical of polynomial interpolation.
    There are other types of interpolation, such a bilinear and trilinear as well as the more popular Spline interpolation.  I will probably write about these methods latter on.
    I had a nice white-knuckled drive to Madison today for an interview.  Turns out the snow storm last night replaced I-90 with a sheet of ice.  Travel speeds were no more then 45 MPH with a lot of bumper to bumper.  I noticed the ice shortly after getting onto 90.  The off ramp was covered in a fair amount of snow, the the interstate looked clear.  So after I reached what looked to be open road, I hit the accelerator to speed up.  Shortly after I started accelerating, my back tires started spinning freely.  I slowed down after that and pass no less then 10 cars in the ditch.  Longest drive to Madison I've ever taken.
    Pictured is Liz who fell in the snow walking around the driveway.