A Random Algorithm for Low-Rank Decomposition of Large-Scale Matrices With Missing Entries.

Area of Science:

• Numerical Analysis
• Linear Algebra
• Machine Learning

Background:

• Low-rank decomposition is crucial for dimensionality reduction and data analysis.
• Existing algorithms for low-rank decomposition can be computationally expensive and memory-intensive.
• Efficient and accurate methods are needed for large-scale matrix computations.

Purpose of the Study:

• To propose a novel Random Submatrix Method (RSM) for efficient low-rank matrix decomposition.
• To significantly reduce computational complexity and memory requirements compared to state-of-the-art methods.
• To maintain high precision in the decomposition results.

Main Methods:

• Randomly selecting submatrices from the original matrix Y (m x n).
• Utilizing statistical properties and a proven theorem to handle random noise.
• Calculating null vectors or singular vectors from submatrices to estimate the full decomposition.

Main Results:

• RSM achieves a computational complexity of O(mr(2)ρ(r)) or O(n(3)ρ(3r)) flops.
• Memory requirement is reduced to max(n(2),mr+nr) real values.
• Experimental results show RSM is 4.30 to 197.95 times faster than existing algorithms with high precision.

Conclusions:

• RSM offers a computationally efficient and memory-saving alternative for low-rank matrix decomposition.
• The method demonstrates superior speed and comparable accuracy on synthetic and real-world datasets.
• RSM is a promising technique for large-scale matrix factorization tasks.