Cool paper on fast covariance computation for sliding window based features

Thought I’d share a cool paper I came across this week. Fast Covariance Computation and Dimensionality Reduction for Sub-Window Features in Images.


  • Trick to speed up calculation of covariance matrix of features when your features come from a sliding windows over a signal (image).
  • Trick takes advantage of redundant information between windows and reduces the covariance calculation to a look up table and/or an autocorrelation function (which can be calculated by FFT).
  • Complexity drops from O(nd^2) to O(nd) or O(n log(n)) where n is image size and d is windows size, which can be significant for large window sizes.


Leave a Reply

Your email address will not be published. Required fields are marked *