Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
Authors: Lijun Ding
Liwei Jiang
Yudong Chen
Qing Qu
Zhihui Zhu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Low rank
Robust recovery
Subgradient
Rank overspecification

Abstract: We study the robust recovery of a low-rank matrix from sparsely and grossly corrupted Gaussian measurements, with no prior knowledge on the intrinsic rank. We consider the robust matrix factorization approach. We employ a robust $\ell_1$ loss function and deal with the challenge of the unknown rank by using an overspecified factored representation of the matrix variable. We then solve the associated nonconvex nonsmooth problem using a subgradient method with diminishing stepsizes. We show that under a regularity condition on the sensing matrices and corruption, which we call restricted direction preserving property (RDPP), even with rank overspecified, the subgradient method converges to the exact low-rank solution at a sublinear rate. Moreover, our result is more general in the sense that it automatically speeds up to a linear rate once the factor rank matches the unknown rank. On the other hand, we show that the RDPP condition holds under generic settings, such as Gaussian measurements under independent or adversarial sparse corruptions, where the result could be of independent interest. Both the exact recovery and the convergence rate of the proposed subgradient method are numerically verified in the overspecified regime. Moreover, our experiment further shows that our particular design of diminishing stepsize effectively prevents overfitting for robust recovery under overparameterized models, such as robust matrix sensing and learning robust deep image prior. This regularization effect is worth further investigation.  

Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
Lijun Ding Department of Mathematics University of Washington 1jding@us edu
Liwei Jiang School of ORIE Cornell University 1j2820cornell. edu
Yudong Chen
Department of Computer Sciences University Wisconsin-Madison
yudongchen@wiscc. edu
Qing Qu Department of EECS
Zhihui Zhu Department of ECE University of Denver zhihui zhu@du edu
University of Michigan-Ann Arbor qingqu@umic ch. edu
Abstract
We study the robust recovery of low-rank matrix from sparsely and grossly corrupted Gaussian measurements, with no prior knowledge on the intrinsic rank. We consider the robust matrix factorization approach. We employ robust & loss function and deal with the challenge of the unknown rank by using an overspecified factored representation of the matrix variable. We then solve the associated non- convex nonsmooth problem using a subgradient method with diminishing stepsizes. We show that under regularity condition the sensing matrices and corruption, which we call restricted direction preserving property (RDPP), even with rank overspecified, the subgradient method converges the exact low-rank solution sublinear rate. Moreover, our result is more general in the sense that automatically speeds up to linear rate once the factor rank matches the unknown rank. On the other hand, we show that the RDPP condition holds under generic settings, such Gaussian measurements under independent or adversarial sparsc corruptions, where the result could be of independent interest. Both the exact recovery and the convergence rate of the proposed subgradient method are numerically verified the overspecified regime. Moreover, our experiment further shows that our particular design of diminishing stepsize effectively prevents overfitting for robust recovery under overparameterized models, such as robust matrix sensing and learning robust deep image prior. This regularization effect is worth further investigation.
Introduction
Robust low rank matrix recovery problems ubiquitous in computer vision [1], signal processing [2), quantum state tomography [3), etc. In the vanilla setting, the task is to recover a rank r positive semidefinite (PSD) matrix X, Rdddd d) from few corrupted linear measurements {(v,, A of the form
(1.1) where (st are the corruptions. This model can be written succinetly A(X.) + where A: dRd + Rm is the measurement operator. Recently, tremendous progress has been made on this problem, leveraging advances on convex relaxation [1, 2], nonconvex optimization [4-7], and high dimension probability [8 11]. However, several practical challenges remain:
y: = (A,, Xx) + Si
"The first authors contributed this work equally.
35th Conference on Neural Information Processing Systems (NeurIPS 202

---

Nonconvex and nonsmooth optimization for sparse corruptions. For computational efficiency, we often exploit the low-rank structure via the factorization X FFT with F E Rdxr, and solve the problem with respect to F via nonconvex optimization. This problem is challenging since the corruption can be arbitrary. Fortunately, the corruptions 8, are sparse [1]. This motivates us to consider the & loss function and lead to a nonsmooth nonconvex problem.
Unknown rank and overspecifieation. Another major challenge in practice is that the exact true rank r is usually unknown apriori. 2 To deal with this issue, researchers often solve the problem in rank overspecified regime, using a factor variable F E Ra*k with a larger inner dimension & > r. Most existing analysis relies the k-th eigenvalue of X being nonzero and is inapplicable in this setting. Recent work studied the problem either in some special case (e.g., rank one) [13] or under unrealistic communitability conditions [14].
Our approach and contributions. To deal with these challenges, we consider the following nonconvex and nonsmooth formulation with overspecified rank & 2 ?,
min FEROXK
f(F) = 2m 1=1
1
Σ (A,, FFT) Vil
1 2m
||((FFT) - v/12
(1.2)
and apply subgradient method with adaptive stepsize. We summarize our contributions below.
Exact recovery with rank overspecification. In Theorem 3.2, we show that under Gaussian measurements and sparse corruptions, with m = Ōdd-²) samples 3, even with overspecified rank k > r, our subgradient method with spectral initialization converges to the ground truth X₃ exactly.
When k > the convergence rate is ( in the operator norm error. ||F.TT XzIl. When
k == r, the convergence rate boosts to linear (geometric) rate.
Convergence under regularity condition. Our convergence result is established under a regularity condition termed restricted direction preserving property (RDPP); see Definition 2. 1. RDPP ensures that the direction of the sample subgradient stays close to its population version along the algorithm's 's iteration path. The key to our proof is to use this property to leverage a recent result on rank overspecification under smooth formulations [15]. Moreover,
show that RDPP holds with high probability under arbitrary sparse corruptions and Gaussian measurement matrices, Adaptive stepsize and implicit regularization As shown [13, 14], for overparamelrized robust matrix recovery problems, subgradient methods with constant stepsizes suffer from overfitting, even when initialized near the origin. In contrast, numerical experiments demonstrate that our theory- inspired diminishing stepsize rule has an implicit regularization effect that prevents overfitting. Our stepsize rule is easy to implement and almost tuning-free, and performs better than other non-adaptive stepsize rules (e.g., sublinear or geometric decaying stepsizes). We demonstrate similar good performance of our method (with a fixed decaying stepsize) in image recovery with a robust deep image prior (DIP) [16].
Related work. The nonconvex, factorized formulation (1.2) is computationally more efficient than convex relaxation approaches [1, 17-19), as involves a smaller size optimization variable and only requires one partial singular value decomposition (SVD) in the initialization phase. In the corruption-free (s, 0) and exact rank (k = r) setting, provably efficient methods have been studied for the smooth, lcast squares version of (1.2) [20-23]; in this case, the loss function has no spurious local minimum and is locally strongly convex [24,25] For smooth formulations with rank overspecification (k 2 or even & = d), gradient descent initialized near the origin is shown to approximately recover the ground truth matrix [26,27].
When the rank r is known and measurement corruption is present, the work [4] considers the smooth formulation and proposes gradient descent method with robust gradient estimator using median truncation. The nonsmooth formulation (1.2) is considered in recent line of work [5-7], again in the known rank setting (k= r), where they show that the loss function satisfics certain sharpness [28] properties and hence subgradient methods converge locally at a lincar ratc. The number of samples required in these works for exact recovery of X2 is (dr²²) when the corruption rate is sufficiently small. The (r-2) dependence due to their initialization procedure. We emphasize that the above results crucially rely on knowing and using the exact true rank. When the rank is unknown, the work [14] considers a doubly over-parne peer-parameterzeed formulation but requires a stringent, commutability
There are very few exceptions, such as the case of robust phase retrieval with 1 [12].
'Here Ô hides the condition number of X; and other log factors.
2

---

[4-7]
[13]
Ours
Rank specification
h:
r
k k21
Exact Recovery
X
Sample complexity
(dr
Oddha)
Table I: Comparison results on robust matrix sensing.
assumptions on the measurement matrices; moreover, their analysis concerns continuous dynamic of gradient descent and is hard to generalize discrete case. Our results only impose standard measurement assumptions and apply to the usual discrete dynamic of subgradient methods.
The work most related ours is [13], which studies subgradient methods for the nonsmooth formu- lation (1.2) in the rank-one case (r = 1). Even in this special case, only approximate recovery is guaranteed (i.c., finding an F with |FF Xt F (og(}) for fixed ô > 0). Additionally, the dk
number of samples required in [13] for this approximate recovery is 8 when the corruption rate sufficiently small. We note that the lack of exact recovery is inherent to their choice of stepsizes, and spectral initialization already guarantees | X1 IF X [13, Equation (85)). In contrast, our result applies beyond rank-l case and guarantees exact recovery thanks to the proposed adaptive diminishing stepsize rule. We summarize the above comparisons in Table 1.
2 Models, regularity, and identifiability
In this section, we formally describe our model and assumptions. We then introduce the restricted direction preserving property and establish a basic identifiability result under rank overspecification, both key to the convergence analysis of our algorithm given in Section 3 to follow.
2.1 Observation and corruption models
In this work, we study subgradient methods for the robust low-rank matrix recovery problem (1.2) under the observation model (1.1). Throughout this paper, we assume that the sensing matrices A, E Rdxd = 1,..., m are generated i.i.d. from the Gaussian Orthogonal Ensemble (GÒE).* That is, each A, is symmetric, with the diagonal entries being i.i.d. standard Gaussian (O, 1), and the upper triangular entries are i.d.d N (0, 2 independent of the diagonal. We consider two models for the corruption = (s1,..., Sm (i) arbitrary corruption (AC) and (ii) random corruption (RC).
Model 1 (AC model). Under the model AC A, p. m)) the index set S C (1.....,) entries of is uniformly random with size [pm].. independently of A, and the values of the nonzero entries are arbitrary.
.m of nonzero
Model 2 (RC model). Under the model RC(X,, A.p.m, each si, = 1,...,m m. is random variable, independent of A and each other, with probability p E (0, 1) being nonzero.
In the AC model, the values of the nonzero entries of s can be chosen in coordinated and potentially adversarial manner dependent on } and X,. whereas their locations are independent. Therefore, this model more general than those in [1, which assume random signs. 5 The RC model puts no restriction on the random variables } except for independence, and hence is more general than the model in [13]. In particular, the distributions
{s,} can be hcavy-tailed, non-identical and have non-zero means (where the means cannot depend on {A.)). Under the RC model, we can allow the corruption rate p to be close to 1 and still achieve exact recovery (see Theorem 3.2).
2
2.2 Restricted direction preserving property (RDPP)
When the true rank known, existing work [5, 6] on subgradient methods typically makes use of the so-called & isometry property (RIP), which ensures that the function g(X) 1 [XX) vll, concentrates uniformly around its expectation. Note that the factorized objective m
f in (1.2) is related to by f(F) (F With f1/22-Ri RIP, existing work establishes the sharpness of g when k i.e., linear growth around the minimum [5, Proposition 2]. In the
*Our results can be easily extended sensing matrices with i..dd. standard normal entries since X; is symmetric. 'Our results can be extended the even more general setting with adversarial locations [4-7], with an extra poly (k, x) factor in the requirement of the corruption rate p compared to the one we present in Section
3

---

d 50
d 100
d 200
d 300
RDPP:
D(X)) -
X; 1 IF
0.62/0.27
0.62/0.28
0.63/0.22 28
0.63/0.28
sign-RIP [13]: [[D()
2.26/1.01
3.17 42
4. 4.48/2.00
5. 5.49/2.45
||
Table 2: Comparison of RDPP and sign-RIP for d e {50, 100, 200, 300) and r E {1, 5). For each entry with two numbers, the left corresponds to 1 and the right corresponds to = 5. We set p 0 and 5dr. Note sign-RIP is never satisfied as the above entries for sign-RIP has value larger than equal
rank ovaresseeecciiittion setting, however, g is not sharp. as it grows more slowly than linear in the
direction of superfluous eigenvectors of F. We address this challenge by directly analyzing the subgradient dynamics, detailed in Section 3, and establishing concentration of the subdifferential of g rather than g itself.
Recall the regular subdifferential of (XX) [30] is
1
I x<0
m
D(X) ==
sign (A,; A,) and sign (r)
1, 1 I x=
(2.1)
x> 0
Since our goal is to study the convergence of the subgradient method, which utilizes only one member (X) and will be illustrated in Section 3.1, is enough to consider this member D(X) by setting sigu(x) 1, x 0
We are now ready to state the RDPP condition.
1, x 2
Definition 2.1 (RDPP). The measurements and corruption (:);; are said to satisfy restricted direction preserving property with parameters (K, 8) and a scaling function vp Raxd - IR if for every symmetric matrix X Raxd with rank no more than k', we have
m Σ
sign( X) A,) and [(X)- -xx)
X
D(X)
56
(2.2)
X
Here, the scaling function accounts for the fact that the expectation not exactly
X e.g., when no corruption, VE(g(X)) = / || How does RDPP relate to the f R122 In the absence of corruption, as shown Appendix H, RDPP implies /1/E2RRIP for S - Conversely, we know if R/22-RIP condition holds for all rank d matrices, then RDPP holds when p 0 [13, Proposition 9].
Our RDPP is inspired by the condition sign-RIP introduced in the recent work [13, Definition 1J. The two conditions are similar, with the difference that RDPP is based on the operator norm (see the inequality in equation (2.2)), whereas sign-RIP uses the Frobenius norm, hence a more stringent condition. In fact, the numerical results in Table 2 suggest that such a Frobenius norm bound cannot hold if is on the order (dr) even for fixed rank-1 X₃ in our experiments [D((), V
[E is always larger than 1,6 contrast, standard Gaussian/GOE sensing matrices satisfy RDPP for any rank k' 1, and it suffices for our analysis. Indeed, can show the following.
X
||
Proposition 2.2. Let m dk' (1og(+)v1)
For Model 1, (K', (8,6+3 de + 33))-RDPP holds with scal- ing function (X) = with probabiiiiy at least 1 -mm
For Model 2,
"To the best of our knowlegde, the proof of [13, Proposition 1] actually establishes a bound on the l norm of top singular values, called partial Frobenius norm, rather than Frobenius norm (i.e., the Ez norm of all singular values). This cousistent with our empirical observations in Table 2.
After the first version of this paper was posted, the work [31] became available, which is an updated version of [13]. In this updated paper, the definition and associated results for sign-RIP (see [31, Definition and Theorem 1J) the rank-r partial Frobenius norm, instead of the Frobenius norm used in the original [13, Definition
1].

---

(6-RDPPP holds with a scaling function v/ (X)
1 Ei= / (1-p+t pBs,
eexp( 2||x 2
)])
with probability at least 1 Ce-emó" Here c, c,C, C are universal constants.
Our proof of Proposition 2.2 follows that of [13, Proposition 5] with minor modifications accounting for our corruption models and the definition of RDPP. For completeness we provide the proof in Appendix C. The operator norm bound in the defimition (2.2) of RDPP turns out be sufficient for our purpose in approximating the population subgradient of f for our factor F.
2.3 Identifiability of the ground truth X;
If the exact rank is given (i.e.. (k: r)), it known that our objective function (1.2) indeed identifies Xt, in the sense that any global optimal solution F. coincides with X; = F.F. [5]. When k r, one may suspect that there might be an idenitfiability or overfitting issue due to rank oversepcification and the presence of corruptions, i.e., there might be factor F that has better objective value than F., where F. F. X; However, so long as the number of samples are sufficiently large m = P(dk), we show that the identifiability of X; is ensured. We defer the proof Appendix F.
Theorem 2.3. Fix any < 3.2 Under either Model I or Model 2 with corruption rate p. if m 2 cdk, then with probability at least 1 - any global optimizer F, of (1.2) satisfies F.F.T X₃- Here, the constants c, C1 > 0 only depend on p.
Here, overfitting does not occur since sample size m matches the degree freedom of our formulation (dk)) making it possible to guarantee success of the algorithm described in Section 3. On the other hand, we are in the hcavily overparameterized regime with m = O(dr) < dk (c.g.. k = d), the above identifiability result should not be expected to hold. Perhaps surprisingly, in Scetion 4 we empirically show that the proposed method works even in this heavy overparametrization regime with k d. This is in contrast to the overfitting behavior of subgradient methods with constant stepsizes observed in [14], and it indicates an implicit regularization effect of our adaptive stepsize rule.
3 Main results and analysis
In this section, we first introduce the subgradient method with implementation details. We then show our main convergence results, that subgradient method with diminishing stepsizes converge to the exact solutions even under the setting of overspecified rank. Finally, we sketch the high-level ideas and intuitions of our analysis. All the technical details are postponed to the appendices
3.1 Subgradient method with diminishing stepsizes
A natural idea of optimizing the problem (1.2) is to deploy the subgradient method starting from some initialization Fo E Raxk, and iterate"
Fr+1 Fe- Tttt,
It D(FFT X,).F ,t= 0, 1,2,
(3.1)
with certain stepsize rule n) 2 O. The vector 9t indeed belongs to the regular subdifferential of (f(R) = DTF,FT - F, by chain rule (recall D in (2.1)).
For optimizing nonconvex and nonsmooth problem with subgradient methods, should be noted that the choice of initialization and stepsize is critical for algorithmic success. As observed in Section 4. a fixed stepsize rule, i.c. stepsize determined before sceing iterates, such geometric sublinear decaying stepsize, cannot perform uniformly well in various rank specification settings, O(r), k d. Hence it is important have an adaptive stepsize rule.
c.g. r,
Initialization We initialize Fú by spectral method similar to [13] yet we do not require F to be close to X2 even in operator norm. We discuss the initialization in more detail in Section 3.4.
"A few authors [13, 15] refer to the setting with > r and m x dk as "overparamettization"" since k is larger than necessary Others reserve the term for the setting m < dk, ie., the number of parameters exceeds the sample size. We generally refer to the former setting "orank-ovverpeefffcatton and the latter as "overparametrizationn"" 'Recall the definition of the subgradient ((X) 1 >nd sign( X) - s.).A in (2.2) for the objective,
m
g(X)= = 2m |A(X)
y1 the original space X C B dxd
5

---

Stepsize choice To obtain exact recovery, we deploy simple and adaptive diminishing stepsize rule for Th, which is inspired by the analysis and is easy to tune. As we shall see Theorem 3.1 and its proof intuition in Section 3.3, the main requirement for stepsize is that it scales with || Xx|l
for an iterate F, and hence diminishing and adaptive as FFT - Xx- To estimate F X when corruption exists, we define the operator TA.((P) Rdxk
R and the corresponding stepsize:
TA E3 (1) FF y (m))))) and Th (yT.,.(Fi).
(3.2)
where Eg(+) is the median operator, and C > is free parameter to be chosen. As E| (A1, PFT) yn VIIFTT X1lir without corruption, expect TA, (F) estimate |FFT -xlllp well up to some scalar when corruption exists since median is robust corruptions.
3.2 Main theoretical guarantees
First, we present our main convergence result, that ensures that the iterate F,F. in subgradient method (3.1) converges to the rank ground-truth Xg, based on conditions on initialization, stepsize, (Xa) and RDPP. Let the condition number of X: be K = (x,) . the result can be stated as follows.
Theorem 3.1. Suppose the following conditions hold: (i) Ler e be a fixed parameter. Suppose Fo satisfies
FFFFFO -c" X²ll S co0,/K.
(3.3)
with some constant c* E Ele, 1] and co ōge for same sufficiently small Co which only depends on C1 below. Moreover, all the constants C, i 2 3 in the following depend only on and ej. (ii) The stepsize satisfies
01 o7 S [F.F. Xxlls S c2 oz for some small numerical constants
0.01 and all t 2 O. (iii) kr+
< 02 <
k. RDD holds for {A,, s: with 8 /VV and a function vè E
+ 2 V
Define T caK² log k. Then, we have sublinear convergence in the sense that for any 2 0,
| -xall S CBO
K
x3 +
Moreover, if = r, then under the same set of condition, we have convergence at a linear rate
FETT X11l C60, (1 CT ) 120.
x
We sketch the high-level ideas of the proof Section 3.3, and postpone all the details to Appendix A.
In the last, we show that the conditions of Theorem 3.1 can be met with our model assumptions in Section 2, our initialization scheme in Section 3.4, and our stepsize choice (3.2), with sufficient number of samples yn and proper sparsity level p of the corruption Define O. to be the left quantile of the folded normal distribution Z). Z ~ (O, 1), i.c., IP(Z < 02) = e. The quantile function is used for the stepsize condition. For both RC and AC models, now state results as follows.
Theorem 3.2. Suppose under Model 1, we have m 2 x (log + log k) logd d and p < <PR for some universal constants C1 C2. And under Model 2. we have fixed p < 3 and m cadk3 x2 2log K log k)) log d for some C3 > 0 depending only on p. Then under both models, with exp(-(pmn + +d) for some universal constants ca cs.
62
probability at least 1 1 C4 exp(-ee g(ggz xx0 our subgradient method (3.1) with the initialization in Algorithm 1, and the adaptive stepsize choice (3.2) with C, E 0.5-p of
Eq
on dx with some universal co, C7 < 0.001. converges as stated
0.5-p
in Theorem 3.1.
The proof follows by verifying the three conditions in Theorem 3.1. The initialization scheme is verified in Proposition 3.3 in Section 3.4. The RDPP is verified in Proposition 2.2. We defer the verification of the validity of our stepsize rule (3.2) to Appendix D.
Note that the initialization condition in Theorem 3.1 is weaker than those in the literature [4. (4,5), which requires F. to be close to Xg. Instead, we allow constant multiple e in the initialization condition (3.3). This means we only require Fo F. to be accurate in the direction of X2 and allows a
6

---

crude estimate of the scale || This in turn allows to have p close to ! in Theorem 3.2 for 2 the RC Model. 10 If we require p S - in both models, which is assumed in [4,5], then the sample complexity can be improved to O D(dk* n (log K + log k) log d) and the convergence rate can also be improved. See Appendix G for more details.
kyr
3.3 A sketch of analysis for Theorem 3.1
In the following, we briefly sketch the high-level ideas of the proof for Theorem 3.1.
Closeness of the subgradient dynamics to its smooth counterpart. To get the main intuition
of our analysis, for simplicity let us first consider the noiseless case, i.e. 5; = 0 for all i. Now the objective fF) in (1.2) has expectation Ef(F) = 1 (A FFT -X:)|
1 |FFT X211F.
Hence, when minimizing this expected loss, the subgradient update at Fe with Fi * X3 becomes
Fi, t 0, 1,2, 2 (F.F - X.)
|F-F F. Th π |F,FF X2l1F Fo Rdxk, Fet1 F; T/: (F)(F)
If we always have 1):
2 y F.FFFFTT X,Ilı for some 7 > O, then the above itcration scheme
becomes the gradient descent for the smooth problem min |FFT Xglle
Fo Rdxk;
FI-1= Fi -2-- (F.F. Xx,) F., t= 1,2,
(3.4)
Recent work [15] showed that when no corruption presents, the gradient decent dynamic (3.4) converges to the exact rank solution in the rank overspecified setting. Thus, under the robustness setting, our major intuition of stepsize design for the subgradient methods is to ensure that subgradient dynamics (3.1) for finite samples mimic the gradient descent dynamic (3.4). To show this, we need NeSt in (3.1) to approximate FF, X₂) F, up to some multiplicative constant y, which is indeed ensured by the conditions (ii) and (iii) in Theorem 3.1. Detailed analysis appears in Appendix A.
Three-stage analysis of the subgradient dynamies. However, recall our condition (i) in Theo- rem 3.1 only ensures that the initial Fd is close to the ground truth X₁ up to some constant scaling factor. Thus, different from the analysis for matrix sensing with no coruptiinn [15]. here need to deal with the issuc where the initial | X2 ll could be quite large. To dcal with this issuc, we introduce extra technicalities by decomposing the iterate Fr into two parts, and conduct stree-stage analysis of the iterates. More specifically, since X2 is rank r and PSD, let its SVD be
x; UU
v
D3s
0 0
JU,,
U
V)",
(3.5)
where D3 E Rr U Rdxr and V (d-()-)) Here U and V are orthonormal matrices and complement to each other, i.e., U V = 0. Thus, for any F, E Rdxr, we can always decompose it
F. US, + VT,,
(3.6)
where S. U.FFF Rrxk stands for the signal term and T; VTF, E R(d-r)x stands for an сггог term. Based on this, we show the following (we refer to Appendix A for the details.):
We characterize the evolution of the smallest singular value (St),, showing that it will increase above certain threshold, so that F.F." is moving closer to the scaling of Xg Stage 2. We show that the quantity Q, max [|S Di [| decrease geometrically. In the analysis, for first two stages, T, may not decrease, and the first two stages consist of the burn-in phase T.
Stage 1.
Stage 3. We control E, = m - -Dyl S.T."
| ||}, showing that E, + 0 at rate O(1/t) due to the slower convergence of [TT, This further implies that ||F.P.T - X,ll converges to 0 at a sublinear rate (1t)). For the case & = r, the convergence speeds up to linear due to a better control of |T;T; ||-
3.4 Initialization schemes
The work [13] actually allows for p to be close to 1 under a simpler RC model. The main reason is that they assume the scale information |||a|lr is known a priori and their guarantee is only approximate FF X² ||F S 8 log ö for a rank-1 Xg. However, estimating ||X lix accurately requires p to be close to 0.

---

generate the sensing matrices A Am to be GOE Algorithm 1: Spectral Initialization
Input: the sensing matrix {Ai ) and observations {yr
Form D m Σx= (gg and compute the top-k eigenpairs D.
Collect the eigenvectors as U E [R and the eigenvalues as the diagonals of E R Compute B = U ) where Σ, is the nonnegative part of Σ. Compuie the median { (11)) } 1), and set 7 = E3 (f //L22/003))
Output: Fo V.B.
In this section, we introduce a spectral initialization method as presented in Algorithm 1. The main intuition is that the cooked up matrix D in Algorithm has expectation E(D) xxx) so
that the obtained factor BB from D should be pointed to the same direction as X; up to a scaling. We then multiply B by suitable quantity to produce an initialization Fo on the same scale X, More specifically, given that 0g is the left quantile of folded normal distribution introduced before Theorem 3.2, we state our result as follows.
Proposition 3.3. Let Fo be the output of Algorithm I. Fix constant co < 0.1. For model with S En 2F where on depends only on co, there exist constants 01, C2 cn depending only on co such that whenever m 2 c,drk (log K + llo dogr) (ogr)ogge d, we have
|FFoFo - c² X1ll S CO0//K.
(3.7)
exp( - (prm + d)), where e* = 1. For Model 2 with a fixed p < 0.5 and m 2 dddr (log k + log r log d. Then (3.7) also holds for c* e
with probability (w.p.) at least 02 exp(
Gam k'r
IV 2
90.5-2
_ w.p. at least es exp(
cam
where the constants Ca, C5,0%, Co "
depend only on and co.
The details of the proof can be found in Appendix E. It should be noted in (3.7) that our guar- antec ensures Fo close to X₁ up to a scalar multiple c*, instead of the usual guarantees on Fo XtIl []. If S 1. we obtain |FFF - X2ll S coa, in Proposition E.2 and the Vre sample complexity m improves drx² log d(log K + logr).
4 Experiments
In this section, we provide numerical evidence to verify our thcoretical discoveries on robust matrix recovery in the rank overspecified regime. First, for robust low-rank matrix recovery, Section 4. I shows that the subgradient method with proposed diminishing stepsizes can (i) exactly recover the underlying low-rank matrix from its linear measurements even in the presence of corruptions and the rank is overspecified, and (ii) prevent overfitting and produce high-quality solution even in the highly wee-paaraeteriize regime & = d. Furthermore, we apply the strategy of diminishing stepsizes for robust image recovery with DIP [14, 16, 32] in Section 4.2, demonstrating its effectiveness in alleviating overfitting. The experiments are conducted with Matlab 2018a and Google Colab [33].
4.1 Robust recovery of low-rank matrices
Data generation and experiment setup. For any given d and r, we generate the ground truth X; F.F.T with entries of F. E RRdx i..dd from standard normal distribution, and then normalize X; such that || 1. Similarly,
matrices discussed in Section 2.1. For any given corruption ratio p. we generate the corruption vector Rm according to the AC model, by randomly selecting [pm] locations to be nonzero and generating those entries from a i.i.d. pero-mean Gaussian distribution with variance 100. We then generate the measurement according (1.1), i.e., y/ (Ai, X₁) + 8,, 1,..., m, and we set n 100, 0.2, and m 10nr. We run the subgradient methods for 1 iterations using the following different stepsizes: (i) the constant stepsize 7) = 0.1 for all t > 0, (ti) sublinear diminishing stepsizes Yi no/t, (iti) geometrically diminishing stepsizes π 770 0.9*, (iv)
11 For the two diminising stepsizes, we set 710 when r or 2r, and np = when &

---

10
10'
16
Gromotric
Sublincac
10
100
Propased
HAP Xalle
Fotrak
Geomendo
10
-Sukinner
Propused
10""
Constant Geoeettic Subliacar
P-lyak
Propused
10 15
600
800
10
200
800
1000
d Figure I: Convergence the subgradient method (3.1) with different stepsize rules in regimes of (a) exact-paramelerization l = r. (b) rank overspecication = 2r, and (c) over-parameterization = d. We use the following stepsizes: constant stepsizes /): !/o, geometric diminishing stepsizes rjo 0.9", sublinear diminishing stepsizes T). T/o /t. the proposed stepsizes (3 2). and the Polyaks's stepsize.
r
(b)
the proposed stepsizes (3.2) with Cn 2 and (v) the Polyak stepsize rule [34] which is given by f( where /* is the optimal value of (1.2) and 9: is the subgradient in (3.1). We use the 9:
"):
spectral initialization illustrated Section 3.4 to generate the initialization Fo-
Observations from the experimental results. We run the subgradient method with different stepsize rules and different rank & = т, 2r, and d, and compute the reconstruction error F|,FF, F. Xalle p for the output of the algorithms. From Figure and Figure 2a, our observations are the follows.
Exact rank case k = As shown in Figure la, we can see that (i) the subgradient method with constant stepsizes does not converge to the target matrix, (ii) using sublinear diminishing stepsizes Polyak!2 stepsizes converge at lincar ralc, consistent with the obscrvation in [5]. and (iv) the proposed stepsize rule also leads to convergence the ground-truth at a linear rate, which is consistent with Theorem I. Overspecified rank case = 2r. As shown in Figure 2b, the subgradient method with any stepsize rule converges most a sublinear rate, while constant geometrically diminishing stepsizes result in poor solution accuracy. The proposed stepsize rule achieves on par convergence performance with the sublinear stepsize rule, which also demonstrates our Theorem 3.1 the sublinear convergence in the rank overspecified setting. As shown in Figure 2a, the proposed strategy (3.2) gives stepsizes similar to Polyak's. and thus both resulting better). However, the Polyak stepsize rule requires knowing the optimal value of the objective function, which is usually unknown a prior in practice.
results in sublinear convergence rate, (iii) geometrically diminishing
similar convergence rate (or the Polyak's 's slightly
Overparameterized case k = d. The results are shown in Figure Ic. In this case, inspired by [13,27], 27]. we use an alternative tiny initialization Fo by drawing its entries from i.i.d. zero-mean Gaussian distribution with standard deviation 10-7 We first note that the constant stepsize rule results overfitting. In contrast, the proposed diminishing stepsizes can prevent overfitting issues and find very high-quality solution. We conjecture this is due to certain implicit regularization effects [14, 26,27 and we leave thorough theoretical analysis as future work.
4.2 Robust recovery of natural images with deep image prior
Finally, we conduct an exploratory experiment on robust image recovery with DIP [14, 16). Here, the goal is to recover natural image X, from its corrupted measurement y X; + s, where s denotes noise corruptions. To achieve this, the DIP fits the observation by a highly overparameterized deep l= o(+) by solving mine lyy (())lo [37], where θ denotes network parameters and the norm || Ill can be either & or & depending on the type of noises. As shown in [14, 16, 6,32], by learning the parameters O, the network first reveals the underlying clear image and then overfits due to overparameterization, so that in many cases early stopping is crucially needed for its success.
In contrast to the constant stepsize rule, here we show a surprising result that, for sparse corruptions, optimizing robust loss using the subgradient method with diminishing stepsize rule does not
12 As guaranteed by Theorem 2.3, in this case, the optimal value f is achicved at Ft.
We omit the performance of the Polyak stepsizes since in this case the optimal value f is not casy compute; it may be achieved at F; due to the overfitting issue. Our experiments indicate that the Polyak stepsizes do not perform well when computed by setting optimal value as either 0 or the value at Fg. the same U-shaped architecture with skip connec-
"Following [16] (license obtained from [35]), tions, each layer containing convolution, nonlinear LeakyReLU and batch normalization units, Kaiming initialization for network parameters, and Adam optimizer [36]. We set the network width as 192 as used [14].

---

10
30
Step size
10
PSNR(aR)
25-
Proposed, Polyuk, =
15-diminichiig
10
10
Polyak, ==
Proposed,
20-
716 couscam
Pegoem-liminiting
Peppenecumttaant
Leme-lminnihing
10-15
Leme-onnian
15
200
400
600
800
1000
1000
2000
3000
4000
5000
Iteration 1
lleration
(a)
(b)
Figure 2: Figure 2a shows the comparison of the proposed stepsize in (3.2) and the Polyak stepsize in the regimes of the nacttparaaeterization learning curves for robust image recovery with DIP on different test images with 50% salt and pepper noise. Here, we compare the constant and diminishing stepsize rules for DIP.
r and the rank overspecification
2r. Figure shows the
overfit. In particular, we consider a sparse corruption by impulse salt-and- wanudeepperr noise, and solve the robust DIP problem mine lly - ( using the subgradient method with diminishing stepsize rule. We test the performance using three images, "F16", "Peppers" and "Lena" from a standard dataset [38], where contaminate the image with salt-and-pepper noise by randomly replacing 50% pixels with either or (each happens with 50% probability). We compare the subgradient method with constant stepsize 0.01 (or learning rate) and diminishing stepsize (we an initial stepsize 0.05 which is then scaled by 0.96 for every 50 iterations). As shown in ??, the subgradient method with constant stepsize eventually overfits that requires early stopping. In comparison, oplimization with diminishing stepsize prevents overfitting in the sense that the performance continues to improve as training proceeds, and achieves on par performance with that of constant stepsizes when the learning is early stopped at the optimal PSNR. However, early stopping is not casy to implement in practice without knowing the clean image a priori.
Discussion
In this work, we designed and analyzed a subgradient method for the robust matrix recovery problem under the rank overspecified setting, showing that it converges to the exact solution with sublinear rate. Based on our results, there are several directions worth further investigation.
Better sample complexity. Our exact recovery result in Theorem 3 2 requires Ödk-") many samples. When the rank is exactly specified (k: = r), for factor approaches with corrupted measurements, the best sample complexity result is (dr²2) [2, 4]. Hence there is an extra k factor in the rank overspecified setting.
possible to improve the dependence on k?? In particular, we think the worse dependence comes from the 5 dependence of the sample complexity of RDPP in Proposition 2.2. More specifically, the Cauchy-Schwart inequality we applied (C.31) might make the dependence on ó not tight.
Implicit regularization. As explored and demonstrated in our experiments in Section 4, our stepsize choice combined with random initialization recovers X; with high accuracy, even if & > and the number of samples m is way less than the degree of freedom (i.e., m (dr)). Theoretically justifying this phenomenon in the overparameterized regime would be of great interest.
Other sensing matrix. In this work, we assume A, to be a GOE matrix. This specific assumption the measurement matrix still seems to be restrictive. Generalizing our results more generic sensing matrices would also be an interesting future direction.
Rectangular matrices. In this work, we utilize the fact that X, PSD, and optimize over factor F. This is consistent with much existing analysis with rank overspecification [13, 15, 27). For rectangular X₁, need optimize over two factors U, V. How combine the analysis here with an extra regularization |UU VVT in the objective is another interesting direction to pursue.
A Akknowledgement
L. Ding would like to thank Jiacheng Zhuo for inspiring discussions. Chen partially supported by NSF grant CCF-1704828 and CAREER Award CCF-2047910. Z. Zhu is partially supported by NSF grants CCF-2008460 and CCF-2106881.
10

---

References
[1] Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1337, 2011.
[2] Yuanxin Li, Yue Sun, and Yuejie Chi. Low-rank positive semidefinite malrix recovery from comrupted rank-one measurements. IEEE Transactions on Signal Processing, 65(2):397-408, 2016.
[3] Markus Rambach, Mahdi Qaryan, Michael Kewming, Christopher Ferrie, Andrew G White, and Jacquiline Romero. Robust and efficient high dimensional quantum state tomography. Physical Review Letters, 126(10):100402, 2021.
[4] Yuanxin Li, Yuejie Chi. Huishuai Zhang, and Yinghin Liang. Non-couvex low-rank matrix recovery with arbitrary outliers median -trnnatet gradient descent. Information and Inference: A Journal of the IMA, 9(2):299-33) 325, 2020.
[5] Xiao Li, Zhibui Zhu, Anthony Man-Cho So, and Rene Vidal. Nonconvex robust low-rank matrix recovery. SIAM Journal on Optimization, 3061)6660-666, 2020.
[6] Vasileios Charisopoulos, Yudong Chen, Damek Davis, Mateo Díaz, Lijun Ding, and Dmitriy Drusvy- atskiy. Low rank matrix recovery with composite optimization: good conditioning and rapid convergence. Foundations of Computational Mathematics, pages 1-89, 2021.
[7] Tian Tong, Cong Ma, and Yuejic Chi. Low-rank matrix recovery with scaled subgradient methods: Fast and robust convergence without the condition number. IEEE Transactions on Signal Processing, 2021.
[8] Roman Vershynin. Introduction to the non-asympiotic analysis of random matrices. arXiv preprint 10xiv 2010.
[9] Joel A Tropp User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389-434, 2012.
[10] Roman Vershynin. High-ddimensooal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[11] Martin Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[12] John C Duchi and Feng Ruan. Solving (most) of set of quadratic equalities: Composite optimization for robust phase retrieval. Information and Inference: A Journal of the IMA, -3)4411-529, 2019.
[13] Jianhao Ma and Salar Fattahi. Implicit regularization of sub-gradient method in robust matrix recovery: Don't tt be afraid of outliers. arXiv preprint 21t.::2002.022999 2021.
[14] Chong You, Zhihui Zhu, Qing Qu. and Yi Ma. Robust recovery via implicit bias of discrepant learning rates for double over-paramettrriztioon In Advances in Neural Information Processing Systems, 2020.
[15] Jiacheng Zhuo, Jeongyeol Kwon, Nhat Ho, and Constantine Caramanis. On the computational and statistical complexity of over-parameterrized matrix sensing, arXiv preprint arXiv:2102 02756, 2021.
[16] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Deep image prior. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 9446-9454, 2018.
[17] Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-ranke solutions of linear malrix equations via nuclear norm minimization. SIAM review, 52(3):471-501, 2010.
[18] Yudong Chen, Ali Jalali, Sujay Sanghavi, and Constantine Caramanis. Low-rank matrix recovery from errors and erasures. IEEE Transactions on Information Theory, 59(7):4324 4337, 2013.
[19] Guangean Liu and Wayne Zhang. Recovery of future data via convolution nuclear norm minimization. arXiv preprint arXiv: arXiv:1909 03889, 2019.
[20] Ruoyu Sun and Zhi-Quan Luo. Guarantecd matrix completion via non-convex factorization. IEEE Transactions on Information Theory, 62(11):6535-677 2016.
[21] Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srehro. Global optimality of local search for low rank matrix recovery. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 3880-3888, 2016.
[22] Rong Ge. Chi Jin, and Yi Zheng, No spurious local minima in nonconvex low rank problems: A unified geometric analysis. International Conference on Machine Learning, pages 1233-1242. PMLR, 2017,
[23] Zhihui Zhu, Qiuwei Li, Goneguo Tang, and Michael B Wakin. Global optimality in low-rank rank matrix optimization. IEEE Transactions Signal Processing, 661133336,3,662, 2018.
[24] Yuejic Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing, 67(20):5239-526) 2019.
[25] Yuqian Zhang, Qing Qu, and John Wright. From symmetry to geometry: Tractable nonconvex problems. arXiv preprint 2007 06753, 2020.
11

---

[26] Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Implicit regularization in matrix factorization. In 2018 Information Theory and Applications Workshop (ITA), pages 1-10. IEEE, 2018.
[27] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-paramelerized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theary, pages 2-47.
PMLR, 2018.
[28] James V Burke and Michael C Ferris. Weak sharp minima in mathematical programming. SIAM Journal Control and Optimization, (1(5):334011333 1993.
[29] Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan. Bridging convex and nonconvex optimization in robust pea: Noise, outliers, and missing data, arXiv preprint arXiv:2001 05484, 2020.
[30] Francis H Clarke, Yuri Ledyaev, Ronald Stern, and Peter Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science & Business Media, 2008.
[31] Jianhao Ma and Salar Fattahi. Sign-rip: A robust restricted isometry property for low-rank matrix recovery. arXiv preprint arXiv:2102 02969v3, 2021.
[32] Reinhard Heckel and Mahdi Soltanolkotabi. Denoising and regularization via exploiting the structural bias of convolutional generators. arXiv preprint arXiv:1910.144 14634, 2019.
[33] Ekaba Bisong. Google colaboratory. In Building Machine Learning and Deep Learning Models on Google Cloud Platform, pages 59-64. Springer, 2019.
[34] Boris Teodorovich Polyak. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics, 94 29, 1969.
[35] https://githuu com/Dmitrylllyeeem tty.o/oo/e/e//eeepppppoopp image- prijor/blob/aastrrrICCCSS.
[36] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 2014.
[37] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer-assister intervention, pages 234-241. Springer, 2015.
[38] http://www.cs. tut ftt//ii/////////////////o//ooo// /otff////FBBBBB BBBIeBBMD//i1 mwaD//indx..o feem@rref_reee trefteeutereeut/....
[39] Emmanuel Candes and Yaniv Plan. Tight oracle inequalities for low rank matrix recovery from a minimal number of noisy random measurements. IEEE Transactions Information Theory, 57(4):23342255 2359, 2011.
12


Reviews:
[{"review_id": "yE73LB0JPeh", "reviewer": "Reviewer_x1C7", "summary": "The paper considers the problem of recovering a rank $r$ matrix $X$ in $\\mathbb{R}^{d\\times d}$ under possibly corrupted linear measurements. The paper studies the non-convex formulation, first considered by [Jianhao Ma, 2021], that uses a overspecified factorization of the unknown matrix and employs an $\\ell_1$ minimization. The goal is to recover $X$ by recovering a matrix $F\\in \\mathbb{R}^{d\\times k}$ such that $X = FF^\\intercal$, with $k$ possibly bigger than $r$. The authors introduce a Restricted Direction Preserving Property (RDPP), which describes the alignment of the sub-differential of the $\\ell_1$ loss function with gradient of the expectation of the loss function. The authors show that RDPP holds for random measurements with certain corruption models and use this to show that the low-rank matrix can be exactly recovered with high probability using a sub-gradient descent method that using diminishing step-size. The result requires number of measurements on the order of $O(dk^3)$, up to log factors and convergence is linear in the case $k = r$. Bulk of the paper rests on the theoretical exposition.  I did not go through the theoretical proofs from the supplementary material in detail, however the proof sketch from the main paper provides sufficient intuition.\n", "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": "1. It is not immediately clear, by reading the introduction section, that the corruptions considered in the paper are sparse. In line 32, the authors state \"in many cases corruptions $s_i$ are sparse\" which falsely implies to the readers that corruptions considered in the paper could be dense and the result presented applies to this general case. Sparsity of corruptions should be made clear before stating the contributions and to motivate the $\\ell_1$ formulation presented in the paper.\n\n2. In contribution (exact recovery with rank overspecification) and in abstract, randomness (Gaussian) of the measurement is not stated. This falsely leads the readers to believe that the result applies to general measurements (for example, subsampled Fourier measurements). To my knowledge, the measurements considered in the paper is random. \n\n3. The measurement matrices considered in the paper are generated from Gaussian Orthogonal Ensemble. How practical is this assumption? This is more restrictive than standard Gaussian measurement. Does a similar recovery result hold of standard Gaussian measurement (with entries i.i.d. $\\mathcal{N}(0,1)$?\n\n4. In line 135, it is stated that \"generic sensing matrices satisfy RDPP\". What are the class of matrices that satisfy RDPP? Can the result be extended to more realistic scenarios where measurements don't follow this property?\n\n5. The subgradient algorithm studied in the paper is initialized using a spectral initialization, which generals involves computing the SVD of a matrix. This problem was reduced to computing eigenvalues/eigenvectors of a matrix because the measurement matrices were symmetric. In Line 60-61, the authors state that their algorithm \"does not require SVD\" which seems to be not entirely true (at least the initialization requires SVD). This should be made clear.\n\n6. The sample complexity required for successful recovery is on the order of $O(dk^3)$, up to log factors, which is not optimal. This should be discussed in the paper, providing comparison to other related works.\n\n7. There are some words missing or unclear phrasing in Line 63 and Line 147.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the paper is discussed in the concluding section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "y12Uhdrx1KO", "reviewer": "Reviewer_skcZ", "summary": "This paper studies the problem of recovering a positive semi-definite matrix from a set of corrupted measurements, under the setup that the rank of the target matrix is unknown. Based on some Gaussian assumptions on the sensing matrices and the corruption model, the authors prove that the nonconvex program (1.2) equipped with a subgradient algorithm can achieve exact recovery. The key to accomplish the proof is a new regularity condition called Restricted Direction Preserving Property (RDPP).", "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": "1. Recently, tremendous attention has been attracted by the theoretical side of non-convex optimization based robust low-rank matrix recovery. Though I don't understand why that happens, this submission truly makes some progress in the direction: they resolve the issues raised by over-specified rank on the target matrix.   \n\n2. The paper is well-written. In fact, this paper is an improved version of another submission entitled \"Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery\", with the same problem space and similar techniques. For the Sign-RIP paper, I have concerns about the rationality of its claims and justifications. The statements and claims in this submission are adequate, thereby I vote for acceptance.\n\n3. The importance of low-rank matrix recovery could be made more convincing. Besides the well-known applications such as image analysis, I have seen some recent papers that apply recovery methodology to the filed of time series forecasting, e.g., \"Recovery of Future Data via Convolution Nuclear Norm Minimization\", \"Time Series Forecasting via Learning Convolutionally Low-Rank Models\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The assumption on the sensing matries is very restrictive, and the authors have adequately addressed this in Section 5. ", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "about 1 hours"}, "extra_text": {}}, {"review_id": "YkZw_a0DIcd", "reviewer": "Reviewer_z2Cg", "summary": "The authors study the problem of low-rank P.S.D matrix recovery in the presence of outliers. In particular, the paper studies a subgradient method to solve the above problem. The authors firstly define the notion of restricted direction preserving property (and show that this holds for the usual Gaussian measurements) and then propose a different rule for diminishing step size. With these conditions, the paper shows that even in the case of rank-overspecification, the method converges (linearly in certain settings) to the ground truth. The authors also perform some numerical experiments that corroborate the claims. ", "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 I think this is a fantastic paper with very impressive results. To the best of my knowledge, the results claimed in the paper are very novel in the area, and are a great addition to the literature on low-rank matrix recovery. The problem studied is an important one that has several applications, and a rich literature. I have a few minor comments/questions to the authors that I list below:\n\n- The particular problem is for the low-rank matrix recovery problem, if one were interested in low-rank matrix completion, can the authors comment something about the RDPP for say random bernoulli/uniform random sampling sort of matrices? \n\n- The wording of the two settings on $s_i$'s (Def.  Model1, 2) is a bit confusing and can be improved to highlight the differences better \n\n- In Def 2.1, if $\\psi(X)$ is just a scalar, why use a function notation at all? \n\n- There are some discrepancies in $D(X)$ and $\\mathcal{D}(X)$ throughout the paper.\n\n- Are the entries in Table 2 based on a Monte-Carlo averaging? Also table 2 seems to contradict the results of [13] which claim (in an order notation at least) that Gaussians satisfy sign-RIP? I believe including a few settings where sign-RIP holds would improve the exposition of the paper. \n\n- I also think that given the close connection with sign-RIP a more detailed discussion (the paragraph following Table 2) regarding these properties is warranted. \n\n- In the expectation discussion below (3.2), what is the expectation taken over? because there are potentially several sources of randomness. \n\n- this is just a question out of curiosity: so since there is some implicit regularization that is happening, would the authors be able to comment on how the stable rank of $F_t F_t^\\top$ evolves over iterations? \n", "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": "2"}, "extra_text": {}}, {"review_id": "SvmClaKLjoM", "reviewer": "Reviewer_aMMW", "summary": "This work studies the problem of recovering a low-rank matrix from grossly corrupted linear measurements. Specifically, the authors analyze an $\\ell_1$ empirical risk minimization problem by parameterizing the unknown matrix via the factorization $FF^T$, where the inner dimension of $FF^T$ can be over-specified (i.e., larger than the ground truth rank $r$). The authors show that rigorous recovery guarantees are possible in both the exact specification and over-specified case with a sufficiently small amount of corruption. Subgradient descent with proper initialization and an adaptive step-size can exactly recover the low-rank matrix at a sublinear rate and linear rate in the over-specified and exactly specified case, respectively. To prove this, the authors introduce a regularity condition, called the Restricted Direction Preserving Property (RDPP), and show that satisfaction of this condition is sufficient for subgradient descent to succeed, as this condition essentially states that subgradients behave like their expectations. Experiments show that the proposed algorithm works comparably well to other descent methods with decaying step-size schedules and also that decaying step-sizes could potentially help the Deep Image Prior (DIP) from overfitting to sparse corruptions.", "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": "# Originality\n\nThe proposed work provides a new sufficient condition on the measurement matrix and corruption statistics that is a variant of previous work on robust matrix sensing. While the RDPP is similar cosmetically to previous work, the novelty lies in the result that it is shown to be sufficient for local convergence of a subgradient descent algorithm with adaptive step sizes. Moreover, this convergence holds for general rank $r$ ground truth matrices and rank over-specification $k \\geqslant r$. \n\n# Quality\n \n- Strengths: - The work is well-written and easy to follow. - The results hold for general rank $r$ and any amount of over-specification $k \\geqslant r$. - The proposed algorithm can exactly recover the underlying low-rank matrix in the presence of sparse corruptions, and convergence rates on the algorithm are shown.\n\n- Weaknesses: - The results require spectral initialization, although the initial error bound in the present work is less stringent in previous works. Experimentally, was the spectral initialization scheme necessary for subGD with the proposed step sizes to converge? The case $k = d$ used random initialization with small norm, but the over-specified and exact rank case all used spectral initialization. - The overall sample complexity of the convergence results appears off by a large factor of $k^2$. Could the authors comment on where this bottleneck arises and where the difficulty lies? This may be helpful for the reader to know where potential improvements could be made. It appears this factor is due to the sample complexity required for the RDPP, as it scales like $\\delta^{-4}$, and the theory requires $\\delta \\leqslant 1/\\sqrt{k}$.\n\n# Clarity\n\nI found the paper easy to follow, and gained a good amount of intuition from the proof sketches and discussion of results. \n\n- Typos: pg 1 line 13 “adversary sparse” -> “adversarial sparse”, pg 3 line 112 “facterized” -> “factorized”, pg 3 line 117 “dynamic” -> “dynamics”, pg 5 line 164 is missing a period\n\nOther comments:\n\n- I believe that the proof of Proposition 2.2 is in Appendix C instead of D.\n- Eq (2.1) should have $y_i$ instead of $s_i$.\n- The results shown for DIP are certainly interesting, but the proposed method wasn’t used in this setting (namely the adaptive step sizes). Thus the sentence on pg 2 line 57-58 may be misleading (instead one could simply note robustness to overfitting for DIP is shown with decaying step sizes). Along these lines, is there an analogous adaptive step-size rule that could be used for denoising with sparse corruptions for the DIP (say, simply taking the median of the measurements)?\n- The authors commented on how analyzing other measurement matrices would be an interesting avenue for future work. Along similar lines, could the RDPP (or a variant thereof) potentially have applications to other inverse problems as well?\n\n# Significance\n\nThe present work adds an interesting contribution to providing rigorous guarantees for the over-specified matrix sensing setting. This setting is important as, in practice, one would rarely know the exact rank of the ground-truth matrix. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As the work is theoretical in nature, there are no foreseeable societal impacts. Some limitations on the theory are discussed near the end, and one I would add here is the sub-optimal sample complexity scaling.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is a consensus among the reviewers that this paper presents significant results of interest to the conference. 
Decision: Accept (Poster)