Title: MultiFIT: A Multivariate Multiscale Framework for Independence Tests,
Abstract: We present a framework for testing independence between two random vectors
that is scalable to massive data. We break down the multivariate test into
univariate tests of independence on a collection of $2\times 2$ contingency
tables, constructed by sequentially discretizing the sample space. This
transforms a complex problem that traditionally requires quadratic
computational complexity with respect to the sample size into one that scales
almost linearly with the sample size. We further consider the scenario when the
dimensionality of the random vectors grows large, in which case the curse of
dimensionality arises in the proposed framework through an explosion in the
number of univariate tests to be completed. To overcome this difficulty we
propose a data-adaptive version of our method that completes a fraction of the
univariate tests judged to be more likely to contain evidence for dependency.
We demonstrate the tremendous computational advantage of the algorithm in
comparison to existing approaches while achieving desirable statistical power
through an extensive simulation study. In addition, we illustrate how our
method can be used for learning the nature of the underlying dependency. We
demonstrate the use of our method through analyzing a data set from flow
cytometry.