Efficient random methods for low-rank matrix estimation

Low-rank matrix estimation is an important tool in modern data analysis and machine learning. The basic idea of low-rank matrix estimation is to estimate the original matrix with a low-rank matrix, thereby achieving dimensionality reduction, noise reduction, or simplification of computations. In this paper, we propose two new matrix decomposition methods based on CUR decomposition, Row Random Decomposition and Column-Row Random Decomposition. These two methods significantly improve computational efficiency, reduce randomness and introduce a degree of determinism compared to the classic CUR decomposition. Then, we apply Row Random Decomposition and Column-Row Random Decomposition to update the low-rank matrix estimation in RPCA problem, resulting in two algorithms: Row Random RPCA and Column-Row Random RPCA. These two algorithms can quickly yield an accurate low-rank matrix estimation while avoiding the need to perform SVD decomposition on the original data matrix. By leveraging Row Random Decomposition and Column-Row Random Decomposition, they effectively reduce computational complexity and improve efficiency in solving the RPCA problem. Additionally, numerical experiments conducted on synthetic datasets demonstrate the computational advantages of our algorithms. These experiments reveal that our methods not only provide linear convergence but also maintain high accuracy and robustness across various scenarios. And experiments in video background subtraction highlight the Row Random RPCA and the Column-Row Random RPCA excellent performance in both speed and visual quality.