Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery
Authors: Junhui Zhang
Jingkai Yan
John Wright
Venue: NeurIPS 2021 Poster (2021)
Keywords: matrix recovery
ADMM
convex optimization

Abstract: We propose a new framework -- Square Root Principal Component Pursuit -- for low-rank matrix recovery from observations corrupted with noise and outliers. Inspired by the square root Lasso, this new formulation does not require prior knowledge of the noise level. We show that a single, universal choice of the regularization parameter suffices to achieve reconstruction error proportional to the (a priori unknown) noise level. In comparison, previous formulations such as stable PCP rely on noise-dependent parameters to achieve similar performance, and are therefore challenging to deploy in applications where the noise level is unknown. We validate the effectiveness of our new method through experiments on simulated and real datasets. Our simulations corroborate the claim that a universal choice of the regularization parameter yields near optimal performance across a range of noise levels, indicating that the proposed method outperforms the (somewhat loose) bound proved here. 

Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery
Junhui Zhang
Department of Applied Physics and Applied Math Columbia University New York, NY 10027
j229038columbia. edu
Jingkai Yan Department Electrical Engineering Columbia University
New York, NY 10027 1y2927@columbia. edu
John Wright
Department of Electrical Engineering
Columbia University
New York, NY 10027
j=2966@columiaa.cm
Abstract
We propose new framework - Square Root Principal Component Pursuit for low-rank matrix recovery from observations corrupted with noise and outliers. Inspired by the square root Lasso, this new formulation does not require prior knowledge of the noise level. We show that single, universal choice of the regularization parameter suffices to achieve reconstruction error proportional to the (a priori unknown) noise level. In comparison, previous formulations such as stable PCP rely on noise-dependent parame- ters to achieve similar performance, and are therefore challenging to deploy in applications where the noise level is unknown. We validate the effec- tiveness of our new method through experiments on simulated and real datasets. Our simulations corroborate the claim that universal choice the regularization parameter yields near optimal performance across a range of noise levels, indicating that the proposed method outperforms the (somewhat loose) bound proved here.
Introduction
The problem of recovering low-rank matrix from unreliable observations arises a wide range of engineering applications, including collaborative filtering [1], latent semantic indexing [2]], image and video analysis [ 4, and so on. This problem can be formalized in terms of the following observation model: given an observation D which is superposition
D
Lo low-rank
+
So spans
+
Zn noise
(1.1)
35th Conference Neural Information Processing Systems (NeurIPS 2021).

---

of an unknown low-rank matrix Lo, sparse corruptions Su and dense noise Zo, our goal is to accurately estimate both Lg and S..
This model has been intensely studied, leading to algorithmic theory for methods based on both convex and nonconvex optimization 66 | One virtue of the convex approach is that in the noise-free setting ( (Zo- = 0), is possible to exactly recover a broad range of low-rank and sparse pairs (Lo, Sa), with universal choice of regularization parameters, which does not depend on either the rank or sparsity. This makes it possible to deploy this method in
"hands-free" manner, provided the dataset of interest indeed has low-rank and sparse structure.
In the presence of noise, however, the situation becomes more complicated: all efficient, guaranteed estimators require knowledge of the noise level (or the rank and sparsity) [ [0]- This is problematic, since in most applications the noise level is not known ahead of time. In standard convex formulations, the appropriate regularization parameter depends on the noise standard deviation, leaving the user with a painful and time-consuming task of tuning these parameters on a per-dataset basis.
Motivated by this issue, we revisit this classical matrix recovery problem. The main contribu- tion of this paper is the proposal and analysis of a new formulation for robust matrix recovery, which stably recovers Lo and So without requiring prior knowledge of the rank, sparsity, or noise level. In particular, our approach admits a single, universal choice of regularization parameters, which under standard hypotheses on Lo and Sp, yields an estimation error proportional to the noise standard deviation a. To our knowledge, our method and analysis are the first to achieve this.
Our approach is based on a combination two natural ideas. For matrix recovery, we draw on the stable principal component pursuit [9], natural convex relaxation, which minimizes combination of the nuclear norm of L, the ε norm of S and the squared Frobenius norm I| of the noise. This a principled approach to handling both the structured components Lo, So and the noise: || can be motivated naturally from the negative log- ligeliikl of the gaussian distribution. Moreover, under mild assumptions on the rank and singular vectors of Lo and the sparsity pattern of So, the reconstruction error of stable PCP is Ol [
On the other hand, optimally balancing these terms requires knowledge of the standard deviation of the true noise distribution. To address this issue, we draw inspiration from the
square root Lasso [i]. The square root Lasso is a sparse estimator which achieves minimax optimal estimation with universal choice of parameters, which does not depend on the noise level. The core idea is very simple: instead of penalizing the squared Frobenius norm | of the noise, one penalizes its square root, / p. We call the resulting formulation square rool principal component pursuit (vPCP) ). Our new formulation has the benefit that with indepeendddd universal choice of regularization parameters, essentially the same level of reconstruction error can be achieved. This makes vPCP a more practical approach to low-rank recovery in unknown noise.
Due to the square root term, the objective function is no longer smooth or differentiable, and so cannot apply algorithms such the proximal gradient m Nevertheless, our new formulation remains convex and separable, i.e. the objective is the sum of functions of different variables, making Alternating Direction Method of Multipliers (ADMM) a suitable solver [1]] We test our new formulation with ADMM on both simulated data and real data in image processing. The experimental results show the effectiveness of our proposed new formulation in recovering the low-rank and the sparse matrix, and suggest that vPCP has better performance than anticipated by our loose upper bound of the reconstruction error.
1.1 Notations and Assumptions
We use ||]] |A| F, and || l. to denote the spectral, Frobenius, and nuclear norm of the matrix A, and A' its (conjugate) transpose. For convenience, we let X,- (Lo, So) be the concatenation of Lo and S.. We assume that Lg a low-rank matrix of rank whose compact
which requires the objective to be the sum of smooth and non-smooth function

---

SvD Lo = UEV' U R V R22xx and without loss of generality, "1 2 Let T= R E R R [ denote the tangent space of rank r matrices at Lg- In addition, we assume that So is sparse with support in Ω.
Since it is impossible to disentangle Lo and So if the low-rank matrix Lo is sparse, or if the sparse matrix So is low-rank, we make the following two assumptions:
Assumption 1.1 The low-rank matrix Lo satisfies the incoherence property with parameter i i.e.
max | 1 nu
vr
max esl2
vr
1 S
vr
n2
n1n2
Assumption 1.2 The support 5S is chosen uniformly among all sets of candinality m, and the signs of supports are random, i.e. (( (((i.) Ω = SS))ks < O((i.j) E 2 = 0.5.
These assumptions follow 6 indeed, our proof makes use of dual certificate constructed for noiseless low-rank and sparse recovery in that paper.
1.2 Problem Formulation and Main Results
Inspired by square root Lasso, we propose to solve the robust noisy matrix recovery problem through the following optimization problem:
PCP
min L.S
|L]l + X|SS|I + S -Dlr
(1.2)
The parameter À that balances the low-rank and the sparse regularizers is studied in
6
where it is shown that À = 1/v/ /mn gives exactrecover when Zo- = and the y || [ + S D penalty term in (1.2) is replaced with the constraint L + S D. In this work, this result and focus on the parameter μ.. Our main result is that under the aforementioned (standard) hypotheses on Lo and So, using a single, universal choice /22/2, vPCP
build
recovers Lo and So, with an estimation error that is proportional to the norm of the noise:
Theorem 1.1 Under Assumptions 1.1
1.2 provided that r, m satisfies
r S Pr R2
(log n
m S P.n1
(1.3)
where p. 11/10, Ps are some positive constants. Then there is numerical constant e such that with probability at least - eni 10 the /PCP problem [12 with X = 1/ //1 and /Tz2/2 produces
solution X (L such that
X -xool S 560 /m0il ZoliF.
(1.4)
Why is possible to achieve accurate estimation with single choice of μ? We draw intuition from a connection to the stable principal component pursuit formulations studied in p]. This work studies both constrained and unconstrained formulations:
StablePCP.
min L.S
|L||+
X||S||| s.t. | + S -DD 5.
(1.5)
StablePCP, min | + i|SS|| + L 1 --DS-D' --L+SDDI1
(1.6)
L.S
These formulations are equivalent, and equivalent to /PCP in the following sense: for each problem instance, there is a calibration of parameters 8 +> ++ μ such that /PCP StablePCP, u and StablePCP, have exactly the same set of optimal solutions. However, [1. (1.6) require that the parameters 5 and f be determined on an instance-by-instance basis, based on the noise level. Choosing these parameters correctly essential: (1.5), 8 should be chosen to be larger than Zo Ir. For square (n1
n) matrices, in a stochastic setting
in which (Zo)iy are iid \( o²), following [9,, J can be chosen as 20 This follows from
z > 1 since ||U [|:- r, and max; |U' I
3

---

the fact that in this setting n n-1/ |/ Zu| + 20 almost surely; setting j in this fashion ensures that the singular value shrinkage induced by the nuclear norm regularizer than the largest singular value of Zo-
is greater
In contrast to this o-dependent penalty parameter, fixing S = Su, /PCP formulation L- Lo
(.2)
requires 0 E a[I + [ Zo- Lolle), which translates into - | Lollo E 0 L ..
With the hope that Σ = Lu, and by the subdifferential formulatior we have μ Zul |aal 1. The concentration stated above then gives intuitive choice for μ 23
/ or μ cov/n for
nd
some en > O. The magic of vPCP is that by using the Frobenius norm instead of its square, the objective function becomes homogeneous, i.e. the gradient of the penalty term at the ground truth X, becomes independent, making universal penalty parameter possible.
1.3 Relationship to the Literature
The problem of low-rank matrix recovery from gross sparse corruption can be considered form of robust PCA, [6] 13 and has been studied extensively in the literature. Algorithmic theory has been developed for both convex 66 13
15 [6]] and nonconvex optimization methods [7 18 While many of the aforementioned works pertain to noiseless data, a line of work has studied extensions to noisy data. [ studied the problem of robust matrix recovery with bounded noise under the incoherence assumption, and proved a bound on the recovery error, with linear dependence on the noise level but suboptimal dependence on the matrix size. [20] studied the problem with a weaker assumption about spikiness using decomposable regularizers and restricted strong convexity (RSC), and obtained essentially optimal bounds on the reconstruction error when the noise level is large. These weaker assumptions are not sufficient to ensure exact recovery, and so when the noise standard deviation a is small, this approach does not yield a reconstruction error proportional to the noise level. [10]] formulated robust PCA as a semidefinite programming problem, which requires strong assumptions about square matrices and positive semidefiniteness of the low- rank matrix. Some other works [21 22] further assumed partial observation of the matrix, and also derived tighter bounds on the recovery error. The recent work of [8] achieves optimal error bounds for both large and small noise, using a novel analysis that leverages an auxiliary nonconvex program. Taken together, these results give efficient and provably effective methods, whose statistical performance nearly optimal. Compared e.g., [8] 20 the stability guarantees provided by our theory are worse by a dimension-dependent factor. Nevertheless, all of the above works regarding robust PCA with noise, the optimization involves parameters that must be set based on the noise level distribution, and therefore pa
14
challenging in actual applications.
On the other hand, there has been existing work in the literature on structured signal recovery without needing to know the noise level. Our proposed square root PCP directly inspired by the square root Lasso [II, which proposed the idea of replacing the squared loss with its "square root" version. This allows for a choice of the parameter independent of noise level, while maintaining near-oracle performance. Later works have extended this idea to other scenarios, such as group lasso [23]], SLOPE variable selection [24]], elastic net [[5]] and matrix completion [26]], etc. Notably, the work of [26]] studied the matrix completion where one aims to recover low-rank matrix from noisy linear observations, aka matrix
completion. Compared with that paper, this work aims to solve a different problem where the observation also contains a sparse outlier matrix. To the best of our knowledge, this paper is the first to propose provable algorithm for Robust PCA with noisy observation that does not require knowledge of the noise level beforehand. On the algorithmic side, interior point method and first order method are used to solve the square root Lasso in [II], while later works apply ADMM to the problem [27 (28]. In our problem, the objective function can be transformed into separable form, making ADMM reasonable choice.
We note that for large a the error bound established this paper is suboptimal compared with [1] and [26]] The problem of square root lasso enjoys benign properties (lower bounds on restricted eigenvalues) which we do not have in square root PCP. The paper [26] on matrix completion makes a spikiness assumption, and proves that a square root
The subdifferential of norm satisfies 0|ıا|| = {= (x,
||||| $ 1).
4

---

lasso-inspired formulation achieves essentially optimal estimation when the noise is large. As with robust matrix recovery, the spikiness assumption not strong enough to imply exact recovery in the noiseless case. Compared to these works, the principal differences in this paper are (i) the problem formulation: we consider robust PCA with sparse errors, (ii) the analysis, which proceeds down different lines, and (iii) that our bounds are linear in the noise level, for both large and small noise. However, in contrast to [26]], our analysis does not yield minimax optimal estimation errors; it is worse by a dimension-dependent factor. Improving this dependence an important direction for future work.
Analysis
The proof of the main Theorem 1.1 is different from the standard approach in [11 due to lack of the Restricted Strong Convexity property for the map (L, + + D) Instead, our approach has three key ingredients:
The result from StablePCP, (Theorem 2.1 shows recovery error [[( (Lo, So)ll
which depends linearly on the parameter
The intimate connection between vPCP formulation (1.2 and StablePCP, formulation
1.5) can help translate the above solution property to vPCP (Lemma 2.2
The powerful dual certificate construction proposed in 66] (restated in Lemma 2.3 can be
used as an approximate subgradient to bound the regularizer X.
The proof of the main theorem has two steps. First, it uses the optimality condition and the subgradient to provide an upper and an lower bound for the regularization terms at X.
Second, the result in Theorem 2.1 is translated into the vPCP setting, and together with the bounds obtained above, we get the desired result. The proof given in the supplementary material, and below we provide three ingredients.
First, we state the main theorem for StablelPPP, problem:
Theorem 2.1 (Theorem in [9] Under Assumptions 7.1 and assumiing further that r S 02 (on2v-(loggn (logni) and m pi where prrs P', are some positive constants, there is a numerical constant è' such that with probability at least 1 c'ni"" -10 for any Zo with || S 8, the solution
X = (I to the StablePCP, problem 1.5 with À = 1/ /ni satisfies
x
Xulle S 3200m + 6.
(2.1)
Note that choosing 8 /Zol allows reconstruction error that O(yning) Z [F). In the case when Zo O, StablePCP, recovers the matrices exactly: = X This is in agreement with the result in [6]] The next lemma connects the two formulations vPCP and StablePCP. and the proof is provided in the supplementary material:
Lemma 2.2 Consider the VPCP problem parameterized by and denote the result as formulCCtooonmulatioo parameterized by 8 and denote the re- sult as (8), (5). Define 8(μ)) = D|D Lroo((p) S,oo0 (H))l then Estable (5(z)). Satable (ō(n)) = Eroot (w), (1).
Eroor Sroot (11), well the StablePCP, formulation
(2.2)
Lastly, we show an adapted dual certificate construction:
Lemma 2.3 (Adapted from 6 Under Assumptions I.1 and 1.2 assume that r, m satisfies
r S PyTe P (logn11) -2 m S P.nin
(2.3)
where pr 11/10, Ps are some positive constants. Then there is numerical constant e such that with probability least 1 en there exists W, F, H such that
UV + W X(sign(So) F P PaH),
(2.4)
where W E L || < } P.F = 0, F < }/2 and |P S 260

---

The dual construction in 6 satisfies | S J. However, the proof for Lemma 2.8(b)
Vr/u2 nf and we only need to make sure that Vr/m2
indicates that Po
af S 260v2
This is very mild condition, especially when it comes to the high dimensional real data (such as video). If we require that r v n2/10, then problems reasonably large dimension
suffice, say, 2 120. And in the extreme case, we can set Pr S 1/2220/
Solving v /PCP with ADMM
Different from 9 where StablePCP,, "n (1.6) is solved via Accelerated Proximal Gradient method, we we solve vPCP (and StablePCP,, ..) via ADMM-plliting since the objective is not differentiable.
To avoid multi-block ADMM which is not guaranteed to converge [29]] we define variables
x [Li z ), X = (Lg S2), and reformulate problem 1.2) as:
min f(X1)
= ||ll| + A||Si|l + / 1
(3.1)
X
I
0
8.t.
Xi
+
0
I
X2
D
The problem (3.1 can be separated into 2 blocks nicely (X, and X2), which guarantees
convergence of ADMM (under additional mild conditions) [12]]
Define dual variables Y = (Yi' Yg Y3'), the Lagrangian can written as
C,(X1, X2, Y)=
LL |l. S || 7 + (L L2, Y1) + 2 I L2ll (S1 S2, Y2)
- 221 + (L2 S₂ + Z D. Y, L S + Z D 2
We present the update rules well as the stopping criteria adapted from 12 in Algorithm aadd helper( () function in the supplementary material. The stopping criteria takes into account the primal and the dual feasibility conditions, and the algorithm stops when the tolerances set using an absolute and relative criterion are reached.
we modify the update of in Algorithm Z + (D- L2 S2 -2- x-)) /(1+ #/p)), we
get ADMM for StablePCP, (1.6).
Algorithm Algorithm for / PCP
Input: E R2 Xn2 X, Output: L, R2xxa2
Z <- prox |1-IF
D L2 S 1
L2 - (D-2
# Tolerance levels, max iterations
Cabs 10-6 Erel +- 10 N + 5000
S - (D-2+25,
L+ I1 (2Y, V, Ys))
# Initialization
Yi - Yi p(L L2)
L1, L2, S1, 52, Z. Y. Y2, Y3 + Op, Xng
Y₁ + Y2 p(s - S2)
< 0.1
Y3 Ys+ p S2 2 D)
for 1 N. N.i++ do
# Update and check convergence
# Save old values temporarily (L/2, 5%) +- (L2, S2)
P. ifConverge helper ()
if ifConverge then break end if end for
# ADMM updates
L + Prox! 1-11.
L2 _
S prox ||-1|
S2 1
S) + ((L) + L2) +2)222 return L, S
*Recall that prox,1-1- -.1 (Z) E, max(A, 7, O),, where Z Σ, A,u,? is the SVD, [prox,1-11 (Z)),.s max] 7, 0) sigu (Z.,), and prox.11115 (2) max( Z 0) T

---

4 Experiments
To show the effectiveness of our new formulation, we test vPCP on simulated data as well as real-world video datasets. The experiments suggest that our error bound in Theorem [.1 has a correct dependency on the noise level of Zo, but loses factor of n (the dimension of the problem). In addition, the solutions produced by vPCP with our proposed noise- independent y and StablePCP,, a with the noise-dependent μ often look very similar to each other. Moreover, experiments on real-world datasets with natural noise also show the denoising effect of vPCP, making vPCP practical approach with good performance in this robust noisy low-rank matrix recovery setting.
Additional experiments of /PCP on simulated data with varying / also suggest that v n2/2 /2 can provide performance (recovery error) close to the optimal ju, justifying our proposed choice of μ = 12/2
4.1 Simulations with Varying Noise Levels and Dimension
In this set of experiments, we are interested in how our error bound in Theorem 1.1 compare with the actual reconstruction error. We simulate (Lo, So Zo) with varying noise levels of Zo and problem dimension n1, n2. To simulate Lo E F x of rank r, we generate U I Xr, V E R"aXr as the unnormalized singular vectors such that U, V are entrywise ii.d. NO 1/n1) and ((0, 1/ng) respectively and let Lo UV* For So, we let P((i,j) Q] = ps and for (i,j) in support Ω (1.) E {0.05, - with equal probability. For the noise Zo, we generate it as entrywise i.i.d. o²).
In addition, in the experiments we take n1 n12 n1 so we choose = 1/v Mstable 1/(20 (the noise level a is known), and Proot = vn/2. Theoretical analysis in Theorem 1.1 and 2.1 shows that with these parameters, X Xoll
Zoll).
To test the dependency of the error on o, we take n = 200, r= 10, and so | m 10. For the outlier So, we take ps 0.1, so || & 0.05", ps = 10. For the noise Zo, we take a E (0,0.001,
0.015 so || 2 x nn E [0,9]. For each a the given set, we randomly generate 20 ground truth (Lu, So Zo) triplets and run vPCP and StablePCP, a on them. We use the mea--mean-squared (RMS) error defined as 1 Σx [[ Loll 20
1/2 and (1) E (|(()) // for evaluation. In Figure (a) we show the RMS error over 20 trials for the low-rank and the sparse. is clear from the plot that | Lolle and ||S Su
are ((r) for both /PCP and StablePCP,,, u, which confirms that the reconstruction error is linear in the noise level a.
We also notice that the recovery error in Figures ((a) and [cc) is linear in the noise level for small o, but exhibits a sublinear behavior for larger σ. This behavior reflects a general phenomenon in recovery/denoising using structured models (sparse, low-rank, etc.): the minimax noise sensitivity 7) = sup7>0 Fill@ æoll] is obtained as - 0. This means that for small a, we expect a linear trend with slope while for larger a, the dependence can be sublinear. This behavior has general geometric explanation. For simplicity we sketch how this plays out in a simpler norm denoising problem, in which the target is to recover structured signal Vo, and we observe y = Do + az. For simplicity, assume that we know that ||oo|]| S T, and solve minj sr ||æ y/12- For small a, the estimation error ã 2o is simply the projection of the noise σæ onto the descent cone of the norm ball {||ø|]] < 7} at Po; its size is linear in a. For larger a, there is additional denoising due to the fact that the L1 ball is smaller than the descent cone at z0g this leads to the behavior observed here.
To test the dependency of the error on the problem dimension, we vary {200, ,,0,,..,,,00,, 1000) and take r = 0n We keep the setting for So, and take a = 0.01 as the noise level for Zo. Figure ((bb shows the RMS error. Note that for fixed Zoll no, so the results in Theorem 1.1 and Theorem 2.1 bound the reconstruction error as O(n)).
E
When 0 and jisable +oo, StablePPP is equivalent to StablePCP. with 6 0.
7

---

However, the analysis provides only loose error bound. As can be seen from this set of experiment, the error is closer (n). We provide experiments with different distributions of the noise in the appendix.
(a) RMSE, vary (b) RMSE, vary (c) "hall" + noise
Figure 1: StablePCP, vPCP: a,b): simulated, c): hall
4.2 Real Data with Added Noise: Surveillance Video
Many imaging datasets can be modeled as the sum of a low-rank matrix Lo, a sparse outlier Su, and noise Zo. For instance, video data often consists of an almost fixed background which can be seen as low-rank, and foreground (such as people) that only occupies a small fraction of the image pixels for short amount of time, which can be considered as sparse. Thus, videos can naturally fit into our robust PCA framework.
In this set of experiments, we use /PCP and StablePCP, to separate the background and the foreground for surveillance video data. We assume that the original video noiseless, and manually add noise Zo that is entrywise i.i.d. (0,, o²) to test the dependency of the reconstruction error on the noise level a.
We use the "hall dataset" in [30], 200-frame video of a hall that has people walking around. Each frame has resolution 144 x 176, and flattened as one column of the noiseless observation matrix D,
have пı 144 x 176 and n2 200. Each pixel is represented by a number in [0, 255], and the mean value among all pixels is 150.3295, with standard deviation 44.7 and median 155.0000.
For the added noise, we choose a E (0, 30, 60, 90, 120}, and denote the recovered matrices
X=() as root/stable' In addition, we let Xn 1 (X (0)
+ X stahle) be the ground truth, and
root
evaluate the error using
[[[[]]
Lo l and || root/sttblle Soll We take 1/ /T,,
root/stable
Mroot n2/22 and Mstable a(vittin following the same intuition in Section 1 We
run the experiments on a laptop with 2.3 GHz Dual-Core Intel Core i5, and set the maximal
iteration of ADMM to be 5000. All of these experiments on real datasets end within 1 hour. For full details, please see the supplementary material.
In Figure I(c) show the reconstruction error with varying noise levels. It can be seen that the error is indeed linear in o, as predicted by our analysis. In Figures 2 we present the first frame (i.e. the first column) of the original video (with noise = 0, 30), and the /PCP recovered low-rank and sparse matrices. Although the added noise blurs the videos, our VPCP still stable and successfully decompose the background and the foreground.
(a) video
(b) (0)
(c) (
(d) video+ Zo (e)
(30) Foot
(f)
(30) Poot
Figure 2: hall frame 1: <PCP for 0, 30
4.3
Real Data with Natural Noise: Low Light Video
Low light videos are known to have very large observation noise due to limited photon counts. In this experiment, we apply our /PCP to the Dark Raw Video (DRV) dataset in [32] (under MIT License) for foreground background separation and denoising. This dataset of
Recall that Z||| <o(n vT22) for rectangular matrices, e.g. from 31

---

RGB videos, approximately 110 frames each, 3672 x 5496 in resolution, was collected at low light settings, so the signal-to-noise ratio (SNR) extremely low (negative if measured in dB)
For the experiments, choose video M0001 (basketball player), M0004 (toy windmill), and M0009 (billiard table) from DRV. As preprocessing, we convert the RGB videos to grayscale using rgb2gray( () in Matlab, and crop and downsample each frame to reduce data size. The final resolution is 322 x 440 for M0001, 294 x 440 for M0004, and 306 x 458 for M0009.
We apply vPCP with À 1/ and μ v n2/2 to these 3 videos, and present the results for frame 30 in Figure The denoising effect of vPCP can be seen by comparing D with L.S. In addition, L recovers the background pretty well, S captures the moving foreground but is still mixed with noise, which we believe due to the extremely low SNR.
D
L+S
M10001
M0009
Figure Low light video frame 30 M0001, M0004, and M0009 (Ø i. $ Đ) Image contrast is enhanced using imadjustn() in Matlab.
4.4 Real Data with Natural Noise: Optical Coherence Tomography
In medical imaging, Optical Coherence Tomography can be used for micro-scale resolution, quick scanning of biological phenomenon [33 These scans of the same scene over time, called time-lapse B-scan, are often noisy, but fit into our low rank/sparse model.
In this experiment, we apply vPCP the time-lapse B-scans (250 frames of resolution
300 x 150) of human trachea samples containing motile cilia (demo dataset of 33 under
CCO License). We present the recovered frame 50 and 100 in Figure As expected, Ż captures the static background, and š captures the motion of cilia.
D (b) ++ S (c) (a)
(d) S
(e) 7 (f) D (g) Ż 5 (h) Ż
(1)
S
(i)
Figure OCT, a-e): frame 50, f-j): frame 100 (2 L + S D).
4.5 Optimal Choice of μ
Our main result Theorem experimentally if this choice of optimal. We vary the problem dimensions and nı, the rank-dimension ratio Pr. : r/n (n ni = 222,, and the noise standard deviation a. For each choice of parameters (M1, 10,, o), we generate 10 pairs of (Lo, So. Zo) using the same method in Section 4.1 run vPCP with 1//ni and μ cuo, where μo /nz and is a varying coefficient (c 1/v2= x 0.71 corresponds our proposed value). Settings of all parameters are included in the supplementary material.
suggests a tuning-free. μ = /n2/2. Here, we investigate

---

We use the 10-average of [[Ł, (Lo. S as the evaluation metric. In Figure we show the heatmaps of this metric relative the optimal μ cyo among all tested c, i.e. ((L()))ip))) (Lo,)
(p))(p) minw/mepg heatmaps. From Figure
so the optimal μ has value each row of the we see that varying f1, n2 has little effect on the optimal choice
(a) vary 12 112
(c) vary PL Figure 5: (1)) under different varying parameters
(b) vary 7h
(d) vary
of μ,, which approximately between 0.7 /nz and / close to our /n2/2. However, decreasing pr. or increasing suggests smaller value of optimal μr. This makes sense because with higher level of noise or smaller rank (thus smaller norm || [a][F] [[]]F),, ) the SNR is smaller, so we should put smaller penalty on | Dllr. Nevertheless, in all these settings, choosing
4 / //2222 2 still gives satisfying results, the recovery errors for μ 0.7 /nz are close to the optimal performance: the error ratios are below 1.2. From these results, we believe that while / n2/2 2 may not be the optimal choice with respect to the recovery error, it can provide performance close to the optimal, and is therefore very effective choice.
5 Conclusion
In this work, we propose vPCP, convex optimization approach for noisy robust low-rank matrix recovery. The benefit of our approach as compared to previous methods such as stable PCP is that it enables tuning-frit recovery of low-rank matrices: theoretical analysis and simulations show that a single universal penalty parameter yields stable recovery at any noise standard deviation. Real video data experiments show suggest that many real life models fit into this low-rank plus sparse setting, and vPCP (as well as stable PCP) does good job in denosing and recovering the patterns of interest.
The presented experiments suggest the potential for both positive and negative societal impacts: visual surveillance can be abused, leading to significant negative impacts; at the same time, the denoising and foreground/ pengground//ackgrooun background separation ability of vPCP can help improve the quality of noisy data in biomedical and scientific research (e.g. medical imaging), and people's life (e.g. low light video).
Acknowledgement
We would like to thank Marianthi-Anna Kioumourtzoglou, Jeff Goldsmith, Elizabeth Gibson, Rachel Tao and Lawrence Chillrud for many helpful discussions around matrix modeling of environmental data and the need for tuning-free solutions. This work was partially funded by the National Institute of Environmental Health Sciences (NIEHS) grant R01 ES028805. We also thank Christine Hendon for helpful pointers regarding optical coherence tomography data, Jingkai Yan also gratefully acknowledges support from the Wei Family Foundation.
References
[1] Xiaoyuan Su and Taghi M Khoshgoftaar. A survey of collaborative filtering techniques. Advances in artificial intelligence, 2009, 2009.
[2] Thomas Hofmann. Probabilistic latent semantic indexing. In Proceedings of the 22nd annual international ACM SIGIR conference on Research and development information retrieval, pages 50-57, 1999.
10

---

[3] Benjamin Haeffele, Eric Young, and Rene Vidal. Structured low-rank matrix factor- ization: Optimality, algorithm, and applications image processing. In International conference on machine learning, pages 2007-2015. PMLR, 2014.
[4] Hongyan Zhang, Wei He, Liangpei Zhang, Huanfeng Shen, and Qiangqiang Yuan. Hyperspectral image restoration using low-rank matrix recovery. IEEE transactions on geascience and remote sensing, :2(8):4729-4443 2013.
[5] Hui Ji, Chaoqiang Liu, Zuowei Shen, and Yuhong Xu. Robust video denoising using low rank matrix completion. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1791-1798. IEEE, 2010.
[6] Emmanuel] Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (8AM)) 2011.
[7] Praneeth Netrapalli, UN Niranjan, Sujay Sanghavi, Animashree Anandkumar, and Prateek Jain. Non-convex robust pca. arxiv preprint arXio:1410.7660, 2014.
[8] Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan. Bridging convex and non- convex optimization in robust pca: Noise, outliers, and missing data. arXiv preprint 0rXtv:2001.05484, 2020.
[9] Zihan Zhou, Xiaodong Li, John Wright, Emmanuel Candes, and Ma. Stable principal component pursuit. In 2010 IEEE international symposium information theory, pages 1518-1522. IEEE, 2010.
[10] Yudong Chen and Martin Wainwright. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. ariio preprint ar xrXi::1509.0302, 2015.
[11] Alexandre Belloni, Victor Chernozhukov, and Lie Wang. Square-root lasso: pivotal recovery of sparse signals via conic programming. Biometrika, 98 94))::791-806 2011.
[12] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn., 311)11122, January 2011.
[13] Venkat Chandrasekaran, Sujay Sanghavi, Pablo A Parrilo, and Alan S Willsky, Rank- sparsity incoherence for matrix decomposition. JIAMJournall Optimization, 272)):577-- 596, 2011.
[14] Daniel Hsu, Sham M Kakade, and Tong Zhang. Robust matrix decomposition with outliers. arXiv preprint arXiv:1011.1518, 2010.
[15] Xiaodong Li. Compressed sensing and matrix completion with constant proportion of corruptions. Constructive Approximation, 37 3711:733-9, 2013.
[16] Yudong Chen, Jalali, Sujay Sanghavi, and Constantine Caramanis. Low-rank matrix recovery from errors and erasures. IEFE Transactions Information Theory, (7)):433 4337, 2013.
[17] Quanquan Gu, Zhaoran Wang Wang, and Han Liu. Low-rank and sparse structure pursuit via alternating minimization. In Artificial Intelligence and Statistics, pages 600- 609. PMLR, 2016.
[18] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR, 2017.
[19] Chong You, Zhihui Zhu, Qing Qu, and Yi Ma. Robust recovery via implicit bias of discrepant learning rates for double over-parameterization, 2020.
[20] Alekh Agarwal, Sahand Negahban, Martin J Wainwright, et al. Noisy matrix decompo- sition via convex relaxation: Optimal rates in high dimensions. The Annals of Statistics, 40(2):1171-1197, 2012.
11

---

[21] Olga Klopp, Karim Lounici, and Alexandre B Tsybakov. Robust matrix completion. Probability Theory and Related Fields, (1::5323-56,4, 2017.
[22] Raymond KW Wong and Thomas CM Lee. Matrix completion with noisy entries and outliers. The Journal of Machine Learning Research, 18(1):5404-5428, 2017.
[23] Florentina Bunea, Johannes Lederer, and Yiyuan She. The group square-root lasso: Theoretical properties and fast algorithms. IEEE Transactions on Information Theory, 60(2):1313-1325 2013.
[24] Alexis Derumigny et al. Improved bounds for square-root lasso and square-root slope. Electronic Journal of Statistics, 12(1)774,-766, 2018.
[25] Elias Raninen and Esa Ollila. Scaled and square-root elastic In 2017 IEEE Interna- tional Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4336 4340. IEEE, 1017,
[26] Olga Klopp et al. Noisy low-rank matrix completion with general sampling distribution. Bernoulli, 20) 2014.
[27] Xinyue Shen, Laming Chen, Yuantao Gu, and H. C. So. Square-root lasso with noncon- regularization: An admm approach. IEEE Signal Processing Letters, 23()):934-933 2016.
[28] Xingguo Li, Tuo Zhao, Xiaoming Yuan, and Han Liu. The flare package for high dimensional linear regression and precision matrix estimation r. Journal of Machine Learning Research, (6(18):553-55) 2015.
[29] Caihua Chen, Bingsheng He, Yinyu Ye, and Xiaoming Yuan. The direct extension of admm for multi-block convex minimization problems is not necessarily convergent. Math. Program., 155(1-)):57779, January 2016.
[30] Liyuan Li, Weimin Huang, Irene Yu-Hua Gu, and Qi Tian. Statistical modeling of complex backgrounds for foreground object detection. IEEE Transactions on Image Processing, 13(11):1459-1472, 2004,
[31] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, page 210-268. Cambridge University Press, 2012.
[32] Chen Chen, Qifeng Chen, Minh Do, and Vladlen Koltun. Seeing motion in the dark. In
2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 3184-3193, 2019.
[33] James P. McLean, Yuye Ling, and Christine P. Hendon. Frequency-constrained robust principal component analysis: a sparse representation approach to segmentation of dynamic features in optical coherence tomography imaging. Opt. Express, 25 25(1))22581- 25830, Oct 2017.
12


Reviews:
[{"review_id": "sck-ALhmP2p", "reviewer": "Reviewer_7yYW", "summary": "Low-rank matrix recovery in the presence of sparse corruptions and random noise, under incoherence assumptions on the low-rank and on the sparse components, have been considered. Following an existing line of work, a tuning-free optimization programs has been proposed for demixing and denoising. The analysis, utilizing existing techniques, establishes a bound on the reconstruction error. The bound has been observed to be loose by a dimension-dependent factor (according to the experiments and compared to other estimators for this problem). The estimator is a convex optimization problem which authors solve via ADMM.  Numerical experiments support the usefulness of the proposed approach in a set of synthetic and real data scenarios. ", "questions": "", "limitations": "", "rating": 5, "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": "I believe the work is original (of course, building upon a now well-known idea as in square-root lasso). The manuscript is clear and details have been provided. However, considering existing works on this approach, of design and analysis for a tuning-free regularized estimator, I think further examination is required to establish this proposal as a useful method in practice. \n\nline 59: I am not sure if the use of 'separable' (which I assume points to the splitting in ADMM) is appropriate. \n\nThe bullet point starting on line 165 seem to be referring to the proof of Theorem 1.1, but is rather technical and vague without further details. A rephrasing of this item could be helpful. \n\nProof of Lemma 2.2 in the Appendix has a few broken references. \n\nAppendix, the equations after (A.3), the third inequality: \n1) bounding r seems to require \\nu\\geq 1 \n2) it seems that 1/520 should be 1/(520 \\sqrt{n_1 n_2}), but the fourth inequality is correct. \nI am not sure if I understand why A.5 holds. Otherwise, the rest of the proof goes through. \n\nline 245: could you please elaborate on how the plot has been interpreted as O(\\sigma)? \nMoreover, the plots suggest a concave trend (authors concluded a linear trend; lines 246, 276). Any insights would be appreciated. \n\nThe visual inspections in sections 4.3 and 4.4 are difficult; Figures 3 and 4. Alternative presentation of the intended results and conclusions could be helpful. \n\nIt might be helpful to discuss the 'limitations' incurred by the homogeneity of the objective function (discussed on lines 106-112); for example in tuning or solving the optimization problem, etc. \n\nDo the authors have any intuition on the dimension-dependent factor in their bound? (lines 132-133, 159)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The proposal is a natural continuation on the idea behind the square root lasso and a few other tuning-free estimators. While such continuation of the underlying idea is undoubtedly valuable, I think a thorough examination of other aspects (beyond the design and the analysis of the estimator; e.g., tuning, computation, runtime, etc) could add further unique value. I believe the authors have already covered a number of interesting aspects (a bound, an algorithm, and the numerical experiments: varying mu, comparing the solutions themselves, etc). However, some further aspects could enhance the paper. Here are a few suggestions:\n- comparing the actual running time of 1) the other two formulations including their hyperparameter tuning 2) with the current proposal considering the quality of solutions (in an appropriae metric) and the possible need for tuning \\mu (to improve the quality of the solution); considering the comparable performance reported in Figure 1 in the Appendix, etc. It would be helpful to see such comparison in various data regimes. \n- further discussions on the dimension-dependent factor. \n- experiments with different noise distributions (which affects the range for \\sigma), closer to the distributions in real data (vision or others). \n\n\n\n======================== Update\n\nI have read the other reviews as well as the responses. I would like to thank the authors for their clear explanations. I think the proposed additions are satisfactory; except for the explanations in regards to:\n\n1) the sub-optimality of the bound, where I would like to (not necessarily as part of this review process) see further intuitions and arguments beyond the mechanics of the current proof. \n\n2) the presented experiments. I apologize as I can see that my original comment (the first bullet point in the above) is not very clear. What I meant was to suggest examining a possible scenario in which sqrt-PCP becomes overall computationally-expensive due to a requirement for tuning mu (motivation: sqrt-PCP has an additional non-smoothness compared to PCP, and, ADMM is a choice which requires examination). Let me elaborate: \n\nIt would be helpful if the authors could use a clear metric(s) for the the quality of the solutions (at the moment, in the Appendix, there are errors reported in Tables 1,2, and there are figures that are not easy to compare quantitatively) and then report wall-clock times for all three algorithms to achieve pre-specified levels of accuracy according to said metric (at the moment, the numbers in Tables 1,2, while comparable between the corresponding cells in the two tables, seem rather arbitrary). Note that in the second step, the desired accuracy determines the length of search for an appropriate mu. Tuning mu, if needed, would increase the wall-clock time for sqrt-PCP, and allows for understanding the limitations of the tuning-free estimator and the solver (e.g., in high-accuracy scenarios). Note that in this experimental setup, tuning for mu is not a choice but is rather dictated by the noise and the desired accuracy level. Finally, considering various data regimes allows for examining the above question when starting the search with the data-agnostic choice of mu=sqrt(n_2/2). \n\nI would like to emphasize that this suggestion is only to 'stress' the system in order to understand its limitations, and I would understand if the authors believe this is outside the scope of this work. However, I believe such examination is important in supporting the tuning-free claim for the proposal (in conjunction with the theoretical bounds). It would be nice to hear the authors' thoughts and whether I am missing a technical aspect in making this suggestion. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "eIFp7iU58PA", "reviewer": "Reviewer_PhKR", "summary": "This work combines stable Principal Component Pursuit and Square Root Lasso and proposes Square Root Principal Component Pursuit for low-rank + sparse recovery problem. Compared to stable PCP, Square Root PCP has the advantage that the choice of the regularization parameter is noise-independent, so it is easier to be deployed in applications where the noise level is unknown. Theoretical analysis and experiments confirm the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 7, "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": "Overall, this is a well written paper. It contains theoretical analysis that with a single, universal choice of the regularization parameter, the low-rank matrix and the sparse matrix can be stably recovered. ADMM is applied to solve Square Root PCP with details such as initializations and stopping criteria. This paper also contains experiments in different settings and they confirm the effectiveness of the proposed method.\n\nI am also satisfied with the improvements made for this resubmission. I have only one comment:\n\nThere are some existing works using ADMM to solve Square Root Lasso and it is worth citing them in this paper:\n- The flare Package for High Dimensional Linear Regression and Precision Matrix Estimation in R by Xingguo Li et al.\n- Square-Root lasso with nonconvex regularization: An ADMM approach by Xinyue Shen et al.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see the limitations in this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "dyMesJn1AdT", "reviewer": "Reviewer_WLTB", "summary": "The paper describes a square-root principal component pursuit for low rank matrix recovery, which is a modification of the original PCP approach in which the original squared Frobenius norm term is replaced with a non-squared term. The paper shows that this change allows one to set the weights of the regularizer in a manner independent of the noise level.", "questions": "", "limitations": "", "rating": 7, "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 notation (L,S) should be defined explicitly - is it a concatenation? It appears inside a Frobenius norm in line 169.\n\nIn Lemma 2.3, it is not clear what T, U and V are. Perhaps one should write L0 instead of UV*?\n\nIn Algorithm 1, although the proximal operators for ell1 and nuclear norm are well know, it is less clear what the proximal operator for the (non squared) Frobenius norm is. Is it a scaling of the matrix by its Frobenius norm? Adding detail on these would be welcome.\n\nIt would be good to discuss why the results in Figure 1(c) show no improvement for root PCP. It would also be good to have numerical comparisons with PCP with real data, perhaps in the supplemental material.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper states the noise regimes in which other algorithms exhibit better noise tolerance than the proposed approach; nonetheless, those must be aware of the noise level. Application-dependent social impacts are discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "-kFVWa73Zhw", "reviewer": "Reviewer_kjYV", "summary": "Motivated from square-root Lasso, this paper propose a new tuning-free convex program, called SR-PCP, to solve low-rank matrix recovery problem from observations corrupted by sparse outliers and dense noise.", "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": "Strengths:\n1. This paper proposes a new program which has appealing tuning-free property, and also provide theoretical guarantees as well as an ADMM algorithm to solve it. The theory is solid, and the paper is clearly written.\n1. SR-PCP improves the prior work [8] in the sense that one does not need to tune the regularization parameter, which either requires to estimate the noise level (which might be difficult) or using cross-validation (which lacks theoretical guarantee). Although the idea is not new (which originates from square-root lasso [11]), but it is still meaningful to introduce this idea to the field of low-rank matrix recovery.\n2. The authors proved stability bounds SR-PCP which scales with the noise level. This stability bound guarantees exact recovery when there is no noise, even in the presence of outliers.\n\nWeakness:\nThe main weakness of this paper, as the authors mentioned in Section 1.3, is that their estimation error bound is sub-optimal by a dimension-dependent factor. I think it would be better if the authors can provide more explanation on why this sub-optimality occurs compared to prior works, and if it is possible to generlize the proof of this paper to achieve the optimal rates.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work, and I think there is no potential societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the low-rank matrix recovery problem from observations corrupted by noise and sparse outliers. It proposes a framework called square root principal component pursuit, which is a combination of stable principal component pursuit and square root Lasso. The proposed technique has the advantage that the choice of the regularization parameter is noise-independent, so it is easier to be deployed in applications where the noise level is unknown. The main concern is about the estimation error bound obtained in the paper which is sub-optimal by a dimension-dependent factor. More explanation on why this sub-optimality occurs compared to prior works should be provided. 
Decision: Accept (Poster)