A Review Study of Eigenvalue–Eigenvector Methods in Covariance Matrices and Dimensionality Reduction
Main Article Content
Abstract
Eigenvalue–eigenvector decomposition of covariance matrices lies at the heart of modern statistical analysis, machine learning, and signal processing. This review paper provides a comprehensive survey of the mathematical foundations, computational algorithms, and practical applications of eigenvalue–eigenvector methods in the context of covariance matrices and dimensionality reduction. We systematically trace the development of Principal Component Analysis (PCA) from its inception by Karl Pearson in 1901 to its modern extensions, including Kernel PCA, Sparse PCA, Robust PCA, and Randomized PCA. The review covers the spectral theorem, singular value decomposition (SVD), and their connections to covariance structure learning. Algorithmic approaches—including power iteration, the QR algorithm, Lanczos methods, and randomized numerical linear algebra—are evaluated for their computational complexity and numerical stability. We further examine applications in face recognition, natural language processing, genomic data analysis, image compression, and graph-based learning. Comparative analysis of algorithms across varying data dimensionalities and sample sizes is provided. The paper concludes by identifying open research challenges and emerging directions, including eigenvalue estimation in the high-dimensional regime, federated PCA, and quantum-accelerated decomposition methods.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
References
Ahn, S. C., & Horenstein, A. R. (2013). Eigenvalue ratio test for the number of factors. Econometrica, 81(3), 1203–1227.
Anderson, T. W. (1963). Asymptotic theory for principal component analysis. Annals of Mathematical Statistics, 34(1), 122–148.
Baik, J., Ben Arous, G., & Péché, S. (2005). Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Annals of Probability, 33(5), 1643–1697.
Belhumeur, P. N., Hespanha, J. P., & Kriegman, D. J. (1997). Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection. IEEE TPAMI, 19(7), 711–720.
Candès, E. J., Li, X., Ma, Y., & Wright, J. (2011). Robust principal component analysis? Journal of the ACM, 58(3), 1–37.
d'Aspremont, A., El Ghaoui, L., Jordan, M. I., & Lanckriet, G. R. G. (2007). A direct formulation for sparse PCA using semidefinite programming. SIAM Review, 49(3), 434–448.
Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., & Harshman, R. (1990). Indexing by latent semantic analysis. JASIS, 41(6), 391–407.
Donoho, D. L., & Gavish, M. (2014). Minimax risk of matrix denoising by singular value thresholding. Annals of Statistics, 42(6), 2413–2440.
Dwork, C., Roth, A., et al. (2014). The algorithmic foundations of differential privacy. Foundations and Trends in TCS, 9(3–4), 211–407.
Fletcher, P. T., Lu, C., Pizer, S. M., & Joshi, S. (2004). Principal geodesic analysis for the study of nonlinear statistics of shape. IEEE TMI, 23(8), 995–1005.
Francis, J. G. F. (1961). The QR transformation: A unitary analogue to the LR transformation. Computer Journal, 4(3), 265–271.
Gavish, M., & Donoho, D. L. (2014). The optimal hard threshold for singular values is 4/√3. IEEE Transactions on Information Theory, 60(8), 5040–5053.
Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
Grammenos, A., Mendoza Smith, R., Crowcroft, J., & Mascolo, C. (2020). Federated principal component analysis. NeurIPS, 33.
Halko, N., Martinsson, P.-G., & Tropp, J. A. (2011). Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2), 217–288.
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009). Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15), 150502.
Hotelling, H. (1933). Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology, 24(6), 417–441.
Johnstone, I. M. (2001). On the distribution of the largest eigenvalue in principal components analysis. Annals of Statistics, 29(2), 295–327.
Lanczos, C. (1950). An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. Journal of Research of the National Bureau of Standards, 45(4), 255–282.
Ledoit, O., & Wolf, M. (2004). A well-conditioned estimator for large-dimensional covariance matrices. Journal of Multivariate Analysis, 88(2), 365–411.
Lloyd, S., Mohseni, M., & Rebentrost, P. (2014). Quantum principal component analysis. Nature Physics, 10(9), 631–633.
Lu, H., Plataniotis, K. N., & Venetsanopoulos, A. N. (2008). MPCA: Multilinear principal component analysis of tensor objects. IEEE TNN, 19(1), 18–39.
Marchenko, V. A., & Pastur, L. A. (1967). Distribution of eigenvalues for some sets of random matrices. Matematicheskii Sbornik, 72(4), 507–536.
Mahoney, M. W. (2011). Randomized algorithms for matrices and data. Foundations and Trends in ML, 3(2), 123–224.
Nadler, B. (2008). Finite sample approximation results for principal component analysis. Annals of Statistics, 36(6), 2791–2817.
Pearson, K. (1901). On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 2(11), 559–572.
Price, A. L., Patterson, N. J., Plenge, R. M., Weinblatt, M. E., Shadick, N. A., & Reich, D. (2006). Principal components analysis corrects for stratification in genome-wide association studies. Nature Genetics, 38(8), 904–909.
Ross, D. A., Lim, J., Lin, R.-S., & Yang, M.-H. (2008). Incremental learning for robust visual tracking. IJCV, 77(1–3), 125–141.
Saad, Y. (2011). Numerical Methods for Large Eigenvalue Problems (Revised ed.). SIAM.
Schmidt, R. O. (1986). Multiple emitter location and signal parameter estimation. IEEE Transactions on Antennas and Propagation, 34(3), 276–280.
Schölkopf, B., Smola, A., & Müller, K.-R. (1998). Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 10(5), 1299–1319.
Turk, M., & Pentland, A. (1991). Eigenfaces for recognition. Journal of Cognitive Neuroscience, 3(1), 71–86.
Woodruff, D. P. (2014). Sketching as a tool for numerical linear algebra. Foundations and Trends in TCS, 10(1–2), 1–157.
Zou, H., Hastie, T., & Tibshirani, R. (2006). Sparse principal component analysis. Journal of Computational and Graphical Statistics, 15(2), 265–286.