Same functionality as built-in MATLAB function 'interp1q' but 3x faster.
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.
1.1 | Minor modifications to the description to clarify the effect of NaN. |
Jose M. Mier (view profile)
Hi Yair, and thank you for your contribution to 'interp1qr'. Those two functions that you mentioned are very useful indeed. However, I think your comment is not fair when you try to compare them with 'interp1qr' since you are not comparing functions with the same functionality. I had a quick look at the two functions you mentioned and observed the following important differences:
1) nakeinterp1:
- As far as I can see, that function can only handle 'y' as a single-column vector, while 'interp1q' and 'interp1qr' allow 'y' to be a matrix with multiple columns.
- Also, that function is a mex-file, while 'interp1qr' is an m-file. I'm not an expert with mex-files, but I believe this format allows functions to run faster, just because of the format, and not because of the code itself. This in itself is a good thing, but doesn't necessarily make the code to be better.
- Additionally, for some users the use of mex-files may be intimidating or more difficult to work with than a simple m-file, which is the standard file format everybody is used to work with in MATLAB.
2) ScaleTime:
- That function has one MAJOR limitation, which is that the input data vector 'x' must be equally spaced. This is not a limitation for 'interp1q' or 'interp1qr', which can take any spacing of the input data as long as it is monotonically increasing.
Finally, the fact that one can use 'interp1qr' as a direct replacement for 'interp1q' with speed increments of minimum 3x and up to 10x without touching anything else in your code is a strong argument in favor of using 'interp1qr'. This is specially important when the user is not 100% confident that the input data is suitable for 'ScaleTime' or 'nakeinterp1'.
I hope this helps you understand the reason for existence of this function, which is perfectly compatible with the existence of 'ScaleTime' or 'nakeinterp1'. Neither one is better than the others, they are just made for different purposes.
Yair Altman (view profile)
While not disparaging the importance of Jose's interp1qr, users might also find interest in the following alternatives that are even faster (by a wide margin):
1) Bruno Luong's nakeinterp1 - http://mathworks.com/matlabcentral/newsreader/view_thread/258413#672827
2) Jan Simon's ScaleTime - http://mathworks.com/matlabcentral/fileexchange/25463-scaletime
Again - I am not trying to disparage interp1qr: this is an important utility, if only for being a faster drop-in replacement to the built-in function. It is simply that the utilities by Matlab performance gurus Luong and Simon are even better...
Dimitrios (view profile)
Eric Sampson (view profile)
Works great, an easy drop-in replacement for interp1q, and is definitely faster for me.
Ryan Muir (view profile)
Works well!
Mauricio Perillo (view profile)
Nils Oberg (view profile)