Aiming at Robust Principal Component Analysis (RPCA) problem, a Newton-Soft Threshold Iteration (NSTI) algorithm was proposed for reducing time complexity of RPCA algorithm. Firstly, the NSTI algorithm model was constructed by using the sum of the Frobenius norm of the low-rank matrix and the l ₁-norm of the sparse matrix. Secondly, two different optimization methods were used to calculate different parts of the model at the same time. Newton method was used to quickly calculate the low-rank matrix. Soft threshold iteration algorithm was used to quickly calculate the sparse matrix. The decomposition of low-rank matrix and sparse matrix of original data was calculated by alternately using the two optimization methods. Finally, the low-rank features of the original data were obtained. Under the condition that the data scale is 5 000×5 000 and rank of the low-rank matrix is 20, NSTI algorithm can improve the time efficiency by 24.6% and 45.5% compared with Gradient Descent (GD) algorithm and Low-Rank Matrix Fitting (LMaFit) algorithm. For foreground and background separation of 180-frame video, NSTI takes 3.63 s and has the time efficiency 78.7% and 82.1% higher than GD algorithm and LMaFit algorithm. In the experiment of image denoising, NSTI algorithm takes 0.244 s, and the residual error of the image processed by NSTI and the original image is 0.381 3, showing that the time efficiency and the accuracy of the proposed algorithm are 64.3% more efficient and 45.3% more accurate than those of GD algorithm and LMaFit algorithm. Experimental results prove that NSTI algorithm can effectively solve the RPCA problem and improve the time efficiency of the RPCA algorithm.