  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 $\alpha$-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 ${\bf P}$. By analyzing the spectrum of this
matrix, under certain conditions, we see that ${\bf 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\times$ can be achieved while
recovering the FWER distribution up to very high accuracy. Further, we show
that the estimated $\alpha$-threshold is also recovered faithfully, and is
stable.
