KernelFunctions.jl icon indicating copy to clipboard operation
KernelFunctions.jl copied to clipboard

Symmetry not used to compute self covariance matrix

Open theogf opened this issue 4 years ago • 1 comments

Right now covariance function is computed on every matrix element instead of ~ half of it. This could be improved! cf: https://github.com/theogf/KernelFunctions.jl/blob/9e8dc488cb5f40529be086fcf32954d5471cdf21/src/kernelmatrix.jl#L53 https://github.com/theogf/KernelFunctions.jl/blob/9e8dc488cb5f40529be086fcf32954d5471cdf21/src/kernelmatrix.jl#L15

theogf avatar Sep 06 '19 14:09 theogf

Hard to say how to do this in general / how much of a win this is likely to be. I'm pretty sure that the usual trick (employed by Distances) to cast the pairwise-distance computations as matrix-matrix multiplications (+ a couple of other bits) isn't amenable to only computing the upper / lower triangular of the matrix. The one instance where this is a win is if you're only considering a single input dimension though, I've found that there are gains to be had by just computing half of the covariance matrix in the single-threaded setting. Not sure about multi-threading.

The above being said, there are definitely some optimisations to be had in the symmetric case, they just don't involve only computing half of the covariance matrix. See, for example, here and here. I've just made calls to Distances, but I've found it to be quite important to use the single-argument interface as Distances is able to optimise for this + ensure the diagonal is numerically zero.

willtebbutt avatar Sep 06 '19 14:09 willtebbutt