Abstract
How many samples are sufficient to guarantee that the eigenvectors and eigenvalues of the sample covariance matrix are close to those of the actual covariance matrix? For a wide family of distributions, including distributions with finite second moment and distributions supported in a centered Euclidean ball, we prove that the inner product between eigenvectors of the sample and actual covariance matrices decreases proportionally to the respective eigenvalue distance. Our findings imply non-asymptotic concentration bounds for eigenvectors, eigenspaces, and eigenvalues. They also provide conditions for distinguishing principal components based on a constant number of samples.
Introduction
In high-dimensional data analysis, estimating the true covariance matrix $C$ of a distribution is a fundamental task. Standard results in matrix concentration suggest that to obtain a reliable estimate of the entire matrix, the number of samples $m$ must be proportional to the dimension $n$ (i.e., $m = O(n)$). However, in many practical applications like signal processing and machine learning, Principal Component Analysis (PCA) remains effective even when the sample size is significantly smaller than the dimensionality.
This paper addresses this discrepancy by investigating the sample complexity required to estimate specific eigenvectors and eigenvalues rather than the full matrix. The authors provide non-asymptotic guarantees, showing that the most significant principal components can often be recovered with far fewer samples than previously thought, provided the eigenvalues are well-separated.
Theoretical Framework: Refined Perturbation and Localization
The core of the paper's contribution lies in combining refined perturbation analysis with non-asymptotic concentration of measure.
Refined Perturbation Bounds
Traditional tools, such as the Davis-Kahan $\sin(\Theta)$ theorem, typically bound the error of an estimated subspace based on the minimum gap between eigenvalues. This paper introduces a more granular approach. Theorem 3.2 establishes that the inner product between a sample eigenvector $\tilde{u}_i$ and a true eigenvector $u_j$ is inversely proportional to their specific eigenvalue distance $|\lambda_i - \lambda_j|$. Specifically, the number of samples $m$ required to ensure a small error in an eigenvector is $O(k_j^2 / (\lambda_i - \lambda_j)^2)$, where $k_j$ relates to the kurtosis in that direction.
Spectral Localization
A key insight is the concept of "spectral leaking." The authors prove that this leaking—where a sample eigenvector $\tilde{u}_i$ becomes "confused" with a true eigenvector $u_j$—is strongly localized. A sample eigenvector is highly unlikely to leak into the span of a true eigenvector if their corresponding eigenvalues are far apart on the spectrum. This localization allows for the recovery of top eigenvectors even in the presence of many other dimensions, as long as the top eigenvalues are sufficiently separated from the rest.
Empirical Results on MNIST
To validate these theoretical findings, the authors conducted experiments using the MNIST database of handwritten digits. Focusing on the pixel distributions for digits '1' and '3' ($n = 784$), they demonstrated that the primary principal components can be estimated accurately with very few samples.
As shown in the figure above, even with $m=10$ or $m=100$ samples (well below the $n=784$ threshold), the first few sample eigenvectors show significant alignment with their true counterparts. The peaks in the plots correspond to the inner product $|\langle \tilde{u}_i, u_j \rangle|$ being highest when $i=j$. As $m$ increases from 10 to 1000, these peaks become sharper and the "leaking" to other eigenvectors (non-zero values at other $\lambda_j$) diminishes and remains localized around the true eigenvalue.
Key Insights
- Eigenvalue Separation: The "direction" of data with high variance is easier to identify with fewer samples.
- Kurtosis and Heavy Tails: The estimation difficulty is influenced by the distribution's kurtosis in a given direction; heavy-tailed distributions require more samples.
- Breaking the Dimension Curse: For approximately low-rank datasets, the sample requirement depends on the spectral properties (eigenvalues) rather than the raw dimensionality $n$.
Conclusion
This work provides a theoretical foundation for why PCA is often successful in high-dimensional regimes with limited data. By proving that eigenvector error is localized and dependent on individual eigenvalue gaps, the authors offer a more optimistic view of sample complexity for principal component estimation. Future work may involve sharpening the multiplicative constants in these bounds and applying this framework to downstream tasks like high-dimensional regression and fast projection algorithms.
Summary updated