Quicker 1D linear interpolation: interp1qr

version 1.1.0.0 (2.28 KB) by Jose M. Mier
Same functionality as built-in MATLAB function 'interp1q' but 3x faster.

2.7K Downloads

Updated 5 Sep 2013

View License

Quicker 1D linear interpolation: 'interp1qr'

Performs 1D linear interpolation of 'xi' points using 'x' and 'y', resulting in 'yi', following the formula yi = y1 + (y2-y1)/(x2-x1)*(xi-x1).

Variables:
- 'x' is column vector [m x 1], monotonically increasing.
- 'y' is matrix [m x n], corresponding to 'x'.
- 'xi' is column vector [p x 1], in any order.
- 'yi' is matrix [p x n], corresponding to 'xi'.

It has same functionality as built-in MATLAB function 'interp1q' (see MATLAB help for details).

It runs at least 3x faster than 'interp1q' and 8x faster than 'interp1', and more than 10x faster as m=length(x) increases (see attached performance graph).

As with 'interp1q', this function does no input checking. To work properly user has to be aware of the following:
- 'x' must be a monotonically increasing column vector.
- 'y' must be a column vector or matrix with m=length(x) rows.
- 'xi' must be a column vector.

As with 'interp1q', if 'y' is a matrix, then the interpolation is performed for each column of 'y', in which case 'yi' is p=length(xi) by n=size(y,2).

As with 'interp1q', this function returns NaN for any values of 'xi' that lie outside the coordinates in 'x', and when 'xi' is NaN.

This function uses the approach given by Loren Shure (The MathWorks) in http://blogs.mathworks.com/loren/2008/08/25/piecewise-linear-interpolation/
- Uses the function 'histc' to get the 'xi_pos' vector.
- Also uses a small trick to rearrange the linear operation, such that yi = y1 + s*(xi-x1), where s = (y2-y1)/(x2-x1), now becomes yi = y1 + t*(y2-y1), where t = (xi-x1)/(x2-x1), which reduces the need for replicating a couple of matrices and the right hand division operation for 't' is simpler than it was for 's' because it takes place only in one dimension (both 'x' and 'xi' are column vectors).

Acknowledgements: Nils Oberg, Blake Landry, Marcelo H. Garcia, the University of Illinois (USA), and the University of Cantabria (Spain).

--------------------------------------
Author's comments:
1- I developed this function as a way to improve performance on a program that makes many 1D simple interpolations. It is only for linear interpolation and does no input checking, so users beware!
2- It is literally 10 lines of code, which makes it a fast and simple solution.
3- It has the exact same functionality as 'interp1q', so you could go and replace it with this function and it should work straight.
4- I started with a slightly different approach, then I was reading some documentation and found Loren's approach, so I tested it and proved to perform even better.
5- During development I have been comparing performance mainly against 'interp1q'. Then I went into the source code to understand what the function was doing, and found that it uses a different approach using the 'sort' function which is more time consuming than 'histc'.
6- Then out of curiosity I went into the source code for 'interp1', which is more complex with many options and error checks, but deep inside it seems to be using a similar approach with 'histc'. So this 'interp1qr' function could be thought of as the stripped down version of the more complete 'interp1'.
7- During my search, I also found another function worth mentioning called 'qinterp1' by Nathaniel Brahms (File ID: #10286), which is even faster than all of these, but only works for evenly-spaced 'x' and 1 column in 'y' as far as I could test. When I looked into the source code of the MATLAB 'interp1' the same approach is used for evenly-spaced data, so Nathaniel Brahms function could be consider the stripped down version in that case.
8- You can take a look at the attached graph showing a performance comparison between this function 'interp1qr' and the built-in MATLAB functions, in terms of time as the length of 'x' increases. Note that both axis are in log scale. The computer used has WinXP with 2.33GHz and 4GB of RAM. The MATLAB version used was 2012a.

In summary, I thought this function could be useful for others to save some time on programs that are heavy on interpolations and when you are sure the type of data you have.

Cite As

Jose M. Mier (2022). Quicker 1D linear interpolation: interp1qr (https://www.mathworks.com/matlabcentral/fileexchange/43325-quicker-1d-linear-interpolation-interp1qr), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2010a
Compatible with any release
Platform Compatibility
Windows macOS Linux
Acknowledgements

Inspired by: Fast interpolation

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!