title: Speeding up Permutation Testing in Neuroimaging.
abstract: Multiple hypothesis testing is a significant problem in nearly all neuroimaging studies. In order to correct for this phenomena, we require a reliable estimate of the Family-Wise Error Rate (FWER). The well known Bonferroni correction method, while simple to implement, is quite conservative, and can substantially under-power a study because it ignores dependencies between test statistics. Permutation testing, on the other hand, is an exact, non-parametric method of estimating the FWER for a given α-threshold, but for acceptably low thresholds the computational burden can be prohibitive. In this paper, we show that permutation testing in fact amounts to populating the columns of a very large matrix P. By analyzing the spectrum of this matrix, under certain conditions, we see that P has a low-rank plus a low-variance residual decomposition which makes it suitable for highly sub-sampled - on the order of 0.5% - matrix completion methods. Based on this observation, we propose a novel permutation testing methodology which offers a large speedup, without sacrificing the fidelity of the estimated FWER. Our evaluations on four different neuroimaging datasets show that a computational speedup factor of roughly 50× can be achieved while recovering the FWER distribution up to very high accuracy. Further, we show that the estimated α-threshold is also recovered faithfully, and is stable.
authors.affiliation: University of Wisconsin-Madison.
authors.forename: Chris
authors.initials: C
authors.lastname: Hinrichs
authors.affiliation: University of Wisconsin-Madison.
authors.forename: Vamsi K
authors.initials: VK
authors.lastname: Ithapu
authors.affiliation: University of Wisconsin-Madison.
authors.forename: Qinyuan
authors.initials: Q
authors.lastname: Sun
authors.affiliation: William S. Middleton Memorial VA Hospital.|University of Wisconsin-Madison.
authors.forename: Sterling C
authors.initials: SC
authors.lastname: Johnson
authors.affiliation: University of Wisconsin-Madison.
authors.forename: Vikas
authors.initials: V
authors.lastname: Singh