Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection
Authors: HanQin Cai
Jialin Liu
Wotao Yin
Venue: NeurIPS 2021 Poster (2021)
Keywords: Robust PCA
Outlier Detection
Deep Unfolding
Learning to Optimize
Video Background Subtraction
Ultrasound Imaging

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 high-dimensional 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. 

Learned Robust PCA: A Scalable Deep Unfolding Approach for
Outlier Detection
HanQin Cai*
Department of Mathematics University of California, Los Angeles Los Angeles, CA 90095, USA hqcai @math. ucla.
Jialin Liu Decision Intelligence Lab Damo Academy, Alibaba US Bellevue, WA 98004, USA jialin. wwwealllualaaaa sataaalbbbabiiin innbbannn...... com com
Wotao Yin
Decision Intelligence Lab Damo Academy, Alibaba US Bellevue, WA 98004, USA wotao. Notao.yineall www.yyyinnaaaaaiii.. com
Abstract
Robust principal component analysis (RPCA) a critical tool in modern machine learning, which detects outliers in the task of low-rank matrix reconstruction. In this paper, we propose scalable and learnable non-convex approach for high- dimensional RPCA problems, which call Learned Robust PCA (LRPCA). LRPCA highly efficient, and its free parameters can effectively learned to optimize via deep unfolding. Moreover, tions to infinite iterations via a novel feedforward-ree reeerd-reuueettmiiii 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, both synthetic datasets and real-world applications.
extend deep unfolding from finite itera-
neural network
Introduction
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 [113] RPCA also plays a key role in wide range of machine learning tasks, such video background subtraction [14) singing-
separation [5] face modeling [16), image alignment
17] feature identification [18,, community detection [19, fault detection (20), and NMR spectrum
recovery [1]] While the standard principal component analysis (PCA) 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.
R Xn2
(I)
where X, is a rank-r data matrix and S, is a sparse outlier matrix, reconstruct X, and S, simultane- ously from Y.
One of the main challenges designing an RPCA algorithm is to avoid high computational costs. Inspired by deep unfolded sparse coding [22]. some recent works 25 have successfully extended deep unfolding techniques to RPCA and achieved noticeable accelerations in certain applications.
Authors listed in alphabetic order. Correspondence shall be addressed H.Q. Cai.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Specifically, by parameterizing 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-base -aasin 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 ((n²) to (n²r) 2 with some large hidden constant in fronf 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-leane method for high- dimensional RPCA problems?" and "Do we have to restrict ourselves to finit-iiteaatinn unfolding (or fixed-layer neural network)?" In this paper, we aim to answer these questions by proposing scalable and learnable approach for high-dimensional RPCA problems, which has flexible feedforward- recurrent-mise mixed neural network model for potentially infinite-iteratio unfolding. Consequently, our approach can satisfy arbitrary accuracy without relearning the parameters.
Related work.
The earlier works 13 for RPCA are based on the convex model:
minimize X.S
X
+ S|S subject to Y = S.
(2)
It has been shown that guarantees exact recovery. provided a S (()/pr), a condition with an optimal order [4.. Therein, a is the sparsity parameter of S, and μ is the incoherence parameter of L., which will be formally defined later in Assumptions 2 and respectively. Problem (2) can be transformed into a semidefinite program and has a variety of dedicated methods, their per-iteration complexities are least On²) 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 a 2 111/22/3,2//0 [6] develops an alternating projections method (AltProj) that alternativey projects Y - S onto the space of low-rank matrices and Y X onto the space of sparse matrices. AltProj costs (n2 flops and tolerates outliers up to a S (1//rr). An accelerated version of AltProj (AccAltProj) was proposed in [10, which improves the computational complexity to ((n2r) with sacrifices on the tolerance to outliers, which are allowed up to a I (1/ max max{ur²2 x². 1u /23 )))²)), where is the condition number of X, Note that the key technique used for outlier detection in AltProj and AccAltProj is employing adaptive wee-thhresholdig parameters.
Another line of non-convex RPCA algorithms reformulate the low-rank component as X = LR.. where L E R and R E R and then performs gradient descend 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 R R||.. While GD costs only (n?rr flops per iteration, its convergence rate relies highly on K. Recently, ScaledGD [12] introduces a scaling term in gradient descend steps to remove the dependence on i in the convergence rate of GD. ScaledGD also drops the balance regularization and targets on more elegant objective:
minimize
LR S - +- subject to S is a-sparse,
LE Xr. R _S2R"1Xm2
2
where a-sparsity means no more than a fraction a 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:
[M
if [M] 2 [M]] (32)) and [[M,,] 2 [[ (ām1)
(Ta
(4)
0,
otherwise
2 For ease of presentation, we take n == #n = n2 when discuss computational complexitics. 3 TTe hidden constant is often hundreds and sometimes thousands.

---

where 1. and [. [1)9]] denote the k-th largest element in magnitude on the i-th row and in the j-th column, respectively. In other words, Ta keeps only the largest & fraction of the entries every row and in every column. The per-iteration computational complexity of ScaledGD remains ((nrr) and it converges faster on ill-conditioned problems. The tolerance to outliers of GD and ScaledGD are S O(1 max maxx(19//2,37 prr²)) }) and S 0(1/)r9/2xx) 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 a technique that dates back to 2010 from a fast approximate method for LASSO: LISTA 22 parameterizes the classic Iterative Shrinkage- Theeaagogi--rehooinng Algorithm (ISTA) connected 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 -f--nnitudeu 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" (7739) parameterizes iterative algorithms as recurrent neural networks and shows great potential on machine learning tasks.
fully-
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 f,2 thresholding for outlier detection since the outliers in ultrasound imaging problems are usually structured. refRPCA (25] focuses video bagroouudbbakkgouuddd 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 remarkable speedup from basclines; however, such RPCA applications are limited.
Contribution. In this work, we propose a novel learning-basee 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. uses a simple formula and differentiable operators to avoid the costly SVD and partial sorting (see Algorithm I LRPCA costs On?2r) flops with a small constan while all its parameters can be optimized by training.
2. An exact recovery guarantee is established for LRPCA under some mild conditions (see Theorem Db. In particular, LRPCA can tolerate outliers up to a fraction of a S O(1/ur 3/2 Moreover, the theorem confirms that there exist set of parameters for LRPCA to outperform the baseline algorithm ScaledGD.
3. We proposed novel feedforward-recunr wererrrruuuuetiiiieee 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 performance reduction from classic deep unfolding.
4. The numerical experiments confirm the advantages of LRPCA on both synthetic and real- world datasets. In particular, we successfully apply LRPCA to large video background subtraction tasks where the problem dimensions exceed the capacities of the existing learning-basse based RPCA approaches.
Notation. For any matrix M, [M] denotes the (i, entry, as (MM denotes the i-th singular value. || := Ei, [[ |n denotes the entrywise E norm, || == (E.,g [M] denotes the Frobenius norm, |M := Σ, (M( denotes the nuclear norm, || Il == max., [[M],] kl denotes the largest magnitude, || == max; (E, [M,,), 1/2 denotes the largest row-wise l
norm, and M denotes the transpose. We use == (X.
(X.) to denote the condition number of X,.
'More precisely, LRPCA costs as low as 3n2r r + 3n² O (nr?) flops per iteration, which is much smaller than the hidden constant of truncated SVD.
3

---

2 Proposed method
In this section, we first describe the proposed Iearnable algorithm and then present the recovery guarantee.
We consider the non-convex minimization problem:
minimize LER"1XT, Reriaar,,R.2.____0 SERmm 2
LLRR T + S Y
subject to SSp S supp(S.). (5)
One may find (5) similar the objective (3) of ScaledGD but with 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 a-sparse. However, we emphasize that our algorithm design does not rely on an accurate estimation of o, 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 modified spectral initialization. In the second phase, we iteratively update outlier estimates via soft-threshodingg 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, We now discuss the key details of LRPCA and begin with
LRPCA, is summarized in Algorithm | the second phase.
Algorithm Learned Robust PCA (LRPCA)
Input: Y X, + Sy: sparsely corrupted matrix; r: the rank of underlying low-rank matrix;
{Ge]: a set of learned thresholding values; {mk J: set of learned step sizes.
2: // Initialization:
3: Su = (Y)
4: [Uo, Σo, Vol SVD,(Y - Sh))
5: Lo = U.E 1/2
Ro VoD
6: // Iterative updates:
7: while (Stooppiig Condition) do
8:
Sk+1 = Sc. (Y L2
9: L = Lx 77+11 Li R + S - R) R R -1
10: R = R& - Mh+1 L1 R + Sk+1 - Y) LL
11: end while
12:
Output: Xx = L R the recovered low-rank matrix.
Updating S. In ScaledGD [12,, the sparse outlier matrix is updated by Sk+1 Ta L where the sparsification operator Ta is defined in (4). Note that Ta requires an accurate estimate of a and its execution involves partial sorting on each row and column. Moreover, deep unfolding and parameter learning cannot be applied to Ta since is not differentiable. Hence, we hope to find an efficient and effectively learnable operator to replace Ta.
The well-known soft-thresholding, a.k.a. shrinkage operator, (M)() = sign([M]
(6) is our choice. Soft-thesholdiin has been applied as proximal operator of é norm (to matrix entrywise) 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 66 [0 22 29 34, 36), we seek for a set of thresholding parameters {G+} } that let our algorithm outperform the baseline ScaledGD.
max [M,[[[M]]] - -}
In fact, we find that the simple soft-thresholding:
Sk+1 Sçu.s -Y L
can also give linear convergence guarantee if we carefully choose the thresholds, and the selected {Gx} also guarantees supp(S), Sx) C supp(S.) at every iteration, i.e., no false-positive outliers. More- over, the proposed algorithm with selected thresholds can converge even faster than ScaledGD under the very same assumptions (see Theorem beloo for formal statement.) Nevertheless, the theoretical selection of (Cx) relies on the knowledge of X., which 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 fat matrices, that is, LR E R x with L R x and R R Denote the loss function fa = [L,, R = L
R + YIE. The gradients can be easily computed:
L.fe = (
Y--YRR
and = + -
(8)
We could apply a step of gradient descent on and R. However, 12 finds the vanilla gradient descent approach suffers from ill ill-conditionnng and thus introduces the scaled terms (R) Rx) and (L L,) - to overcome this weakness. In particular, we follow ScaledGD and update the low-rank component:
Lk+1 Lss 1 V (R) Rx)
Rk+1 = Rs Th-11 VRfk (L Lx)
where 7 is the step size at the (k: 1)-th iteration.
Initialization. We use a modified spectral initialization with soft- toftthhresholding in the proposed algorithm. That is, first initialize the sparse matrix by So S, (Y), which should remove the obvious outliers. Next, for the low-rank component, we take Lo Un U and R = Vo % where Un Eg Vo is the best rank-r approximation (denoted by SVD,) of Y Sg. Clearly, the initial thresholding step crucial for the quality of initialization and the thresholding parameter Co can be optimized through learning.
For the scge-scale problems where even 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 [[]]
Computational complexity. Along with guaranteed linear convergence, LRPCA costs only 3n2r- 3n² + (nr²) flops per iteration provided r < n. In contrast, truncated SVD costs O(n²r) flops with much larger hidden constant. The breakdown of LRPCA's complexity is provided in Appendix B
Limitations. LRPCA assumes the knowledge of rran((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 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.
2.1 Theoretical results
We present the recovery guarantee LRPCA in this subsection. Moreover, when the parameters are selected correctly, we show that LRPCA provably outperforms the sate-oof-the-rrs
We start with two common assumptions for RPCA: Assumption 1 (u-incoherence of low-rank component). X. E R2ixnn is rank-r matrix with p-incoherence, i.e.
pr
pr
U. 12102,00 I V
and VV.112,00 S
(10)
n2
for some constant 1 1 S where U.E.V. is the compact SVD of X..
Assumption (a-sparsity of outlier component). S. E IR x is an a-sparse matrix, i.e., there at most fraction of non-zero elements in each row and column of S.. In particular, require a S 0 pr2))))) ) for the guaranteed recovery, which matches the requirement for ScaledGD. We future assume the problem is well-posed, i.e.,
& n.
Remark 1. Note that some upplications may have a more specific structure for outliers, which may lead to more suitable operator for S updating in the particular applicutions. 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 it is differentiable.
5

---

Technical innovation. The main challenge to our analysis is to show both the distance (i.e., dist LL,, Rs; L., RR), later defined in Appendix A) and for error metric (i.e., Lg R xx_ mox) are linearly decreasing. While the former takes some minor modifications from the proof of ScaledGD, By the rank- spansiiasity uncertainty principle, 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 (Guaranteed recovery). Suppose that X, is a rank-r matrix with y-incoherence and
S. is an a-spae matrix with a S 10'p/3/22 If we set the thresholding values Ço = Ixx and
k 110 for 2 for LRPCA, the iterates of LRPCA satisfy < - [ R X.
| - X. || S 0.03(1 0.6n)* o,
and supp(Sx) S supp(S.).
(11)
with the step sizes Tp = rj [ |.
Proof. The proof of Theorem is deferred to Appendix A
Essentially, Theorem states that there exists set of selected thresholding values {(k} that allows one to replace the sparsification operator Ta in ScaledGI) with the simpler soft-thresooddin operator Sc and maintains the same linear convergence rate 1 0.6r under the same assumptions. Note that the theoretical choice of parameters relies on the knowledge of X.-an an unknown factor. Thus, Theorem
D can be read as a proof for the existence of the appropriate parameters.
Moreover, Theorem shows two advantages of LRPCA:
1. Under the very same assumptions and constants, we allow the step sizes 17s to be as large 8, in contrast, ScaledGD has the step sizes larger than [[2] 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 dalse-positive outlier in S In contrast, Ta necessarily yields some false- possteiesiivee outliers in the earlier stages of ScaledGD, which drag the algorithm when outliers are relatively small.
metric
the latter is rather challenging and utilizes several new technical lemmata. Note that ScaledGD shows I R
1oo always bounded but not necessary decreasing, which insufficient for LRPCA.
3 Parameter learning
Theorem I shows the existence of "good" parameters {[*], {m 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 [ as layer of neural network and regard the variables Lg, R2. Sy as the units of the k-th hidden layer. The top part of Figure [ demonstrates the structure of such feed-forward neural network (FNN). The k--th layer is denoted as Lt- Based on 7 and (9), it takes Y as an input and has two parameters Çk, Th when k > 1. The initial layer Lo is special, it takes Y and r as inputs, and it has only one parameter Ço- For simplicity, we use θ ({G+ k= {7ı } to represent all parameters in this neural network.
Training. Given training data set Derain consisting of (Y, XX.) pairs (observation, ground truth), one can train the neural network and obtain parameters θ by minimizing the following loss function:
minimize (.)),..))PP.u.
0)) T- -
(12)
Directly minimizing 12 D called end-to-end training, and it can be easily implemented on deep learning platforms nowadays. In this paper, we adopt 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 + stages:

---

Lo(:sGu)
(1)
Cx Ck Sk)
Co)
Ck Cx(sness Sk)
(()
Y
r
Y
Figure 1: high-level structure comparison between classic FNN- deep unfolding (top) and proposed FRMNN-based deep unfolding (bottom). In the diagrams, Cs denotes the k-th layer of FNN and L is layer of RNN.
Training the 0-th layer with minimizeg Lo XX. 1F.
Training the 1-st layer with minimizeg L, R. x.1
Training the final layer with 12 minimizeg L -
neural network. One disadvantage 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 later) and their parameters should be trained individually. Thus, propose hybrid model that is demonstrated in the bottom part of Figure [ named as cendffowward-rcurret----iie neural network (FRMNN). We neural network. When & 2 K, in the (k K) K--th loop of the RNN layer, we follow the same calculation procedures with Algorithm 1 and determine the parameters ÇA and m by
recurrent neural network appended after K K-layer feedforward
7) = BTj-11 and = -
(13)
Thus, all the RNN layers share the common parameters 3 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 B and á minimize the convergence metric at the (K - KK-tth layer of RNN for some K > K:
minimize Ey ((.x.))) (x)) (g 0) (3 (B, xx 8.
(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) the parameters are trained via FNN model; and the stop condition can be (Error < Tolerance) our FRMNN model used.
In this paper, we use stochastic gradient descent (SGD) in the layer-wise training stage and use grid search to obtain 33 and since there only two parameters. Moreover, find that picking K +++ 3 < K < K 5 empirically good.
4 Numerical experiments
In this section, we compare the empirical performance of LRPCA with the state-of-the-arts: ScaledGI
12 and AltProj (6). We hand tune the parameters for ScaledGD and AltProj to achieve their best
7

---

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 19-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 online at /tttp:///gg thub. com/ caesaaraai/LLPCA
The code for LRPCA is available
Unfolding models. We compare the perfor- mance 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 O. For FRMNN model, we take K 10 and K 15 for the train- ing. The test results 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 (110-)) which is the machine precision since we use single precision in this experiment.
10
10
10
10
10
20
40
90
LLayers
Figure 2: Convergence comparison for FNN- based, RNN-based, and ORMNN-based learning.
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, compare per-iteration runtime 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 a and is significantly faster than ScaledGD. Finally, we compare the total runtime among LRPCA, ScaledGD and AltProj in Figure [5] Therein, find LRPCA is substantially faster than the state-of- the-arts if the model has been trained. The training time for models with different sizes and settings reported in the supplement.
10a
10
100
IRPCA
IRCA
X- X/Ix|l
LRPCA
ScaledGD
ScaledGD
ScaleeGD
Xx
10
to
x
X
XX
1044
10
10
15
10
20
40
60
lterations / Layers
lterations Layers
lterations
Layers
(a) a ====0 0.1
(b) 0.2
(c) a = 0.3
Figure 3: Convergence comparison for LRPCA and baseline ScaledGD with varying outlier sparsity 5.
Problem dimension 1000 and rank
Single step time (secs)
10
LRPCA
LRPCA
Runtime (secs)
ScaledGD
ScaledGD
AltProj
10a
10
0.05
0.1
0.15
0.2
0.25
0.3
0.05
0.1
0.15
0.2
0.25
0.3
Ourlier Spansity
Ourlier Sparsity
Figure 4: Single-step runtime comparison with emror bar for LRPCA and baseline ScaledGD with varying outlier sparsity a. Problem dimension n 1000 and rank 5. The results are based on running 100 iterations excluding initialization.
Figure 5: Runtime comparison with error bar for LRPCA and start-of-the-an (ScaledGD and Alt- Proj) with varying outlier sparsity a. Problem
dimension d = 3000 and rank 5. All algo- rithms halt when - S I|e < -
8

---

Recovery performance. We generate 10 problems for each of the outlier density levels (i.e., a) and compare the recoverabilities of LRPCA and ScaledGD. The test result is presented in the Table [| where we can conclude that LRPCA is more robust when a is larger.
Table I: Recovery performance under different outlier density levels.
0.4
0.45
0.5
0.55
0.6
0.65
0.7
LRPCA
10/10
10/10
10/10
9/10
8/10
0/10
0/10
ScaledGD
10/10
10/10
0/10
0/10
0/10
0/10
0/10
Video background subtraction. this section, we apply LRPCA to the task of video background subtraction. We use VIRAT video datasefa 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 verification 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 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 summarized in Table 2 and selected visual results for LRPCA are presented Figure One can see L.PCAA 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.
the low-rank component of the data
Table Video details and runtime comparison for the task of background subtraction. All algorithms halt when max X X 11lll///||XX-11 [r, S S ||/l/// (1(p) < 10-3
VIDEO NAME
FRAME SIZE
FRAME NUMBER
RUNTIME (secs)
LRPCA
ScaledGD
AltProj
ParkingLot
320 x 180
965
16.01
260.45
63.04
ParkingLot2
320 180
2149
33.95
639.03
144.50
ParkingLot3
480 x 270
1110
38.85
662.08
166.91
Stree View
480 270
1034
33.73
626.05
167.66
Ultrasound imaging. We compare LRPCA with CORONA 233, a state-of-the-art lcarning-base 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//. http://wwwoo..oo/////////w/....w www.om. weizmann ac ac. ie. ic.ii/nn Each example is of size 1024 x 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( A.So(Xottputt X.), where
MSE stands for the mean square error. The test results summarized in Table
Table 3: Test results for ultrasound imaging.
ALGORITHM AVERAGE INFERENCE TIME
AVERAGE loss
LRPCA CORONA
0.0057 sees
9.97 10-4
0.9225 secs
4.88 x 10 -4-
Note that LRPCA is designed for generic RPCA and CORONA is specifically designed for ultrasound imaging. Thus, it is not surprise that our recovery accuracy is slightly worse than CORONA.
Available at: https::/virattaaa.
'The names of the tested videos are corresponding to these original video numbers in VIRAT dataset:
PorkingLot2: S. 01011011000000000000000100111000 010100005_0009111111111111111111 05_000991_001017 ParkingLotl: S. 00020400000 0015200522202 001527_001560, 00156000
ParkingLot3:
S. $500244 00. 000000. 000066. Stree View: S. 050100 13 002222222222221111 002244..

---

Figure 6: Video background subtraction visual results for LRPCA. Each column represents selected frame from the tested videos. From left to right, they are ParkingLotl, ParkingLot2, ParkingLott and Street The first row contains the original frames. The next two rows are the separated foreground and background produced by LRPCA, respectively. More visual results for ScaledGD and AltProj are available in Appendix C
However, the average runtime speed advantage will be even more significant on larger-scale examples, which is indeed our main contribution: scalability.
of LRPCA is substantially faster than CORONA. We believe that our
More numerical experiments. There are some other interesting empirical problems worth explore and we put the extra experimental results in Appendix C due to the space limitation. They summarized here: 1. Our model has good generalization ability. We can train our model 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
or with higher rank (say, = 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.
1000 and
5 Conclusion and future work
We have presented a highly efficient learning-basse approach for high-dimensional RPCA problems. In addition, we have presented novel 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 superior to the state-of-the--rts. the-artss
neural network model which can
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., partialGI g PG-RMC 19. 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
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.
10

---

References
[T] John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, and Yi Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. In Advances in Neural Information Processing Systems, pages 2080-20888 2009.
[2] Zhouchen Lin, Minming Chen, and Yi Ma. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv preprint 1009,5000 2010.
[3] Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM, 58(3):1, 2011.
[4] Daniel Hsu, Sham M Kakade, and Tong Zhang. Robust matrix decomposition with sparse corruptions. IEEE Transactions on Information Theory, 57(11):7221-72333 2011.
[5] Yudong Chen, Ali Jalali, Sujay Sanghavi, and Constantine Caramanis. Low-rank matrix recovery from errors and erasures. IEEE Transactions on Information Theory, 59(7)4434-4337, 2013.
[6] Praneeth Netrapalli, UN Niranjan, Sujay Sanghavi, Animashree Anandkumar, and Prateek Jain. Non-convex robust PCA. In Advances in Neural Information Processing Systems, pages 1107-1115, 2014.
[7] Quanquan Gu, Zhaoran Wang. and Han Liu. Low-rank and sparse structure pursuit via alternat- ing minimization. In Artificial Intelligence and Statistics, pages 600-609, 2016.
[8] Xinyang Yi, Dohyung Park, Yudong Chen, and Constantine Caramanis. Fast algorithms for robust PCA via gradient descent. In Advances in Neural Information Processing Systems, pages 4152-4160, 2016.
[9] Yeshwanth Cherapanamjeri, Kartik Gupta, and Prateek Jain. Nearly optimal robust matrix completion. In International Conference on Machine Learning, pages 797-805, 2017.
[10] HanQin Cai, Jian-Feng Cai, and Ke Wei. Accelerated alternating projectionn for robust principal component analysis. The Journal of Machine Learning Research, 20(1)6685-717, 2019.
[11] HanQin Cai, Keaton Hamm, Longxiu Huang, Jiaqi Li, and Tao Wang. Rapid robust principal component analysis: CUR accelerated inexact low rank estimation. IEEE Signal Processing Letters, 28:1 18:116-1201 120, 2020.
[12] Tian Tong, Cong Ma. and Yuejie Chi. Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. The Journal of Machine Learning Research, 22(150):1-63, 2021.
[13] HanQin Cai, Keaton Hamm, Longxiu Huang, and Deanna Needell, Robust CUR decomposition: Theory and imaging applications. SIAM Journal on Imaging Sciences, 14(4):1472-153, 2021.
[14] Won-Dong Jang, Chulwoo Lee, and Chang-Su Kim. Primary object segmentation in videos via alternate convex optimization of foreground and background distributions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 696-704, 2016.
[15] Po-Sen Huang, Scott Deeann Chen, Paris Smaragdis, and Mark Hasegawa-Johnson Singing- voice separation from monaural recordings using robust principal component analysis. In IEEE International Conference on Acoustics, Speech and Signal Processing, pages 57-60, 2012.
[16] John Wright, Allen Y Yang, Arvind Ganesh, Shankar Sastry, and Yi Ma. Robust face recognition via sparse representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(2):210-227, 2008.
[17] Yigang Peng, Arvind Ganesh, John Wright, Wenli Xu, and Yi Ma. RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(11):2233-2246, 2012.
[18] Jin-Xing Liu, Yong Xu, Chun-Hou Zheng, Heng Kong, and Zhi-Hui Lai. RPCA-based tumor classification using gene expression data. IEEF/ACM Transactions on Computational Biology and Bioinformatics, 12(4):964-970, 2014.

---

[19] Yudong Chen, Sujay Sanghavi, and Huan Xu. Clustering sparse graphs. In Advances in Neural Information Processing Systems, pages 2204-220111 2012.
[20] Yvon Tharrault, Gilles Mourot, José Ragot, and Didier Maquin. Fault detection and isolation with robust principal component analysis. International Journal of Applied Mathematics and Computer Science, ((()):49-442, 2008.
[21] HanQin Cai, Fian-Feng&&o Cai, Tianming Wang, and Guojian Yin. Accelerated structured alter- nating projections for robust spectrally sparse signal recovery. IEEE Transactions Signal Processing, 69:809-821 121, 2021.
[22] Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th International Conference International Conference Machine Learning, pages 399 406, 2010.
[23] Regev Cohen, Yi Zhang, Oren Solomon, Daniel Toberman, Liran Taieb, Ruud JG van Sloun, and Yonina C Eldar. Deep convolutional robust PCA with application ultrasound imaging. In IEEE International Conference on Acoustics, Speech and Signal Processing, pages 3212-3216, 2019.
[24] Oren Solomon, Regev Cohen, Yi Zhang. Yi Yang, Qiong He, Jianwen Luo, Ruud JG van Sloun, and Yonina C Eldar. Deep unfolded robust PCA with application to clutter suppression in ultrasound. IEEE Transactions on Medical Imaging, 39(4):1051-106; 2019.
[25] Huynh Van Luong, Boris Joukovsky, Yonina C Eldar, and Nikos Deligiannis. A deep-unfolded reference-based RPCA network for video geagroonddbackkrooun separation. In European Signal Processing Conference, pages 1432-1436, 2021.
[26] Jian-Feng Cai, Emmanuel Candès, and Zuowei Shen. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4):1956 1982, 2010.
[27] Søren Hauberg, Aasa Feragen, Raff Enficiaud, and Michael J Black. Scalable robust principal component analysis using Grassmann averages. IEEE transactions on pattern analysis and machine intelligence, 38(1 (1:21)2:22223311 2015.
[28] Rudrasis Chakraborty, Liu Yang, Soren Hauberg, and Baba Vemuri. Intrinsic Grassmann averages for online linear, robust and nonlinear subspace learning. IEEE transactions on pattern analysis and machine intelligence, 2020.
[29] Bo Xin, Yizhou Wang, Wen Gao, David Wipf, and Baoyuan Wang. Maximal sparsity with deep networks? Advances in Neural Information Processing Systems, 29:4340-4348, 2016.
[30] Yan Yang. Jian Sun, Huibin Li, and Zongben Xu. Deep ADMM-Net for compressive sensing MRI. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 10-18, 2016.
[31] Christopher A Metzler, Ali Mousavi, and Richard G Baraniuk. Learned D-AMP: Principled neural network based compressive image recovery. Advances in Neural Information Processing Systems, pages 1773 1784, 2017.
[32] Jian Zhang and Bernard Ghanem. ISTA-Net: Interpretable optimizzaiion-inspired deep network for image compressive sensing. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1828-1837, 2018.
[33] Jonas Adler and Ozan Öktem. Learned primal-dual reconstruction. IEEE Transactions on Medical Imaging, 332)-1332 2018.
[34] Jialin Liu, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. ALISTA: Analytic weights are as good as learned weights in LISTA. In International Conference on Learning Representations, 2019.
[35] Jiayi Shen, Xiaohan Chen, Howard Heaton, Tianlong Chen, Jialin Liu, Wotao Yin, and Zhangyang Wang. Learning minimax optimizer: pilot study. International Conference on Learning Representations, 2020.
12

---

[36] Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 38(2):18-44 44,,
2021.
[37] Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems, pages 3981-3989, 2016.
[38] Olga Wichrowska, Niru Maheswaranathan, Matthew W Hoffman, Sergio Gomez Colmenarejo, Misha Denil, Nando Freitas, and Jascha Sohl-Diekstein. Learned optimizers that scale and generalize. In International Conference on Machine Learning, pages 3751-3760. PMLR, 2017.
[39] Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstein. Understanding and correcting pathologies in the training of learned optimizers. International Conference on Machine Learning, pages 4556-4565 PMLR, 2019.
[40] Calypso Herrera, Florian Krach, Anastasis Kratsios, Pierre Ruyssen, and Josef Teichmann. Denise: Deep learning based robust PCA for positive semidefinite matrices. arXiv preprint Ttt::2004.136122 2020.
[41] Ivan Dokmanic, Reza Parhizkar, Juri Ranieri, and Martin Vetterli. Euclidean distance matrices: essential theory, algorithms, and applications. IEEE Signal Processing Magazine, 32(6):12-30, 2015.
[42] Venkat Chandrasekaran, Sujay Sanghavi. Pablo A Parrilo, and Alan S Willsky, Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization, 21(2):572-596, 2011.
[43] Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical linear convergence of unfolded ISTA and its practical weights and thresholds. In Advances in Neural Information Processing Systems, pages 9079-9089, 2018.
[44] Tianlong Chen, Weiyi Zhang, Zhou Jingyang, Shiyu Chang, Sijia Liu, Lisa Amini, and Zhangyang Wang. Training stronger baselines for learning to optimize. In Advances in Neural Information Processing Systems, pages 7332-7343, 2020.
[45] HanQin Cai, Zehan Chao, Longxiu Huang, and Deanna Needell. Fast robust tensor prin- cipal component analysis via fiber CUR decomposition. In Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, pages 189-197, 2021.
[46] Man-Feng Cai, Jingyang Li, and Dong Xia. Generalized low-rank plus sparse tensor estimation by fast Riemannian optimization. arXiv preprint 2103:22003.0889, 2021.
13


Reviews:
[{"review_id": "qm8USklruxW", "reviewer": "Reviewer_NqV9", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is well written and the thought process is clearly explained. Here are some detailed comments: \n\n**Originality:** A key contribution of this paper seems to be a hybrid Neural Network architecture that exploits best-of-both-worlds of Feedforward NNs and Recurrent NNs. This allows for the iterative optimization algorithm (essentially a modified version of scaled Gradient Descent) for *infintely* many iterations. To my best knowledge, I am not aware of such a approach. Thus, it would be nice to see a slightly more detailed review of such a discussion (on this line of work).\n\n\n**Quality:** The paper is well written and concepts are explained clearly. I think this is an interesting result, but I have the following main comments/questions:\n\n**Experiments**\n\n  - Firstly, the experiments are not very convincing. The reported run-time is definitely not a fair metric since the proposed method requires a massive NN that needs to be trained. The time taken for such training needs to be reported in ALL experiments. While I understand that training is a one-time cost incurred, this is also technically not true since if the data set changes (in test time, or said another way *if the network encounters an out of distribution sample*) then of course the network needs to be trained again. \n\n  - In the same vein as above, this makes the claim of the \"constant factor\" improvement in SVD not as impressive. Also to clarify, how do the authors attain this precise per iteration complexity (described in footnote 3)? There is no mention of this contribution anywhere later in the paper.\n \n- The experiments only show a run time comparison with existing methods, what about the output of the background subtraction?  This definitely needs to be included to show it outperforms (or performs at par) with existing methods. \n\n**Theoretical Contributions**\n\n- Firstly, the claim that the algorithm is better than state-of-the-art is misleading. There are key references (such as *Nearly Optimal Robust Matrix Completion*, Cherapanamjeri et al., '16 and references therein) that are missing. These provide better time complexity and outlier-tolerance (under the exact model considered in this paper). \n\n- Second, the claim that the result is better than [10] of the paper is also debatable. While I understand that tolerating a higher step-size is somewhat beneficial, a crtical point that has not been elaborated upon is that the $\\zeta_k$'s require the knowledge of $X_{\\ast}$ whereas [10] makes no such assumptions. \n\n- The fact that the threshold in soft-thresholding is reducing in every iteration is not a new idea.  This has in fact been the basis for *Non-Convex Robust PCA*, Netrapalli et al., '14, and follow up works\n\n\n**Clarity:** The paper is well written and explained. \n\n**Significance:** The paper introduces some new ideas regarding a hybrid model of feedforward and recurrent NN architectures. This seems to allow more control in iterative optimization procedures that is instantiated on a RPCA problem.\n\n-----------------------\n\nOverall, I believe that the paper has some good ideas, but the authors need to tone the discussion down  wherever applicable. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "kXymPXjLcmC", "reviewer": "Reviewer_7NwB", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers robust PCA under the usual assumption of the data being an additive composition of a low-rank matrix and a sparse (outlier) matrix. This is solved with a  technique that is quite similar to ScaledGD [10], which provide a neat gradient update that is numerically well-behaved. As I see it, the main contribution of the paper is then an 'unfolding' of this method such that it can be realized as (trainable) feed-forward neural network. This allows for significant speed-ups compared to similar methods.\n\nPositive:\n-- the paper is well-written, and does a nice job of placing itself with respect to the existing literature.\n-- the observation that an RNN version of the unfolded algorithm is unstable is (in many ways) unsurprising, but the straight-forward solution concatenating a feed-forward network with an RNN is neat. It's sufficiently simple that it trust it to work.\n-- the theoretical guarantees are nice; it's good to see that nothing is lost when going to more scalable algorithms.\n-- Theorem 1 seems quite useful as it justifies the simple soft-thresholding.\n\nLess-positive:\n-- While the paper does a nice positioning job relative to similar RPCA methods, other branches of the RPCA literature is ignored. E.g. statements such as \"Nevertheless, all existing approaches call an expensive step of singular value thresholding (SVT)\" (line 30-31) is only true with a highly narrow definition of RPCA. For example, methods based on Grassmann averages\n\n  *) Scalable Robust Principal Component Analysis using Grassmann Averages\n     Søren Hauberg, Aasa Feragen, Raffi Enficiaud and Michael J. Black.\n     In IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI).\n\n  *) Intrinsic Grassmann Averages for Online Linear Robust and Nonlinear Subspace Learning\n      Rudrasis Chakraborty, Liu Yang, Søren Hauberg and Baba C. Vemuri.\n      In IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI).\n\ndoes not suffer from such limitations. The first of the papers also demonstrated RPCA on terabytes of data (Star Wars IV, in HD resolution), which would indicate a significantly more scalable algorithm than the one presented here. I do not think that these (and similar) existing works diminish the contribution of the present paper, but the related work should be acknowledged.\n\n--  Related: I found it rather confusing that the paper argues that SVD is not needed by the proposed algorithm, yet, line 4 of Algorithm 1 is a call to SVD. I acknowledge that this is just *one* call to SVD where as existing methods call SVD repeatedly, but for large data sets even a single call to SVD can be computationally (and memory-wise) prohibitive.\n\n-- As I read the paper, the proposed method is very similar to ScaledGD. It isn't entirely clear to me if there are other benefits than a faster algorithm. Computational speed is important, so I think it is fine if a speed-up is the only benefit, but I could use a more explicit discussion of this in the paper.\n\n-- The section \"More numerical experiments\" could to with a rewrite. The current text states which additional experiments can be found in the supplements, but it would be better if the text also provided a high-level summary of the findings.\n\nOther:\n-- I could not find any mention of licenses in Section 4 even if this is stated in the checklist.\n-- The authors did not include code, but have promised to release upon acceptance. I find this satisfactory.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I was satisfied with this aspect of the paper.", "review_text": "", "extra_scores": {"ethical_concerns": "I see no ethical concerns; the work is methodological/theoretical.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "gyQIgo0g5Qy", "reviewer": "Reviewer_P4S4", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper is well written and well motivated. The proposed method makes a huge improvement compared to the classical solvers.\nMy main criticism is that the authors don't compare against other learned methods arguing that they are specialised on problem types. However, for a practitioner it doesn't matter if the method is generic for their specific problem, they just need the best one. Hence, I'd encourage the authors to show performance results against specialised learned methods. Even if each specialised method is marginally better than this generic one on one problem, this methods is still a major contribution to the scientific community. However, I think it is important to understand how they compare for each setting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any obvious limitations or societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "YPkf4tRYBCF", "reviewer": "Reviewer_3Wem", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and the motivation is clearly explained. The proposed LRPCA algorithm (Algorithm 1) is an improved version of the ScaledGD. They are different in the initialization and the update of the sparse matrix S. Theorem 1 can demonstrate the superiority of the proposed algorithm over the ScaledGD. On the other hand, the authors use RNN to determine the step size and thresholding parameter adaptively, which is new to me, though it is still in the traditional framework of \"learning to optimize\".\n\nThe paper has the following weakness.\n\n1. Some statements are not convincing. For example, in lines 34-38, the authors claimed that \"Another issue is that the existing approaches only learn the parameters for a finite number of iterations\". But I think this is not an issue. Nobody wants to use infinite number of iterations. \"Moreover, if the user desire a better accuracy later, one may have to restart the learning process to obtain parameters of the extra iterations\". One can just store the iterative information and restart from any iterations.\n\n2. In Theorem 1, the alpha should be no larger than a value scaled by 10^4. It is better to provide some examples of the values of \\mu, r, \\kappa to show that \\alpha can be large relatively.\n\n3. In Figure 3, it seems that the initialization plays a very important role in LRPCA. It is not clear that why the proposed method outperform the ScaledGD when alpha is larger.\n\n4. In Figure 4, it is not clear why LRPCA has less time cost per iteration than the ScaledGD. The authors haven't provided the computational cost of training the RNN. I think the per-iteration cost of the proposed method should be higher than that of the ScaledGD because it involves the RNN.\n\n5. In Table 1, the stop criterion may not be a good choice because the reconstruction error is sensitive the the sparsity of S. The authors may use the relative changes of the variables X and S instead.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies learned approaches to the problem of recovering a low-rank matrix from sparsely corrupted observations (here, RPCA). This problem has been intensely studied, and a number of methods have been proposed based on both convex and nonconvex optimization. The paper takes the perspective of *learned* optimization, in which one learns parameters of an optimization method from data, by interpreting iterations of the method as layers of a neural network. This has the advantage of adapting the method to (1) perform as well as possible for a given (small) number of iterations and (2) to perform as well as possible on data whose distribution mimics that of the training data. There are applications of learned optimization to RPCA. However, these approaches are based on the singular value decomposition, and so are not scalable to very large input matrices. 

The paper proposes a learned optimization method which combines soft-thresholding / proximal methods and a factorized low-rank model which is optimized using a scaled gradient descent (ScaledGD) which better copes with the ambiguity between factors. The paper uses learning to determine a sequence of step sizes and a sequence of thresholding parameters. The paper allows the learned method to be applied for arbitrary numbers of steps, by treating the layers as a recurrent neural net which can be iterated indefinitely. 

The main potential advantages compared to previous learned RPCA approaches are (1) avoiding the need to perform singular value decomposition, (2) the use of RNN’s enables the learned method to be applied for arbitrary numbers of iterations. 

The paper provides theoretical analysis showing that there exist parameters which enable linear convergence from an appropriate initialization (given by performing a single truncated SVD, as in many prior works). Experiments show significantly improved convergence speed compared to ScaledGD and alternating minimization. 

Initial reviews praised the clear motivation and presentation of the paper, as well as the idea of combining feedforward and recurrent networks to learn more flexible optimizers. At the same time, reviewers raised questions about the novelty of the paper’s proposals, the relationship to other notions of RPCA, and various aspects of the experiments. 

After responses from the authors, the reviewers converged to an evaluation of the paper as above the bar for acceptance, appreciating the paper’s empirical improvements, and the idea of combining feedforward and recurrent networks to handle arbitrary numbers of iterations. The paper would benefit from clarifications as to the novelty of the theoretical recovery results, and where technical innovations were required in the proofs.  
Decision: Accept (Poster)