Add fast HSIC

[brian-lau]

https://github.com/devinjacobson/prediction/tree/master/correlations/samplecode/NIPS2011-code/code-nips2011

[wittawatj]

I have not read the paper you posted. Since you put as the title "fast HSIC", I just want to point out

Large-Scale Kernel Methods for Independence Testing
Qinyi Zhang, Sarah Filippi, Arthur Gretton, Dino Sejdinovic
https://arxiv.org/abs/1606.07892

This paper discusses many variants of HSIC.

• HSIC + random Fourier features
• HSIC + Nystrom approximation
• Block HSIC that asymptotically runs in linear time (wrt sample size)

The first two are linear-time wrt sample size, with quadratic dependency on the number of features (or number of inducing points in Nystrom). The last one does not have good power because of its high variance (this is mentioned in the paper).

[brian-lau]

Thanks for the reference! I haven't looked at the paper either, but I'm pretty sure the fastHSIC in the link is not linear-time, so I will definitely have a look at the Zhang paper.