A Fast Adaptive Randomized PCA Algorithm

A Fast Adaptive Randomized PCA Algorithm

Xu Feng, Wenjian Yu

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 3695-3704. https://doi.org/10.24963/ijcai.2023/411

It is desirable to adaptively determine the number of dimensions (rank) for PCA according to a given tolerance of low-rank approximation error. In this work, we aim to develop a fast algorithm solving this adaptive PCA problem. We propose to replace the QR factorization in randQB_EI algorithm with matrix multiplication and inversion of small matrices, and propose a new error indicator to incrementally evaluate approximation error in Frobenius norm. Combining the shifted power iteration technique for better accuracy, we finally build up an algorithm named farPCA. Experimental results show that farPCA is much faster than the baseline methods (randQB_EI, randUBV and svds) in practical setting of multi-thread computing, while producing nearly optimal results of adpative PCA.
Keywords:
Machine Learning: ML: Feature extraction, selection and dimensionality reduction
Data Mining: DM: Big data and scalability
Data Mining: DM: Theoretical foundations of data mining