Multiple permutation test for high-dimensional data: a components-combined algorithm

Multiple permutation testing is a test method combining the idea of permutation and multiple testing. It first employs the permutation testing to calculate p-values for single tests, and then determines the result based on criteria of multiple testing. To well control type I error rate, the classical method needs a large number of permutation samples for calculating p-values. When the dimension of data, m, is high, the permutation procedure is very time consuming. This paper proposes a components-combined algorithm for the type I error rate control. The new algorithm only requires a small and fixed number of permutation samples for any dimension of data and can achieve the same approximation accuracy of p-values as the classical method. Therefore, it reduces the computational amount of multiple permutation testing procedures from O(m²) to O(m).. The algorithm is then applied to several testing problems and the power performance is examined by simulations and comparisons with existing methods.