Doing a permutation test with the general linear model (GLM) in the presence of nuisance variables can be challenging. Let the model be:
where is a matrix of observed variables,
is a matrix of predictors of interest,
is a matrix of covariates (of no interest), and
is a matrix of the same size as
with the residuals.
Because the interest is in testing the relationship between and
, in principle it would be these that would need be permuted, but doing so also breaks the relationship with
, which would be undesirable. Over the years, many methods have been proposed. A review can be found in Winkler et al. (2014); other previous work include the papers by Anderson and Legendre (1999) and Anderson and Robinson (2001).
One of these various methods is the one published in Freedman and Lane (1983), which consists of permuting data that has been residualised with respect to the covariates, then estimated covariate effects added back, then the full model fitted again. The procedure can be performed through the following steps:
- Regress
against the full model that contains both the effects of interest and the nuisance variables, i.e.,
. Use the estimated parameters
to compute the statistic of interest, and call this statistic
.
- Regress
against a reduced model that contains only the covariates, i.e.
, obtaining estimated parameters
and estimated residuals
.
- Compute a set of permuted data
. This is done by pre-multiplying the residuals from the reduced model produced in the previous step,
, by a permutation matrix,
, then adding back the estimated nuisance effects, i.e.
.
- Regress the permuted data
against the full model, i.e.
- Use the estimated
to compute the statistic of interest. Call this statistic
.
- Repeat the Steps 2-4 many times to build the reference distribution of
under the null hypothesis of no association between
and
.
- Count how many times
was found to be equal to or larger than
, and divide the count by the number of permutations; the result is the p-value.
Steps 1-4 can be written concisely as:
where is a permutation matrix (for the
-th permutation,
is the hat matrix due to the covariates, and
is the residual forming matrix; the superscript symbol
represents a matrix pseudo-inverse.
In page 385 of Winkler et al. (2014), my colleagues and I state that:
[…] add the nuisance variables back in Step 3 is not strictly necessary, and the model can be expressed simply as
, implying that the permutations can actually be performed just by permuting the rows of the residual-forming matrix
.
However, in the paper we do not offer any proof of this important result, that allows algorithmic acceleration. Here we remedy that. Let’s start with two brief lemmata:
Lemma 1: The product of a hat matrix and its corresponding residual-forming matrix is zero, that is, .
This is because , hence
since
is idempotent.
Lemma 2 (Frisch–Waugh–Lovell theorem): Given a GLM expressed as , we can estimate
from an equivalent GLM written as
.
To see why, remember that multiplying both sides of an equation by the same factor does not change it (least squares solutions may change; transformations using Lemma 2 below do not act on the fitted model). Let’s start from:
Then remove the parentheses:
Since :
and that :
Since :
where .
Main result
Now we are ready for the main result. The Freedman-Lane model is:
Per Lemma 2, it can be rewritten as:
Dropping the parenthesis:
Per Lemma 1:
What is left has the same form as the result of Lemma 2. Thus, reversing it, we obtain the final result:
Hence, the hat matrix cancels out, meaning that it is not necessary. Results are the same both ways.
References
- Anderson MJ, Legendre P. An empirical comparison of permutation methods for tests of partial regression coefficients in a linear model. Journal of Statistical Computation and Simulation 1999;62(3):271–303.
- Anderson MJ, Robinson J. Permutation tests for linear models. Australian & New Zealand Journal of Statistics of Statistics 2001;43(1):75–88.
- Freedman D, Lane D. A Nonstochastic Interpretation of Reported Significance Levels. Journal of Business & Economic Statistics 1983;1(4):292.
- Winkler AM, Ridgway GR, Webster MA, Smith SM, Nichols TE. Permutation inference for the general linear model. NeuroImage 2014;92:381–97.
Updates
- 07.Jun.2020: A graphical representation of Lemma 1 can be found in p.40 of Jaromil Frossard PhD thesis (Université de Genève), available here.
- 07.Jun.2020: Lemma 2 corresponds to the Frisch–Waugh–Lovell theorem. Thanks to Samuel Davenport (University of Oxford) for pointing out.