Speeding up Permutation Testing in Neuroimaging *
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.
general comments: i love this paper, and i 
      think it makes a great contribution. in particular, the matrix completion 
      and optimization communities have mostly focused on estimation problems, 
      rather than testing problems. this is a beautiful example of how the novel 
      developments in one field can make substantial contributions to another 
      field. note that i haven't read the supplement and i am not an expert in 
      matrix completion, though i do know some stats and neuroscience. 
      major comments: -- the authors comment, "We believe this 
      is due to the approximate estimate of bias from training module." there 
      are several possible sources of error, including model misspecification, 
      approximation error (even given the true model), and sampling error. it 
      will be interesting to investigate when these errors arise, their relative 
      impact, how to mitigate and parse them, etc. some synthetic data analysis 
      would be a most welcome addition; i imagine the full journal length 
      version of this work would include that. -- t-tests are ubiquitous 
      and great, and obviously problematic. here, perhaps less problematic, as 
      rather than modeling the distribution of the data, the authors are 
      modeling the distribution of the residuals. thus, already, perhaps this 
      test is "robust" in certain ways (to the assumption of gaussian 
      distributed data). yet, robust isn't mentioned in the manuscript. i think 
      this method is robust to certain very simple assumptions, and that point 
      should be highlighted and explored if i am correct. -- the data 
      sets that were used are perfectly fine. however, no ground truth is 
      available for them. so, to complement a synthetic data analysis, a real 
      data analysis with ground truth would be excellent. my favorite example of 
      such an endeavor is from: @article{Eklund2012a, author = {Eklund, 
      Anders and Andersson, Mats and Josephson, Camilla and Johannesson, Magnus 
      and Knutsson, Hans}, journal = {NeuroImage}, month = apr, 
      number = {3}, pages = {565--578}, pmid = {22507229}, 
      publisher = {Elsevier Inc.}, title = {{Does parametric fMRI 
      analysis with SPM yield valid results?-An empirical study of 1484 rest 
      datasets.}}, url = {http://www.ncbi.nlm.nih.gov/pubmed/22507229}, 
      volume = {61}, year = {2012} } using this data, one 
      can check how accurate the permutation tests are, and then how much 
      accuracy degrades via this method. -- the figures could be 
      improved. the checklist available at: 
      http://buddhabaki.tumblr.com/post/44143989765/top-20-figure-checklist 
      could help. specifically, fonts are too small, graphics are not vector 
      graphics, symbols are not so obviously different, color choices might be 
      hard for color blind people, axis labels and titles are missing or could 
      be improved. streaming comments: -- Bonferoni, FWER, 
      and other statistical techniques should be defined prior to their 
      introduction, as many in this community are relatively unfamiliar with 
      testing. -- permutation testing is not necessarily sampling from 
      the global null, only in the multiple hypothesis testing scenario. 
      probably worth clarifying. -- "permutation testing ensures" 
      does it really "ensure" this? i haven't thought carefully about 
      whether it is possible in the multiple testing scenario for permutation 
      tests to not capture some dependencies, but i imagine it does not. for 
      example, 3rd order dependencies, given finite samples, wouldn't be 
      captured typically. this is not to say that it is not unbiased, but 
      rather, unbiased doesn't ensure relevant dependencies are carried through; 
      those that are hard to capture might still be missed. please cite 
      something or soften or explain. -- " are required" don't love 
      that either. required for what? high power? yes. unbiased results, not 
      necessarily. please clarify or soften. -- "Observe that if 
      voxel-wise statistics were completely i.i.d., then regardless of their 
      distribution, we could simply compute the distribution of the sample 
      maximum analytically by exponentiating." what do you mean 
      exponentiating the univariate CDF? multiplying? please clarify. also, 
      i think CDF is not defined, only the acronym is given. -- why is 
      "Null" capital? and "Global" seems non-standard to me, but maybe is 
      standard in some literatures. certainly not in the stats textbooks i'm 
      familiar with, eg 'testing statistical hypotheses' is the standard used at 
      many top programs, and is my default for notations & definitions. 
      -- "this subspace. [15, 5]." extra period. -- "In 
      other words, our algorithm does the same job as permutation testing, 
      099 but takes anywhere from a few minutes up to a few hours, rather 
      than days or weeks." but is approximate, and its accuracy will depend 
      on the matrix completion assumptions and algorithms. -- 
      Theorem 3.1 of which paper? i figured it out eventually, but was confused 
      at first, fyi. also, you fluctuate between Thm and Theorem; i prefer 
      consistency. -- "In order to preserve anonymity," while i 
      appreciate preserving anonymity, referring to the studies by a letter does 
      not anonymize, afaict. anonymizing involves stripping headers, and 
      possibly faces, generating unique random IDs, etc. also, punctuation is a 
      bit weird in the following sentence, with a space before the colon only 
      sometimes. -- "How sensitive is the estimated α-level threshold 
      with respect to the recovered Null distribution" how sensitive to 
      what? -- fig 1 shows the KL and BD divergence/distance between the 
      subsampled and the truth? i guess that is implied, but i don't see that 
      explicitly stated. for example, y-axis just gives scale, not quantity. no 
      titles. and the caption doesn't make it clear to me either. -- 
      does 'e^{-5}' mean '10^{-5}'? or really 'e'? i guess that means the log 
      scale is natural log scale. maybe those things are safe to assume in this 
      community, though i wasn't sure. -- "We believe this is due to the 
      approximate estimate of bias from training module." it would be great 
      to investigate the source of this error. simulations would obviously be 
      appropriate for such an investigation. a synthetic data analysis, where 
      the simulation parameters were chosen to match the realized data to the 
      extent possible would be especially interesting. -- i think in 
      your tex file, when writing things like Fig. blah, if you instead write 
      'Fig.\ ' the spacing will look cleaner (i'm just guessing that you are 
      not) -- i think fig 2 might be more impressive on a log scale? the 
      black box thing is weird to me. i've often seen a line break with some 
      twiddles separating, know what i mean? also, the y-axis is 'time', the 
      units are '(minutes)'. on a log scale, the speed-up factor may be explicit 
      in the image? -- i don't think 'upto' is a word. -- "Our 
      experiments suggest that the threshold is stable." i think this 
      sentence belongs *after* showing it, not before? QUALITY: 
      great CLARITY: great ORIGINALITY & SIGNIFICANCE: 
      great