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.