Sampling without replacement from a high-dimensional finite population

Jiang Hu, Shaochen Wang, Yangchun Zhang, Zhou Wang

TL;DR

This paper provides a rigorous theoretical foundation for high-dimensional statistics when sampling without replacement from a finite population—a common real-world scenario that contradicts standard "infinite population" assumptions. The authors prove that the largest eigenvalues of these sample covariance matrices follow the Tracy-Widom law, offering a mathematical justification for popular heuristic techniques like Parallel Analysis used in factor discovery.

What Problem Does This Paper Address?

Most classical statistical theories are built on a convenient fiction: that we are sampling with replacement from an infinite population. In practice, researchers often deal with finite populations (e.g., a specific cohort of patients or a fixed set of genomic markers) and sample without replacement.

When the number of features ($p$) is very large—potentially even larger than the number of samples ($n$)—traditional multivariate statistics fail. Specifically, the "edge" of the spectrum (the largest eigenvalues) is used to distinguish true signal from random noise. Until now, there was a gap in understanding whether the well-known laws of Random Matrix Theory (RMT) still applied to these finite-population, high-dimensional covariance matrices where entries are inherently correlated due to the sampling method.

Methods

The authors employ tools from Random Matrix Theory (RMT) to analyze the spectral properties of the sample covariance matrix $S_n$. Their approach involves:

  • Asymptotic Analysis: They study the regime where both the dimension ($p$) and sample size ($n$) tend toward infinity at a proportional rate ($p/n \to c$).
  • Tracy-Widom Law Derivation: They prove that the fluctuations of the largest eigenvalue of $S_n$ converge to the Tracy-Widom distribution, which is the standard limit for the "edge" of random matrices.
  • Green Function Comparison: To prove "universality" (showing the result holds regardless of the specific distribution of the population), they use a sophisticated comparison strategy. This involves showing that the matrix of interest behaves like a Gaussian reference matrix at the spectral edge.
  • Parallel Analysis (PA) Application: They apply these results to the permutation methods used in PA, where rows of a data matrix are shuffled to create a "noise-only" baseline.

Datasets

  • Simulated Data: Extensive simulations were used to verify that the empirical distribution of eigenvalues matches the theoretical Tracy-Widom curve as $n$ and $p$ increase.
  • HGDP (Human Genome Diversity Project): The authors used a real-world genetic dataset containing 1,043 samples and 9,730 SNPs (Single Nucleotide Polymorphisms) from chromosome 22. This dataset represents a classic high-dimensional ($p > n$) scenario where sampling is effectively from a finite population of genetic variations.

Key Insights and Ideas

  • Robustness of the Tracy-Widom Law: The most significant "aha moment" is that the Tracy-Widom law is incredibly robust. Even though sampling without replacement introduces correlations between samples (violating the i.i.d. assumption), the largest eigenvalues still behave as if they came from an infinite, independent population.
  • Theoretical Grounding for Heuristics: Parallel Analysis (PA) has been a popular "rule of thumb" for decades to decide how many factors to keep in a model. This paper provides the rigorous mathematical proof for why the permutation step in PA works: it essentially forces the matrix into a regime governed by the Tracy-Widom law.
  • Extension to Spearman’s Rho: The authors show their results naturally extend to Spearman’s rank correlation matrices, which are frequently used in non-parametric statistics.

Key Results

  • Theorem 2.3 & 2.6: These are the core results, establishing that for both standard and spatial-sign covariance matrices, the largest eigenvalue (properly scaled and centered) follows the Tracy-Widom distribution.
  • Empirical Fit: In the HGDP dataset analysis, the authors demonstrated that the numerical distribution of the largest eigenvalue from 5,000 permutations fit the theoretical Tracy-Widom distribution remarkably well (see Figure 1 in the paper).
  • Computational Efficiency: The results suggest that researchers might eventually skip the "massive permutation computations" usually required for Parallel Analysis and instead use theoretical Tracy-Widom quantiles to determine the significance of their factors.

Limitations and Future Work

  • Centralization Requirement: The current proofs rely on the data being centralized (shifted by the mean). The authors note that proving these results for non-centralized matrices is more technically challenging and remains a task for future work.
  • Signal-to-Noise Restrictions: While the paper handles the "noise" part of the signal-plus-noise model well, the authors suggest that adding more specific restrictions on the "signal" matrix could lead to even more refined results for factor analysis.
  • Alternative PA Methods: The paper mentions newer variants like Derandomized Parallel Analysis (DPA). Future work could explore how these theoretical results can further optimize or validate these faster, more reproducible alternatives.

Summary updated

Abstract

It is well known that most of the existing theoretical results in statistics are based on the assumption that the sample is generated with replacement from an infinite population. However, in practice, available samples are almost always collected without replacement. If the population is a finite set of real numbers, whether we can still safely use the results from samples drawn without replacement becomes an important problem. In this paper, we focus on the eigenvalues of high-dimensional sample covariance matrices generated without replacement from finite populations. Specifically, we derive the Tracy-Widom laws for their largest eigenvalues and apply these results to parallel analysis. We provide new insight into the permutation methods proposed by Buja and Eyuboglu in [Multivar Behav Res. 27(4) (1992) 509–540]. Simulation and real data studies are conducted to demonstrate our results.
BibTeX
@inproceedings{hu2023sampling,
  author = {Jiang Hu and Shaochen Wang and Yangchun Zhang and Zhou Wang},
  title = {{Sampling without replacement from a high-dimensional finite population}},
  booktitle = {Bernoulli},
  year = {2023},
  doi = {10.3150/22-bej1580},
}

Loading related content...

Figure