Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection
Year: 2021

Abstract:
Robust principal component analysis (RPCA) is a critical tool in modern machine learning, which detects outliers in the task of low-rank matrix reconstruction. In this paper, we propose a scalable and learnable non-convex approach for highdimensional RPCA problems, which we call Learned Robust PCA (LRPCA). LRPCA is highly efficient, and its free parameters can be effectively learned to optimize via deep unfolding. Moreover, we extend deep unfolding from finite iterations to infinite iterations via a novel feedforward-recurrent-mixed neural network model. We establish the recovery guarantee of LRPCA under mild assumptions for RPCA. Numerical experiments show that LRPCA outperforms the state-of-the-art RPCA algorithms, such as ScaledGD and AltProj, on both synthetic datasets and real-world applications.

heading: 1 Introduction
text: Over the last decade, robust principal component analysis (RPCA), one of the fundamental dimension reduction techniques, has received intensive investigations from theoretical and empirical perspectives [1–13]. RPCA also plays a key role in a wide range of machine learning tasks, such as video background subtraction [14], singing-voice separation [15], face modeling [16], image alignment [17] , feature identification [18], community detection [19], fault detection [20], and NMR spectrum recovery [21]. While the standard principal component analysis (PCA) is known for its high sensitivity to outliers, RPCA is designed to enhance the robustness of PCA when outliers are present. In this paper, we consider the following RPCA setting: given an observed corrupted data matrix
Y = X? + S? ∈ Rn1×n2 , (1)
where X? is a rank-r data matrix and S? is a sparse outlier matrix, reconstruct X? and S? simultaneously from Y .
One of the main challenges of designing an RPCA algorithm is to avoid high computational costs. Inspired by deep unfolded sparse coding [22], some recent works [23–25] have successfully extended deep unfolding techniques to RPCA and achieved noticeable accelerations in certain applications.
∗Authors are listed in alphabetic order. Correspondence shall be addressed to H.Q. Cai.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Specifically, by parameterizing a classic RPCA algorithm and unfolding it as a feedforward neural network (FNN), one can improve its performance by learning the parameters of the FNN through backpropagation. Since RPCA problems of a specific application often share similar key properties (e.g., rank, incoherence, and amount of outliers), the parameters learned from training examples that share the properties can lead to superior performance. Nevertheless, all existing learning-based approaches call an expensive step of singular value thresholding (SVT) [26] at every iteration during both training and inference. SVT involves a full or truncated singular value decomposition (SVD), which costs from O(n3) to O(n2r) flops2 with some large hidden constant in front3. Thus, these approaches are not scalable to high-dimensional RPCA problems. Another issue is that the existing approaches only learn the parameters for a finite number of iterations. If a user targets at a specific accuracy of recovery, then the prior knowledge of the unfolded algorithm is required for choosing the number of unfolded layers. Moreover, if the user desires better accuracy later, one may have to restart the learning process to obtain parameters of the extra iterations.
We must ask the questions: “Can one design a highly efficient and easy-to-learn method for highdimensional RPCA problems?” and “Do we have to restrict ourselves to finite-iteration unfolding (or a fixed-layer neural network)?” In this paper, we aim to answer these questions by proposing a scalable and learnable approach for high-dimensional RPCA problems, which has a flexible feedforwardrecurrent-mixed neural network model for potentially infinite-iteration unfolding. Consequently, our approach can satisfy arbitrary accuracy without relearning the parameters.
Related work. The earlier works [1–3] for RPCA are based on the convex model:
minimize X,S
‖X‖∗ + λ‖S‖1, subject to Y = X + S. (2)
It has been shown that (2) guarantees exact recovery, provided α . O(1/µr), a condition with an optimal order [4, 5]. Therein, α is the sparsity parameter of S? and µ is the incoherence parameter of L?, which will be formally defined later in Assumptions 2 and 1, respectively. Problem (2) can be transformed into a semidefinite program and has a variety of dedicated methods, their per-iteration complexities are at least O(n3) flops and some of them guarantee only sublinear convergence. Later, various non-convex methods with linear convergence were proposed for RPCA: [7] uses alternating minimization, and it can tolerate outliers up to a fraction of only α . O(1/µ2/3r2/3n). [6] develops an alternating projections method (AltProj) that alternatively projects Y − S onto the space of low-rank matrices and Y −X onto the space of sparse matrices. AltProj costs O(n2r2) flops and tolerates outliers up to α . O(1/µr). An accelerated version of AltProj (AccAltProj) was proposed in [10], which improves the computational complexity to O(n2r) with sacrifices on the tolerance to outliers, which are allowed up to α . O(1/max{µr2κ3, µ3/2r2κ, µ2r2}), where κ is the condition number of X?. Note that the key technique used for outlier detection in AltProj and AccAltProj is employing adaptive hard-thresholding parameters.
Another line of non-convex RPCA algorithms reformulate the low-rank component as X = LR>, where L ∈ Rn1×r and R ∈ Rn2×r, and then performs gradient descend on L and R separately. Since the low-rank constraint of X is automatically satisfied under this reformulation, the costly step of SVD is avoided (except for one SVD during initialization). Specifically speaking, [8] uses a complicated objective function, which includes a practically unimportant balance regularization ‖L>L−R>R‖F. While GD costs onlyO(n2r) flops per iteration, its convergence rate relies highly on κ. Recently, ScaledGD [12] introduces a scaling term in gradient descend steps to remove the dependence on κ in the convergence rate of GD. ScaledGD also drops the balance regularization and targets on a more elegant objective:
minimize L∈Rn1×r,R∈Rn2×r,S∈Rn1×n2
1 2 ‖LR> + S − Y ‖2F, subject to S is α-sparse, (3)
where α-sparsity means no more than a fraction α of non-zeros on every row and every column of S. To enforce the sparsity constraint of S, ScaledGD (and also GD) employs a sparsification operator:
[Tα̃(M)]i,j =
{ [M ]i,j , if |[M ]i,j | ≥ |[M ](α̃n2)i,: | and |[M ]i,j | ≥ |[M ] (α̃n1) :,j |
0, otherwise , (4)
2For ease of presentation, we take n := n1 = n2 when discuss computational complexities. 3The hidden constant is often hundreds and sometimes thousands.
where [ · ](k)i,: and [ · ] (k) :,j denote the k-th largest element in magnitude on the i-th row and in the j-th column, respectively. In other words, Tα̃ keeps only the largest α̃ fraction of the entries on every row and in every column. The per-iteration computational complexity of ScaledGD remains O(n2r) and it converges faster on ill-conditioned problems. The tolerance to outliers of GD and ScaledGD are α . O(1/max{µr3/2κ3/2, µrκ2}) and α . O(1/µr3/2κ), respectively. It is worth mentioning there exist some other RPCA settings that high-dimensional problems can be efficiently solved. For example, if the columns of X? are independently sampled over a zero-mean multivariate Gaussian distribution, an efficient approach is using Grassmann averages [27, 28].
Deep unfolding is a technique that dates back to 2010 from a fast approximate method for LASSO: LISTA [22] parameterizes the classic Iterative Shrinkage-Thresholding Algorithm (ISTA) as a fullyconnected feedforward neural network and demonstrates that the trained neural network generalizes well to unseen samples from the distribution used for training. It achieves the same accuracy within one or two order-of-magnitude fewer iterations than the original ISTA. Later works [29–36] extend this approach to different problems and network architectures and have good performance. Another recently developed technique “learning to learn” [37–39] parameterizes iterative algorithms as recurrent neural networks and shows great potential on machine learning tasks.
Applying deep unfolding on RPCA appeared recently. CORONA [23, 24] uses convolutional layers in deep unfolding and focuses on the application of ultrasound imaging. It uses SVT for low-rank approximation and mixed `1,2 thresholding for outlier detection since the outliers in ultrasound imaging problems are usually structured. refRPCA [25] focuses on video foreground-background separation and also uses SVT for low-rank approximation. However, refRPCA employs a sequence of constructed reference frames to reflex correlation between consecutive frames in the video, which leads to a complicated yet learnable proximal operator for outlier detection. Given the high computational cost of SVT, both CORONA and refRPCA are not scalable. In addition, Denise [40] studies a deep unfolding RPCA method for the special case of positive semidefinite low-rank matrices. Denise achieves a remarkable speedup from baselines; however, such RPCA applications are limited.
Contribution. In this work, we propose a novel learning-based method, which we call Learned Robust PCA (LRPCA), for solving high-dimensional RPCA problems. Our main contributions are:
1. The proposed algorithm, LRPCA, is scalable and learnable. It uses a simple formula and differentiable operators to avoid the costly SVD and partial sorting (see Algorithm 1). LRPCA costs O(n2r) flops with a small constant4 while all its parameters can be optimized by training.
2. An exact recovery guarantee is established for LRPCA under some mild conditions (see Theorem 1). In particular, LRPCA can tolerate outliers up to a fraction of α . O(1/µr3/2κ). Moreover, the theorem confirms that there exist a set of parameters for LRPCA to outperform the baseline algorithm ScaledGD.
3. We proposed a novel feedforward-recurrent-mixed neural network (FRMNN) model to solve RPCA. The new model first unfolds finite iterations of LRPCA and individually learns the parameters at the significant iteration; then, it learns the rules of parameter updating for subsequent iterations. Therefore, FRMNN learns the parameters for infinite iterations of LRPCA while we ensure no performance reduction from classic deep unfolding.
4. The numerical experiments confirm the advantages of LRPCA on both synthetic and realworld datasets. In particular, we successfully apply LRPCA to large video background subtraction tasks where the problem dimensions exceed the capacities of the existing learning-based RPCA approaches.
Notation. For any matrix M , [M ]i,j denotes the (i, j)-th entry, σi(M) denotes the i-th singular value, ‖M‖1 := ∑ i,j |[M ]i,j | denotes the entrywise `1 norm, ‖M‖F := ( ∑ i,j [M ] 2 i,j)
1/2 denotes the Frobenius norm, ‖M‖∗ := ∑ i σi(M) denotes the nuclear norm, ‖M‖∞ := maxi,j |[M ]i,j |
denotes the largest magnitude, ‖M‖2,∞ := maxi( ∑ j [M ] 2 i,j)
1/2 denotes the largest row-wise `2 norm, and M> denotes the transpose. We use κ := σ1(X?)σr(X?) to denote the condition number of X?.
4More precisely, LRPCA costs as low as 3n2r + 3n2 +O(nr2) flops per iteration, which is much smaller than the hidden constant of truncated SVD.

heading: 2 Proposed method
text: In this section, we first describe the proposed learnable algorithm and then present the recovery guarantee.
We consider the non-convex minimization problem:
minimize L∈Rn1×r,R∈Rn2×r,S∈Rn1×n2
1 2 ‖LR> + S − Y ‖2F, subject to supp(S) ⊆ supp(S?). (5)
One may find (5) similar to the objective (3) of ScaledGD but with a different sparsity constraint for S. The user may not know the true support of S?. Also, the two constraints in (3) and (5) may seem somewhat equivalent when S? is assumed α-sparse. However, we emphasize that our algorithm design does not rely on an accurate estimation of α, and our method eliminates false-positives at every outlier-detection step.
Our algorithm proceeds in two phases: initialization and iterative updates. The first phase is done by a modified spectral initialization. In the second phase, we iteratively update outlier estimates via soft-thresholding and the factorized low-rank component estimates via scaled gradient descends. All the parameters of our algorithm are learnable during deep unfolding. The proposed algorithm, LRPCA, is summarized in Algorithm 1. We now discuss the key details of LRPCA and begin with the second phase.
Algorithm 1 Learned Robust PCA (LRPCA) 1: Input: Y = X? + S?: sparsely corrupted matrix; r: the rank of underlying low-rank matrix; {ζk}: a set of learned thresholding values; {ηk}: a set of learned step sizes.
2: // Initialization: 3: S0 = Sζ0(Y ) 4: [U0,Σ0,V0] = SVDr(Y − S0) 5: L0 = U0Σ 1/2 0 , R0 = V0Σ 1/2 0 6: // Iterative updates: 7: while Not(Stopping Condition) do 8: Sk+1 = Sζk+1(Y −LkR>k ) 9: Lk+1 = Lk − ηk+1(LkR>k + Sk+1 − Y )Rk(R>kRk)−1
10: Rk+1 = Rk − ηk+1(LkR>k + Sk+1 − Y )>Lk(L>k Lk)−1 11: end while 12: Output: XK = LKR>K : the recovered low-rank matrix.
Updating S. In ScaledGD [12], the sparse outlier matrix is updated by Sk+1 = Tα̃(Y −LkR>k ), where the sparsification operator Tα̃ is defined in (4). Note that Tα̃ requires an accurate estimate of α and its execution involves partial sorting on each row and column. Moreover, deep unfolding and parameter learning cannot be applied to Tα̃ since it is not differentiable. Hence, we hope to find an efficient and effectively learnable operator to replace Tα̃. The well-known soft-thresholding, a.k.a. shrinkage operator,
[Sζ(M)]i,j = sign([M ]i,j) ·max{0, |[M ]i,j | − ζ} (6) is our choice. Soft-thresholding has been applied as a proximal operator of `1 norm (to a matrix entrywise) in some RPCA algorithms [2]. However, a fixed threshold, which is determined by the regularization parameter, leads to only sublinear convergence of the algorithm. Inspired by AltProj, LISTA, and their followup works [6, 10, 22, 29–34, 36], we seek for a set of thresholding parameters {ζk} that let our algorithm outperform the baseline ScaledGD. In fact, we find that the simple soft-thresholding:
Sk+1 = Sζk+1(Y −LkR>k ) (7) can also give a linear convergence guarantee if we carefully choose the thresholds, and the selected {ζk} also guarantees supp(Sk) ⊆ supp(S?) at every iteration, i.e., no false-positive outliers. Moreover, the proposed algorithm with selected thresholds can converge even faster than ScaledGD under the very same assumptions (see Theorem 1 below for a formal statement.) Nevertheless, the theoretical selection of {ζk} relies on the knowledge of X?, which is usually unknown to the user. Fortunately, these thresholds can be reliably learned using the deep unfolding techniques.
Updating X . To avoid the low-rank constraint on X , we write a rank-r matrix as product of a tall and a fat matrices, that is, X = LR> ∈ Rn1×n2 with L ∈ Rn1×r and R ∈ Rn2×r. Denote the loss function fk := f(Lk,Rk) := 12‖LkR > k + S − Y ‖2F. The gradients can be easily computed:
∇Lfk = (LkR>k + S − Y )Rk and ∇Rfk = (LkR>k + S − Y )>Lk. (8) We could apply a step of gradient descent on L and R. However, [12] finds the vanilla gradient descent approach suffers from ill-conditioning and thus introduces the scaled terms (R>kRk)
−1 and (L>k Lk)
−1 to overcome this weakness. In particular, we follow ScaledGD and update the low-rank component:
Lk+1 = Lk − ηk+1∇Lfk · (R>kRk)−1, Rk+1 = Rk − ηk+1∇Rfk · (L>k Lk)−1,
(9)
where ηk+1 is the step size at the (k + 1)-th iteration.
Initialization. We use a modified spectral initialization with soft-thresholding in the proposed algorithm. That is, we first initialize the sparse matrix by S0 = Sζ0(Y ), which should remove the obvious outliers. Next, for the low-rank component, we take L0 = U0Σ 1/2 0 and R0 = V0Σ 1/2 0 , where U0Σ0V >0 is the best rank-r approximation (denoted by SVDr) of Y −S0. Clearly, the initial thresholding step is crucial for the quality of initialization and the thresholding parameter ζ0 can be optimized through learning.
For the huge-scale problems where even a single truncated SVD is computationally prohibitive, one may replace the SVD step in initialization by some batch-based low-rank approximations, e.g., CUR decomposition. While its stability lacks theoretical support when outliers appear, the empirical evidence shows that a single CUR decomposition can provide sufficiently good initialization [11].
Computational complexity. Along with guaranteed linear convergence, LRPCA costs only 3n2r+ 3n2 +O(nr2) flops per iteration provided r n. In contrast, truncated SVD costsO(n2r) flops with a much larger hidden constant. The breakdown of LRPCA’s complexity is provided in Appendix B.
Limitations. LRPCA assumes the knowledge of rank(X?), which is commonly assumed in many non-convex matrix recovery algorithms. In fact, the rank of X? is fixed or can be easily obtained from prior knowledge in many applications, e.g., Euclidean distance matrices are rank-(d+ 2) for the system of d-dimensional points [41]. However, the true rank may be hard to get in other applications, and LRPCA is not designed to learn the true rank from training data. Thus, LRPCA may have reduced performance in such applications when the target rank is seriously misestimated.

heading: 2.1 Theoretical results
text: We present the recovery guarantee of LRPCA in this subsection. Moreover, when the parameters are selected correctly, we show that LRPCA provably outperforms the state-of-the-arts.
We start with two common assumptions for RPCA: Assumption 1 (µ-incoherence of low-rank component). X? ∈ Rn1×n2 is a rank-r matrix with µ-incoherence, i.e.,
‖U?‖2,∞ ≤ √ µr
n1 and ‖V?‖2,∞ ≤
√ µr
n2 (10)
for some constant 1 ≤ µ ≤ n, where U?Σ?V >? is the compact SVD of X?. Assumption 2 (α-sparsity of outlier component). S? ∈ Rn1×n2 is an α-sparse matrix, i.e., there are at most α fraction of non-zero elements in each row and column of S?. In particular, we require α . O( 1
µr3/2κ ) for the guaranteed recovery, which matches the requirement for ScaledGD. We future
assume the problem is well-posed, i.e., µ, r, κ n. Remark 1. Note that some applications may have a more specific structure for outliers, which may lead to a more suitable operator for S updating in the particular applications. This work aims to solve the most common RPCA model with a sparsity assumption. Nevertheless, our learning framework can be adapted to another operator as long as it is differentiable.
By the rank-sparsity uncertainty principle, a matrix cannot be incoherent and sparse simultaneously [42]. The above two assumptions ensure the uniqueness of the solution in RPCA. Now, we are ready to present our main theorem: Theorem 1 (Guaranteed recovery). Suppose that X? is a rank-r matrix with µ-incoherence and S? is an α-sparse matrix with α ≤ 1104µr3/2κ . If we set the thresholding values ζ0 = ‖X?‖∞ and ζk = ‖Lk−1R>k−1 −X?‖∞ for k ≥ 1 for LRPCA, the iterates of LRPCA satisfy ‖LkR>k −X?‖F ≤ 0.03(1− 0.6η)kσr(X?) and supp(Sk) ⊆ supp(S?), (11) with the step sizes ηk = η ∈ [ 14 , 8 9 ].
Proof. The proof of Theorem 1 is deferred to Appendix A.
Essentially, Theorem 1 states that there exists a set of selected thresholding values {ζk} that allows one to replace the sparsification operator Tα̃ in ScaledGD with the simpler soft-thresholding operator Sζ and maintains the same linear convergence rate 1 − 0.6η under the same assumptions. Note that the theoretical choice of parameters relies on the knowledge of X?—an unknown factor. Thus, Theorem 1 can be read as a proof for the existence of the appropriate parameters.
Moreover, Theorem 1 shows two advantages of LRPCA:
1. Under the very same assumptions and constants, we allow the step sizes ηk to be as large as 89 ; in contrast, ScaledGD has the step sizes no larger than 2 3 [12, Theorem 2]. That is,
LRPCA can provide faster convergence under the same sparsity condition, by allowing larger step sizes.
2. With the selected thresholding values, Sζ in LRPCA is effectively a projection onto supp(S?), which matches our sparsity constrain in objective function (5). That is, Sζ takes out the larger outliers, leaves the smaller outliers, and preserves all good entries — no false-positive outlier in Sk. In contrast, Tα̃ necessarily yields some false-positive outliers in the earlier stages of ScaledGD, which drag the algorithm when outliers are relatively small.
Technical innovation. The main challenge to our analysis is to show both the distance error metric (i.e., dist(Lk,Rk;L?,R?), later defined in Appendix A) and `∞ error metric (i.e., ‖LkR>k −X?‖∞) are linearly decreasing. While the former takes some minor modifications from the proof of ScaledGD, the latter is rather challenging and utilizes several new technical lemmata. Note that ScaledGD shows ‖LkR>k −X?‖∞ is always bounded but not necessary decreasing, which is insufficient for LRPCA.

heading: 3 Parameter learning
text: Theorem 1 shows the existence of “good" parameters {ζk}, {ηk} and, in this section, we describe how to obtain such parameters via machine learning techniques.
Feed-forward neural network. Classic deep unfolding methods unroll an iterative algorithm and truncates it into a fixed number, says K, iterations. Applying such idea to our model, we regard each iteration of Algorithm 1 as a layer of a neural network and regard the variables Lk,Rk,Sk as the units of the k-th hidden layer. The top part of Figure 1 demonstrates the structure of such feed-forward neural network (FNN). The k-th layer is denoted as Lk. Based on (7) and (9), it takes Y as an input and has two parameters ζk, ηk when k ≥ 1. The initial layer L0 is special, it takes Y and r as inputs, and it has only one parameter ζ0. For simplicity, we use Θ = {{ζk}Kk=0, {ηk}Kk=1} to represent all parameters in this neural network.
Training. Given a training data set Dtrain consisting of (Y ,X?) pairs (observation, ground truth), one can train the neural network and obtain parameters Θ by minimizing the following loss function:
minimize Θ
E(Y ,X?)∼Dtrain‖LK(Y ,Θ) ( RK(Y ,Θ) )> −X?‖2F. (12) Directly minimizing (12) is called end-to-end training, and it can be easily implemented on deep learning platforms nowadays. In this paper, we adopt a more advanced training technique named as layer-wise training or curriculum learning, which has been proven as a powerful tool on training deep unfolding models [43, 44]. The process of layer-wise training is divided into K + 1 stages:
• Training the 0-th layer with minimizeΘ E‖L0R>0 −X?‖2F. • Training the 1-st layer with minimizeΘ E‖L1R>1 −X?‖2F. • · · · • Training the final layer with (12): minimizeΘ E‖LKR>K −X?‖2F.
Feedforward-recurrent-mixed neural network. One disadvantage of the aforementioned FNN model is its fixed number of layers. If one wants to go further steps and obtain higher accuracy after training a neural network, one may have to retrain the neural network once more. Recurrent neural network (RNN) has tied parameters over different layers and, consequently, is extendable to infinite layers. However, we find that the starting iterations play significant roles in the convergence (validated in Section 4 later) and their parameters should be trained individually. Thus, we propose a hybrid model that is demonstrated in the bottom part of Figure 1, named as Feedforward-recurrent-mixed neural network (FRMNN). We use a recurrent neural network appended after a K-layer feedforward neural network. When k ≥ K, in the (k − K)-th loop of the RNN layer, we follow the same calculation procedures with Algorithm 1 and determine the parameters ζk and ηk by
ηk = βηk−1 and ζk = φζk−1. (13)
Thus, all the RNN layers share the common parameters β and φ.
The training of FRMNN follows in two phases:
• Training the K-layer FNN with layer-wise training. • Fixing the FNN and searching RNN parameters β and φ to minimize the convergence metric
at the (K −K)-th layer of RNN for some K > K:
minimize β,φ
E(Y ,X?)∼Dtrain‖LK(β, φ)(RK(β, φ)) > −X?‖2F. (14)
Our new model provides the flexibility of training a neural network with finite K layers and testing it with infinite layers. Consequently, the stop condition of LRPCA has to be (Run K iterations) if the parameters are trained via FNN model; and the stop condition can be (Error < Tolerance) if our FRMNN model is used.
In this paper, we use stochastic gradient descent (SGD) in the layer-wise training stage and use grid search to obtain β and φ since there are only two parameters. Moreover, we find that picking K + 3 ≤ K ≤ K + 5 is empirically good.

heading: 4 Numerical experiments
text: In this section, we compare the empirical performance of LRPCA with the state-of-the-arts: ScaledGD [12] and AltProj [6]. We hand tune the parameters for ScaledGD and AltProj to achieve their best
performance in the experiments. Moreover, all speed tests are executed on a Windows 10 laptop with Intel i7-8750H CPU, 32GB RAM and Nvidia GTX-1060 GPU. The parameters learning processes are executed on an Ubuntu workstation with Intel i9-9940X CPU, 128GB RAM and two Nvidia RTX-3080 GPUs. All our synthetic test results are averaged over 50 random generated instances, and details of random instance generation can be found in Appendix C. The code for LRPCA is available online at https://github.com/caesarcai/LRPCA.
Unfolding models. We compare the performance of LRPCA with the parameters learned from different unfolding models: classic FNN, RNN and proposed FRMNN. In particular, FNN model unrolls 10 iterations of LRPCA and RNN model directly starts the training on the second phase of FRMNN, i.e., K = 0. For FRMNN model, we take K = 10 and K = 15 for the training. The test results is summarized in Figure 2. One can see FRMNN model extends FNN model to infinite layers with performance reduction while
the pure RNN model drops the convergence performance. Note that the convergence curves of both FRMNN and RNN go down till they reach O(10−8) which is the machine precision since we use single precision in this experiment.
Computational efficiency. In this section, we present the speed advantage of LRPCA. First, we compare the convergence behavior of LRPCA to our baseline ScaledGD in Figure 3. We find LRPCA converges in much less iterations, especially when the outlier sparsity α is larger. Next, we compare per-iteration runtime of LRPCA to our baseline ScaledGD in Figure 4. One can see that ScaledGD runs slower when α becomes larger. In contrast, the per-iteration runtime of LRPCA is insensitive to α and is significantly faster than ScaledGD. Finally, we compare the total runtime among LRPCA, ScaledGD and AltProj in Figure 5. Therein, we find LRPCA is substantially faster than the state-ofthe-arts if the model has been trained. The training time for models with different sizes and settings are reported in the supplement.
Recovery performance. We generate 10 problems for each of the outlier density levels (i.e., α) and compare the recoverabilities of LRPCA and ScaledGD. The test result is presented in the Table 1, where we can conclude that LRPCA is more robust when α is larger.
Video background subtraction. In this section, we apply LRPCA to the task of video background subtraction. We use VIRAT video dataset5 as our benchmark, which includes numerous colorful videos with static backgrounds. The videos have been grouped into training and testing sets. We used 65 videos for parameter learning and 4 videos for verification6. We first convert all videos to grayscale. Next, each frame of the videos is vectorized and become a matrix column, and all frames of a video form a data matrix. The static backgrounds are the low-rank component of the data matrices and moving objects can be viewed as outliers, thus we can separate the backgrounds and foregrounds via RPCA. The video details and the experimental results are summarized in Table 2 and selected visual results for LRPCA are presented in Figure 6. One can see LRPCA runs much faster than both ScaledGD and AltProj in all verification tests. Furthermore, the background subtraction results of LRPCA are also visually desirable. More details about the experimental setup can be found in Appendix C, alone with additional visual results for ScaledGD and AltProj.
Ultrasound imaging. We compare LRPCA with CORONA [23], a state-of-the-art learning-based RPCA method, on ultrasound imaging. The testing dataset consists of 2400 training examples and 800 validation examples, which can be downloaded online at https://www.wisdom.weizmann. ac.il/~yonina. Each example is of size 1024× 40. The target rank of the low-rank matrix is set to be r = 1. Recovery accuracy is measured by the loss function: loss = MSE(Xoutput, X?), where MSE stands for the mean square error. The test results are summarized in Table 3.
Note that LRPCA is designed for generic RPCA and CORONA is specifically designed for ultrasound imaging. Thus, it is not a surprise that our recovery accuracy is slightly worse than CORONA.
5Available at: https://viratdata.org. 6The names of the tested videos are corresponding to these original video numbers in VIRAT dataset: ParkingLot1: S_000204_06_001527_001560, ParkingLot2: S_010100_05_000917_001017, ParkingLot3: S_050204_00_000000_000066, StreeView: S_050100_13_002202_002244.
However, the average runtime of LRPCA is substantially faster than CORONA. We believe that our speed advantage will be even more significant on larger-scale examples, which is indeed our main contribution: scalability.
More numerical experiments. There are some other interesting empirical problems worth to explore and we put the extra experimental results in Appendix C due to the space limitation. They are summarized here: 1. Our model has good generalization ability. We can train our model on small-size and low-rank training instances (say, n = 1000 and r = 5) and use the model DIRECTLY on problems with larger size (say, n = 3000 and r = 5) or with higher rank (say, n = 1000 and r = 15) with good performance. 2. The learned parameters are explainable. With the learned parameters, LRPCA goes very aggressively with large step sizes in the first several steps and tends to be conservative after that.

heading: 5 Conclusion and future work
text: We have presented a highly efficient learning-based approach for high-dimensional RPCA problems. In addition, we have presented a novel feedforward-recurrent-mixed neural network model which can learn the parameters for potentially infinite iterations without performance reduction. Theoretical recovery guarantee has been established for the proposed algorithm. The numerical experiments show that the proposed approach is superior to the state-of-the-arts.
One of our future directions is to study learning-based stochastic approach. While this paper focuses on deterministic RPCA approaches, the stochastic RPCA approaches, e.g., partialGD [8], PG-RMC [9], and IRCUR [11], have shown promising speed advantage, especially for large-scale problems. Another future direction is to explore robust tensor decomposition incorporate with deep learning, as some preliminary studies have shown the advantages of tensor structure in certain machine learning tasks [45, 46].
Broader impact
RPCA has been broadly applied as one of fundamental techniques in data mining and machine learning communities. Hence, through its applications, the proposed learning-based approach for RPCA has potential broader impacts that data mining and machine learning have, as well as their limitations.

Review summaries:
This paper presents a a new approach to solve the Robust PCA problem. They use matrix factorisation to formulate RPCA as a more scalable problem, then learn (or optimise) parameters during the algorithm's each iteration. They also add a recurrent layer at the end to allow for "unlimited" iterations. The methods is compared against classic RPCA solvers, but not against learned methods.

The authors study the problem of robust PCA inspired  by a LISTA type approach. In particular, the authors consider  a hybrid model of feedforward, and recurrent NN architectures and "learn the parameters of (scaled) GD" that is used to solve RPCA. I am not extremely familiar with the literature, but essentially the hybrid model allows for a non-apriori (in terms of the architecture) number of iterations that the algorithm can run for. This seems particularly interesting to me. The authors show that under certain conditions of the parameters, the algorithm enjoys linear convergence. The authors also show synthetic data experiments and a use-case of background subtraction to validate their results. 

The paper studies the problem of robust PCA. The authors first proposed an improved algorithm based on the previous work ScaledGD. Then they proposed to use "learning to optimize" to select the hyper parameters dynamically and adaptively. The numerical results showed that the proposed method is more effective than two baselines.

The paper propose a new technique for robust PCA that can be realised as a trainable neural network. The technique provides similar theoretical guarantees to existing methods, yet scale better to larger problems. The paper is well-written and mostly easy to follow.