Overview

Permutation tests are computationally intensive. For small, non-imaging datasets, recomputing a model thousands of times is seldom a problem, but for large, complex models this can be prohibitively slow, even with the availability of inexpensive computing power. PALM offers the possibility of accelerating the inference through properties of statistics used with the general linear model (GLM) and their distributions, in a way that is irrespective of software or hardware improvements.

In the table, CMV stands for Classical Multivariate Tests (such as MANOVA, MANCOVA, CCA), whereas NPC stands for Non-Parametric Combination. See here for details.

The figure below summarises the methods: With permutations (i.e., few permutations, negative binomial, and low rank matrix completion), the p-value is the fraction of the test statistics obtained after permuting that are higher than in the unpermuted. In the tail approximation, the tail of the permutation distribution is subjected to the fit of a generalised Pareto distribution (GPD), from which the p-values are computed. In the method in which no permutations are performed, the first three moments of the permutation distribution are computed from data and model, and to these which a gamma distribution is fitted, and from which the p-values are computed. In the gamma approximation, the moments of the empirical permutation distribution are used to the fit of the gamma distribution. The figure is merely illustrative: the actual fit uses the cumulative distribution function directly, such that histograms are not constructed.

Methods available

Few permutations

This method consists of simply choosing a small number of permutations, e.g., less than 1000. To run, use:

palm [...] -n 500

Negative binomial

This method consists of running as many permutations as needed until a fixed, pre-defined number of exceedances is found. An exceedance is an event in which the statistic after permutation is larger or equal than in the unpermuted case. The procedure continues until all possible permutations have been exhausted, or until a very large limit is reached. To run, use:

palm [...] -accel negbin [nexced]

If the number of exceedances is omitted, the default is 2. The number of permutations to keep trying can be indicated with the option -n, but in this case, it would be a large number. For example:

palm [...] -accel negbin 4 -n 100000

Tail approximation

This method consists of running a number of permutations, then fitting a Generalised Pareto Distribution (GPD) to the tail of the distribution. The p-values are computed from the GPD. To run, use:

palm [...] -accel tail [pthr]

The parameter pthr indicates the permutation p-value below which the GPD fit will be used. For the permutation p-values above this number, there will be no changes. The default pthr (if omitted) is 0.10.

The number of permutations used to build the initial null distribution is controlled by the option -n:

palm [...] -accel tail -n 500

For large datasets, or for a large number of permutations, this method can be memory intensive for uncorrected and for FDR corrected p-values. In these cases, consider using the option -nouncorrected:

palm [...] -accel tail -n 500 -nouncorrected

No permutation

This method consists of first computing analytically the first three moments of the permutation distribution of test statistics that can be written in the form trace(AW), where A = X*pinv(X), W = UU', USV = svd(RY), R = I-Z*pinv(Z), and I is the identity matrix of size N, where N is the number of subjects. Once the moments have been estimated, gamma distribution (also known as Pearson type III distribution) with same moments is used to calculate the p-values. Differently than all other methods, permutations are not actually performed, yet the p-values are based on permutations. To run, use:

palm [...] -accel noperm

This method cannot be used in cases in which only sign-flippings would be used (-ise), nor with exchangeability blocks or variance groups, and cannot be used to test the intercept (i.e., the intercept must be entirely contained in the set of nuisance variables, but not among the variables of interest). The test can be used when the distribution of the errors is symmetric as a replacement to permutations.

Gamma approximation

This method consists of running a number of permutations, then fitting a gamma distribution to the whole null distribution. The p-values are computed from the gamma distribution. To run, use:

palm [...] -accel gamma

The number of permutations used to build the initial null distribution is controlled by the option -n:

palm [...] -accel gamma -n 500

As with the tail approximation, for large datasets, or for a large number of permutations, this method can also be memory intensive for uncorrected and for FDR corrected p-values. In these cases, consider using the option -nouncorrected:

palm [...] -accel gamma -n 500 -nouncorrected

Low rank matrix completion

This method consists of running a small number of permutations (call this number J0), then for the subsequent permutations, use only a subset containing a small number V0 of voxels. This subset is chosen randomly. The remaining voxels that are not tested have their exact test statistic computed from the others using low rank matrix completion theory. For this method, both J0 and V0 must be larger or equal than N(N+1)/2. To run, use:

palm [...] -accel lowrank [val]

where val is either:

• A positive value less than 1, indicating the fraction of the total tests (usually voxels) that will be randomly sampled.
• An integer greater than 1, indicating the number V0 of tests that will be randomly sampled.

The default val is NaN, indicating that PALM will compute it from the sample size as V0 = N*(N+1)/2. The overall number of permutations (fully sampled plus the ones with values filled in) can be specified with the option -n as usual.

Gains in speed with low rank matrix completion are noticeable only for large images and small number of subjects. Otherwise, the other methods above tend to be faster.

Recommendations

From all the methods, the one that is the most general, applicable to a wider variety of situations, including corrected and uncorrected p-values, spatial and multivariate statistics (classical and NPC), and which also showed overall a good performance and a good tradeoff with resampling risk is the tail approximation, and this method is recommended generally. Other methods can also be considered in a variety of scenarios.

The flow chart below gives overall guidance on which method to use in particular applications.

Advanced usage

The tail and gamma approximation can take one extra argument called "out":

palm [...] -accel tail [pthr] [out]

palm [...] -accel gamma [out]

This is a true/false indicating whether the unpermuted statistic should be left out of the null distribution. The default is false, indicating that the unpermuted statistic is included in the null. This setting rarely (if ever) needs to be changed.

References

The reference for the accelerated permutation tests is:

The main general reference for PALM is the same as for randomise:

For NPC, CMV assessed with permutations, and for correction over contrasts and/or modalities (options -corrcon and -corrmod), the reference is: