On data sparsification and a recursive algorithm for estimating a kernel-based measure of independence

Technological improvements have led to situations where data sets are sufficiently rich that in the interests of processing speed it is desirable to throw away samples that provide little additional information. This is referred to here as data sparsification. The first contribution is a study of a recently proposed data sparsification scheme; ideas from vector quantisation are used to assess its performance. Informed by this study, a modification of the data sparsification algorithm is proposed and applied to the problem of estimating a kernel-based measure of independence of two datasets. (Given i.i.d. observations from two random variables, x and y, the underlying problem is to determine whether or not x and y are independent of each other.) The second contribution of this paper is to make recursive an existing algorithm for measuring independence and able to operate on both raw data and on sparsified data generated by the aforementioned data sparsification algorithm. Compared with the original algorithm, the recursive algorithm is significantly faster due to its lower memory and computational requirements.