• PDF
• Cite
• Share
Article Contents  Article Contents

# Fast algorithms for robust principal component analysis with an upper bound on the rank

• * Corresponding author

N. Sha and M. Yan are supported by NSF grant DMS-1621798 and DMS-2012439. L. Shi is supported by NNSFC grant 11631015 and Shanghai Science and Technology Research Program 19JC1420101 and and 20JC1412700

• The robust principal component analysis (RPCA) decomposes a data matrix into a low-rank part and a sparse part. There are mainly two types of algorithms for RPCA. The first type of algorithm applies regularization terms on the singular values of a matrix to obtain a low-rank matrix. However, calculating singular values can be very expensive for large matrices. The second type of algorithm replaces the low-rank matrix as the multiplication of two small matrices. They are faster than the first type because no singular value decomposition (SVD) is required. However, the rank of the low-rank matrix is required, and an accurate rank estimation is needed to obtain a reasonable solution. In this paper, we propose algorithms that combine both types. Our proposed algorithms require an upper bound of the rank and SVD on small matrices. First, they are faster than the first type because the cost of SVD on small matrices is negligible. Second, they are more robust than the second type because an upper bound of the rank instead of the exact rank is required. Furthermore, we apply the Gauss-Newton method to increase the speed of our algorithms. Numerical experiments show the better performance of our proposed algorithms.

Mathematics Subject Classification: Primary:65K10, 90C26;Secondary:65D18.

 Citation: • • Figure 2.  The relative error to the true low-rank matrix vs the rank $p$ for Shen et al.'s and Alg. 2. Alg. 2 is robust to $p$, as long as $p$ is not smaller than the true rank 25

Figure 1.  The contour map of the relative error to ${\bf{L}}^\star$ for different parameters. In this experiment, we set $r = 25$ and $s = 20$. The upper bound of the rank is set to be $p = 30$

Figure 3.  The numerical experiment on the 'cameraman' image. (A-C) show that the proposed model performs better than Shen et al.'s both visually and in terms of RE and PSNR. (D) compares the objective values vs time for general SVD, Alg. 1, and Alg. 2. Here $f^\star$ is the value obtained by Alg. 2 with more iterations. It shows the fast speed with the Gauss-Newton approach and acceleration. With the Gauss-Newton approach, the computation time for Alg. 1 is reduced to about 1/7 of the one with standard SVD (from 65.11s to 8.43s). The accelerated Alg. 2 requires 5.2s, though the number of iterations is reduced from 3194 to 360

Figure 4.  The numerical experiment on the 'Barbara' image. (A-C) show that the proposed model performs better than Shen et al.'s both visually and in terms of RE and PSNR. (D) compares the objective values vs time for general SVD, Alg. 1, and Alg. 2. Here $f^\star$ is the value obtained by Alg. 2 with more iterations. It shows the fast speed with the Gauss-Newton approach and acceleration. With the Gauss-Newton approach, the computation time for Alg. 1 is reduced to less than 1/3 of the one with standard SVD (from 148.6s to 43.7s). The accelerated Alg. 2 requires 23.3s, though the number of iterations is reduced from 3210 to 300

 Algorithm 1: Proposed Algorithm Input: ${\bf{D}}$, $\mu$, $\lambda$, $p$, $\mathcal{A}$, stepsize $t$, stopping criteria $\epsilon$, maximum number of iterations $Max\_Iter$, initialization ${\bf{L}}^0 = \bf{0}$Output: ${\bf{L}}$, ${\bf{S}}$ Algorithm 2: Accelerated algorithm with nonmonotone APG Input:${\bf{D}}$, $\mu$, $\lambda$, $p$, $\mathcal{A}$, stepsize $t$, $\eta \in [0,1)$, $\delta > 0$, stopping criteria $\epsilon$, maximum number of iterations $Max\_Iter$, initialization: ${\bf{L}}^0 = {\bf{L}}^1 = {\bf{Z}}^1 = \textbf{0}$, $t^0 = 0$, $t^1 = q^1=1$, $c^1 = F( {\bf{L}}^1)$Output:${\bf{L}}$, ${\bf{S}}$ Table 1.  Comparison of three RPCA algorithms. We compare the relative error of their solutions to the true low-rank matrix and the number of iterations. Both Alg. 1 and Alg. 2 have better performance than  in terms of the relative error and the number of iterations. Alg. 2 has the fewest iterations but the relative error could be large. It is because the true low-rank matrix is not the optimal solution to the optimization problem, and the trajectory of the iterations moves close to ${\bf{L}}^\star$ before it approaches the optimal solution

 $r$ s Shen et al.'s  Alg. 1 Alg.2 $RE( {\bf{L}}, {\bf{L}}^\star)$ $\#$ iter $RE( {\bf{L}}, {\bf{L}}^\star)$ $\#$ iter $RE( {\bf{L}}, {\bf{L}}^\star)$ $\#$ iter 25 20 0.0745 1318 0.0075 296 0.0075 68 50 20 0.0496 1434 0.0101 473 0.0088 77 25 40 0.0990 2443 0.0635 796 0.0915 187

Table 2.  Performance of Alg. 2 on low-rank matrix recovery with missing entries. We change the level of sparsity in the sparse noise, standard deviation of the Gaussian noise, and the ratio of missing entries

 {s} {$\sigma$} ratio of missing entries $RE( {\bf{L}}, {\bf{L}}^\star)$ by Alg. 2 20 0.05 10% 0.0079 20 0.05 20% 0.0088 20 0.05 50% 0.0201 5 0.01 50% 0.0015
• Figures(4)

Tables(4)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint