Research on Dimensionality Reduction Algorithms for High-Dimensional Data Based on Matrix Analysis

Qianwen Wu

doi:10.54097/xd4z6b55

Authors

Qianwen Wu

DOI:

https://doi.org/10.54097/xd4z6b55

Keywords:

Dimensionality Reduction; Matrix Analysis; Principal Component Analysis; Singular Value Decomposition; Manifold Learning; Randomized Algorithms; High-Dimensional Data

Abstract

More and more high dimensional data can be found in many fields including genomics, computer vision, NLP, RS etc. Therefore Dimensionality Reduction is important in most of the Machine Learning and Data analysis pipelines. This article carries out a comprehensive research on different types of dimensionality reduction algorithms which are based both in linear and nonlinear paradigms. This study includes both linear and nonlinear paradigms: In this section we have discussed about the mathematical foundations of PCA, LDA, NMF, SparsePCA with respect to consider it as singular value decomposition and eigen-decompostion for the structered matrix. Regarding non-linear methods, we consider the graph - Laplacian and manifold - geometric matrix framework that is the foundation of Isomap, LLE, Laplacian eigenmaps, t - SNE, and UMAP. And we also compare computational complexity and scalability approximation(random svds, incremental). We benchmark all algorithms on commonly used datasets(MNIST, 20newsgroups, swissroll, cifar) regarding their reconstruction quality, speed and how well they enable us to classify things. For randomized svd the randomization gives us very good approximations on a small amount of the full decomposition computing time and UMAP seems to have the best mix of scale and shape when using nonlinear approaches. Proposed some practical advice for algorithm choices according to information size, internal dimension and task necessities

References

[1] Hotelling, H. (1933). Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology, 24(6), 417–441. https://doi.org/10.1037/h0071325

[2] Jolliffe, I. T., & Cadima, J. (2016). Principal component analysis: a review and recent developments. Philosophical Transactions of the Royal Society A, 374(2065), 20150202. https://doi.org/10.1098/rsta.2015.0202

[3] Tenenbaum, J. B., De Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500), 2319–2323. https://doi.org/10.1126/science.290.5500.2319

[4] Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500), 2323–2326. https://doi.org/10.1126/science.290.5500.2323

[5] Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6), 1373–1396. https://doi.org/10.1162/089976603321780317

[6] Van der Maaten, L., & Hinton, G. (2008). Visualizing data using t-SNE. Journal of Machine Learning Research, 9(11), 2579–2605.

[7] McInnes, L., Healy, J., & Melville, J. (2018). UMAP: Uniform manifold approximation and projection for dimension reduction. Journal of Open Source Software, 3(29), 861. https://doi.org/10.21105/joss.00861

[8] 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. https://doi.org/10.1137/090771806

[9] Böhm, J. N., Berens, P., & Kobak, D. (2022). Attraction-repulsion spectrum in neighbor embeddings for dimensionality reduction. Journal of Machine Learning Research, 23(95), 1–32.

[10] Damrich, S., Berens, P., & Kobak, D. (2025). From t-SNE to UMAP with contrastive learning. International Conference on Learning Representations.