Randomized algorithms for distributed computation of principal component analysis and singular value decomposition

Area of Science:

• Numerical analysis
• Distributed computing
• Linear algebra

Background:

• Distributed computation platforms like Spark are essential for large-scale data analysis.
• Standard deterministic algorithms for matrix decomposition can suffer from numerical inaccuracies.
• Principal Component Analysis (PCA) and Singular Value Decomposition (SVD) are fundamental matrix factorization techniques.

Purpose of the Study:

• To develop and evaluate randomized algorithms for distributed PCA and SVD.
• To address limitations in accuracy and numerical stability of existing deterministic methods.
• To provide superior solutions for large-scale matrix decomposition tasks.

Main Methods:

• Implementation of honed randomized algorithms for distributed PCA and SVD.
• Comparison against stock, deterministic implementations within the Spark platform.
• Assessment of numerical orthonormality of computed singular vectors.

Main Results:

• Randomized algorithms demonstrated superior performance over deterministic Spark implementations.
• Achieved numerically orthonormal left singular vectors to near machine precision.
• Provided accurate solutions for distributed PCA and SVD of highly rectangular matrices.

Conclusions:

• The developed randomized algorithms offer a more numerically stable and accurate approach for distributed matrix decomposition.
• These improved methods are crucial for reliable large-scale data analysis in scientific computing.
• Randomized algorithms represent a significant advancement over standard deterministic techniques for SVD and PCA.