Factor selection by permutation

Edgar Dobriban

Abstract

Researchers often have datasets measuring features $x_{ij}$ of samples, such as test scores of students. In factor analysis and PCA, these features are thought to be influenced by unobserved factors, such as skills. Can we determine how many components affect the data? This is an important problem, because it has a large impact on all downstream data analysis. Consequently, many approaches have been developed to address it. Parallel Analysis is a popular permutation method. It works by randomly scrambling each feature of the data. It selects components if their singular values are larger than those of the permuted data. Despite widespread use in leading textbooks and scientific publications, as well as empirical evidence for its accuracy, it currently has no theoretical justification. In this paper, we show that the parallel analysis permutation method consistently selects the large components in certain high-dimensional factor models. However, it does not select the smaller components. The intuition is that permutations keep the noise invariant, while destroying the low-rank signal. This provides justification for permutation methods in PCA and factor models under some conditions. Our work uncovers drawbacks of permutation methods, and paves the way to improvements.

Introduction

In fields ranging from psychology to genomics, researchers use Factor Analysis (FA) and Principal Component Analysis (PCA) to find hidden patterns—or factors—in large datasets. A fundamental challenge in these analyses is determining the correct number of factors to retain. Retaining too many leads to overfitting, where noise is mistaken for signal, while retaining too few ignores vital information.

Since its introduction in 1965, Parallel Analysis (PA) has been a preferred heuristic for this task. It operates by comparing the singular values of the original data against those of a "null" version created by shuffling the data. Despite its empirical success, PA has lacked a rigorous mathematical foundation. Edgar Dobriban's paper, "Factor selection by permutation," provides the first theoretical proof of why and when PA works, particularly in high-dimensional settings.

The Parallel Analysis Mechanism

The core idea behind PA is that random permutations effectively "destroy" structured signals while leaving background noise relatively intact. By modeling the data matrix $X$ as a combination of signal and noise ($X = S + N$), the paper evaluates the PA algorithm through a three-step process:

  1. Permutation: Entries within each column of the data are randomly shuffled to create a new matrix, $X_\pi$.
  2. Comparison: The singular values ($\sigma_k$) of the original data $X$ are compared against the singular values of the shuffled data $X_\pi$.
  3. Selection: A factor is kept if its singular value is significantly larger than the corresponding singular value of the shuffled data (often using a high percentile as a threshold).
Singular values of original data $X$ vs. permuted data $X_\pi$.

As shown in Figure 1, the first few singular values of the original data (dashed line) stand out clearly above the noise floor established by the permuted data (solid line). As the index $k$ increases, the signal is exhausted, and the singular values of $X$ converge to those of $X_\pi$.

Why Permutation Works: Signal Destruction

The "magic" of permutation lies in its ability to transform a "smooth" low-rank signal into a "rough," noise-like matrix. While the total energy (Frobenius norm) of the signal remains constant, its peak strength (operator norm) drops drastically upon shuffling.

Visual representation of signal destruction: (a) structured signal $S$ and (b) its permuted version $S_\pi$.

Figure 2 illustrates this effect: a structured signal $S$ with clear patterns becomes indistinguishable from noise after permutation ($S_\pi$). This transformation allows the background noise level to be accurately estimated, providing a clear benchmark for identifying significant factors.

Key Insights and Theoretical Results

The paper uses asymptotic analysis—examining behavior as the number of samples $n$ and features $p$ grow toward infinity—to establish several key findings:

  • Theoretical Consistency: Theorem 2.1 formally proves that PA selects all significant factors with high probability, provided the factors are "delocalized" (influencing many variables) and the noise is invariant under permutation.
  • The Blessing of Dimensionality: PA actually becomes more reliable as the number of variables ($p$) increases. In low-dimensional settings, the method is significantly less consistent.
  • Robustness to Sparsity: Simulations demonstrate that PA can identify factors even when they affect as few as 2% of the variables in a dataset.
  • The Shadowing Effect: A notable limitation discovered is that extremely strong factors can bias the noise estimate. The "destroyed" version of a very strong signal might still be large enough to "shadow" or hide weaker signals, leading PA to undercount the total number of factors.

Conclusion and Future Directions

While providing a long-awaited justification for Parallel Analysis, this work also highlights areas for improvement. The "shadowing effect" suggests that a "deflation" approach—removing the strongest factors before re-running PA—might enhance accuracy. Furthermore, while the current theory assumes relatively independent noise, future research could extend these findings to datasets with complex noise structures, such as time-series data, perhaps by incorporating Fourier transforms before shuffling. Finally, the computational cost of repeated SVDs on large datasets remains a challenge, inviting the development of faster approximation methods for the shuffled noise floor.

Summary updated

Abstract

Researchers often have datasets measuring features $x_{ij}$ of samples, such as test scores of students. In factor analysis and PCA, these features are thought to be influenced by unobserved factors, such as skills. Can we determine how many components affect the data? This is an important problem, because it has a large impact on all downstream data analysis. Consequently, many approaches have been developed to address it. Parallel Analysis is a popular permutation method. It works by randomly scrambling each feature of the data. It selects components if their singular values are larger than those of the permuted data. Despite widespread use in leading textbooks and scientific publications, as well as empirical evidence for its accuracy, it currently has no theoretical justification. In this paper, we show that the parallel analysis permutation method consistently selects the large components in certain high-dimensional factor models. However, it does not select the smaller components. The intuition is that permutations keep the noise invariant, while destroying the low-rank signal. This provides justification for permutation methods in PCA and factor models under some conditions. Our work uncovers drawbacks of permutation methods, and paves the way to improvements.
BibTeX
@article{dobriban2020factor,
  author = {Edgar Dobriban},
  title = {{Factor selection by permutation}},
  journal = {The Annals of Statistics},
  year = {2020},
  doi = {10.1214/19-aos1907},
}
Figure