Finite sample approximation results for principal component analysis: a matrix perturbation approach

By Boaz Nadler. 2009

338 citations recorded by the source corpus.

Principal component analysis (PCA) is a standard tool for dimensional reduction of a set of $n$ observations (samples), each with $p$ variables. In this paper, using a matrix perturbation approach, we study the nonasymptotic relation between the eigenvalues and eigenvectors of PCA computed on a finite sample of size $n$, and those of the limiting population PCA as $n\to\infty$. As in machine learning, we present a finite sample theorem which holds with high probability for the closeness between the leading eigenvalue and eigenvector of sample PCA and population PCA under a spiked covariance model. In addition, we also consider the relation between finite sample PCA and the asymptotic results in the joint limit $p,n\to\infty$, with $p/n=c$. We present a matrix perturbation view of the "phase transition phenomenon," and a simple linear-algebra based derivation of the eigenvalue and eigenvector overlap in this asymptotic limit. Moreover, our analysis also applies for finite $p,n$ where we show that although there is no sharp phase transition as in the infinite case, either as a function of noise level or as a function of sample size $n$, the eigenvector of sample PCA may exhibit a sharp "loss of tracking," suddenly losing its relation to the (true) eigenvector of the population PCA matrix. This occurs due to a crossover between the eigenvalue due to the signal and the largest eigenvalue due to noise, whose eigenvector points in a random direction.

Subfields: Computational Mathematics, Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/7c0f5b508303c35da77fa775fa08fdfa5f6b37db

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Anisotropic diffusion on sub-manifolds with application to Earth structure classification (2012, background): “Clearly, the correct estimation of the noise covariance matrix from given data is limited and depends on the size of the data sample (see, for example, [15,16]).”
Statistical inference for principal components of spiked covariance matrices (2020, background): “[61] B.”
Fundamental limits of detection in the spiked Wigner model (2018, background): “Estimation using the top eigenvector undergoes the same transition, where it is known to “lose track” of the spike below the spectral threshold (Paul, 2007; Nadler, 2008; Johnstone and Lu, 2009; Benaych-Georges and Nadakuditi, 2011).”
Regression on manifolds: Estimation of the exterior derivative (2011, methodology): “PCR cannot be easily extended to have lasso-type regularization.”
Selecting the number of principal components: estimation of the true rank of a noisy matrix (2014, methodology): “In simulation studies we find that our proposed method compares well to the proposal of Kritchman & Nadler (2008), which uses the asymptotic distribution of singular values based on the Tracy-Widom laws.”
On Consistency and Sparsity for Principal Components Analysis in High Dimensions (2009, result): “While this article was in publication review, subsequent rigorous proofs were published, along with other results, by Paul (2007) and Nadler (2008).”
On the principal components of sample covariance matrices (2014, result): “Moreover, in [9,32] result analogous to those of [8] were obtained for the model from Example (2).”
Estimating structured high-dimensional covariance and precision matrices: Optimal rates and adaptive estimation (2016, background): “…considered in Johnstone (2001) and have been studied by several papers under the sparse principal component analysis setting, including Paul (2007), Nadler (2008), Johnstone and Lu (2009), Amini andWainwright (2009), Birnbaum et al. (2013), Ma (2013), Vu and Lei (2013), Cai et al. (2013), Berthet…”
Asymptotic power of sphericity tests for high-dimensional data (2013, background): “…of recent studies in various applied fields including population and medical genetics [Patterson, Price and Reich (2006)], econometrics [Onatski (2009, 2010)], wireless communication [Bianchi et al. (2011)], chemometrics [Kritchman and Nadler (2008)] and signal processing [Perry and Wolfe (2010)].”
Sparse Principal Component Analysis and Iterative Thresholding (2011, background): “When both n, p → ∞ with n/p → c ∈ (0 , ∞ ), at diﬀerent levels of rigor and generality, this phenomenon has been examined by a number of authors [27, 17, 11, 23, 19, 21] under model (1.2).”
Determining the number of components in a factor model from limited noisy data (2008, methodology): “Thus, following common practice of many other algorithms, we present a method to infer the number of components only from the eigenvalues of Sn, denoted ℓj p j¼1, and sorted in decreasing order ℓ1⩾ℓ2⩾⋯⩾ℓp.”
Random matrix theory in statistics: A review (2014, methodology): “Nadler (2008) used a finite sample asymptotic framework by allowing s2-0 in (33).”
Sparse PCA: Optimal rates and adaptive estimation (2012, background): “This estimate works because σ1(S) − 2 is an over-estimate of λ with high probability [39, 43], since the noise variance here is two.”
The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices (2009, background): “This trick cannot be applied for Wishart matrices since Wishart matrices do not exhibit the symmetries of Wigner matrices.”
Active Subspace Methods in Theory and Practice: Applications to Kriging Surfaces (2013, methodology): “ient is too small. However, a thorough analysis of these errors is beyond the scope of the present work. We anticipate that results from classical perturbation theory for eigenvalues and eigenvectors [29] will prove useful. 3.2. Building a response surface. In this section, we detail a procedure to ”
Nonasymptotic upper bounds for the reconstruction error of PCA (2016, background): “Nadler [27] obtains non-asymptotic bounds for the spiked covariance model and studies phase transitions when dimension and sample size tend to infinity simultaneously.”