RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees
Authors: Eilon Vaknin Laufer
Boaz Nadler
Venue: NeurIPS 2025 poster ()
Keywords: Robust Matrix Completion
Outlier Detection
Gauss-Newton Method
Matrix Factorization
Robust PCA
Matrix Completion
Primary area: general_machine_learning
TL;DR: A novel robust matrix completion method that overcomes limitations of existing schemes, accompanied by recovery guarantees

Abstract: Recovering a low rank matrix from a subset of its entries, 
some of which may be corrupted, is known as the robust matrix completion (RMC) problem.
Existing RMC methods have  several limitations: they require a relatively large number of observed entries; 
they may fail under overparametrization, when their assumed rank is higher than the correct one;
and many of them fail to recover even mildly ill-conditioned matrices.
In this paper we propose a novel RMC method, denoted $\texttt{RGNMR}$, which overcomes these limitations. 
$\texttt{RGNMR}$ is a simple factorization-based iterative algorithm, which combines a Gauss–Newton linearization with removal of entries suspected to be outliers.
On the theoretical front, we prove that under suitable assumptions, 
$\texttt{RGNMR}$ is guaranteed exact recovery of the underlying low rank matrix.
Our theoretical results improve upon the best currently known for factorization-based methods. 
On the empirical front, 
we show via several simulations
the advantages of $\texttt{RGNMR}$ over existing RMC methods, and in particular its ability to handle a small number of observed entries, overparameterization of the rank and ill-conditioned matrices.
In addition, we propose a novel scheme for  estimating the number of corrupted entries.
This scheme may be used by other RMC methods that require as input the number of corrupted entries.

RGNMR:
A Gauss-Newton method for robust matrix completion with theoretical guarantees
Eilon Vaknin Laufer Weizmann Institute of Science eilon. wwwninwveizaann ac.
Boaz Nadler
Weizmann Institute of Science boaz. nadl er@weizmann ac.
Abstract
Recovering low rank matrix from subset of its entries, some of which may be corrupted, known as the robust matrix completion (RMC) problem. Existing RMC methods have several limitations: they require relatively large number of observed entries; they may fail under overparametrization, when their assumed rank is higher than the correct one; and many of them fail to recover ill-conditioned matrices. In this paper we propose a novel RMC method, denoted RGNMR, which overcomes these limitations. RGNMR is simple factorization- based iterative algorithm, which combines Gauss-New of entries suspected to be outliers. On the theoretical front, prove that under suitable assumptions, RGNMR is guaranteed exact recovery of the underlying low rank matrix. Our theoretical results improve upon the best currently known for factorization-batt methods. On the empirical front, we show via several simu- lations the advantages of RGNMR its ability to handle a small number of observed entries, overparameterization the rank and ill-conditioned matrices. addition, we propose novel scheme for estimating the number of corrupted entries. This scheme may be used by other RMC methods that require input the number of corrupted entries.
mildly
linearization with removal
existing RMC methods, and in particular
Introduction
Low-rank matrices play a fundamental role in multiple scientific disciplines. As reviewed in Dav enport and Romberg (2016), in various applications, there is need to recover low rank matrix from only a subset its entries. Examples include recommendation systems (Bennett et al. 2007). various problems in computer vision (Kennedy al.) [016 Tulyakov et al., 2016 Miao and Kou 2021), in sensor networks (Wu et al. (025) and in single-cel data analysis (Lejun et al. (2025) A key challenge in these and other applications is that some of the observed entries may be arbitrarily corrupted outliers.
In this work, consider the robust matrix completion (RMC) problem, of recovering low rank matrix from a subset of its entries, out which a few are outliers. Formally, let E "R X be a matrix with decomposition X L* S", where L is rank matrix and S* is sparse corruption matrix whose few non-zero entries are arbitrary. The RMC problem is to recover L from the subset {X+s (i, L), where Ω C [n]] [mz] denotes the subset of observed entries in X.
Related work. Over the past decade, the RMC problem was studied from both mathematical, computational and statistical perspectives. On the computational front, several RMC algorithms have been proposed. general, to solve the RMC problem the following optimization issues need to be addressed: (i) either promote low rank solution or strictly enforce it: and (ii) suppress the potentially detrimental effect of the outliers, whose locations are a-priori unknown.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

RMC AOP + RPCC-OD - HOAT
RMC + AOP + RPCA-GD + HOAT
HUB RRMC RGNMR-BS RGNMR
+-HUB RRMC RGNMR-BS R-RNMRR
10
failure probability
14
median error
0.8
10.5
0.6
0.4
10
10
<2
oversampling ratio
oversampling ratio
Figure 1: Performance of RMC methods function of the number of observed entries measured by the oversampling ratio r-(n1-ng-- where r (n1 + n22 r) is the number of degrees of freedom of a rank r matrix. (left) Median RMSE; (right) Failure probability (#1.96 SE). The underlying matrix L has condition number K = 2. The corruption fraction is 5%.
Regarding the first issue, one approach is incorporate into the optimization objective low-rank promoting penalty such as the nuclear norm (Candès et al. 2011 Nie et al., 2012 Klopp et al. 2017] Wong and Lee 2017: Chen al., [202]] Under suitable assumptions on the matrices L S* and on the set S2, these methods enjoy strong theoretical guarantees. However, these schemes are in general computationally slow, and do not scale well large matrices. different approach is to strictly enforce a rank solution. This can be done by optimization over the manifold of rank matrices (Yan et al. 2013) Cambier and Absil 2016), or by projecting matrices onto it. Several works factorize the target matrix as L -= UVT and optimize over the two factor matrices U R and
Ve _ (Yi et al. 2016 Lin et al. 2017 Zeng and So 2017 Huang et al. 2021 Wang et al. 2023). The resulting problem involves only (z4 + n22)r variables instead of the
n2 entries in L.
Factorization based methods are thus in general more scalable and able to handle larger matrices.
Regarding the second issue, some works attenuate the effect of the outliers either by estimating the
locations of the corrupted entries and removing them, by estimating their values S.j for (i.j) E Z Yan et al. 2013 Cherapanamjeri et al. 2017 Huang et al. [021] Chen et al., 2021 Wang and Weil
2024). Other works mitigate the influence outliers by using a robust norm on the difference X L
in the objective function (Nie et al. 2012. Cambier and Absil 2016 Lin et al. 2017 Zhao et al.
2016 Zeng and So. 2017 Wang et al.) 2023).
Limitations of existing RMC methods. Despite extensive research on the RMC problem, current algorithms have various limitations: (i) Several RMC methods fail to recover the low rank matrix unless the number of observed entries is quite large; (ii) Some methods require as input the (often unknown) rank r of the target matrix and fail when overparameterrzeed even by just a single additional dimension (an input rank of r + 1); (iii) Various methods fail to recover a matrix with moderate condition number, as low as
We illustrate these issues in Figures 1 2 and These figures show recovery results of various RMC algorithms for matrix L' of size 3200 400, rank 5, a corruption rate of = 5% (see Section 4 for further details). As in Zeng and So 2017); 7); Tong et al. (2021) and Huang et al. (2021) the quality of recovered matrix f. is measured by the relative error -MMERMMEE ||-|| [|L.-1" and considered a
failure if MifreelMMM > 10-3, For each simulation setting ran 100 independent realizations. As shown in these figures, RMC methods such as AOP (Yan et al. 2013). RMC (Cambier and Absil (2016), RPCA-GD (Yi et al. 2016), RRMC (Cherapanamjeri et al. 2017 77), ,, HUB (Ruppel et al. 2020) and HOAT (Wang et al. (202)) require a large number of observed entries and fail when overparameterizzed In addition, all of them (except HUB) fail at condition numbers greater than 5.
On the theoretical front, some RMC methods have no theoretical recovery guarantees. The currently available guarantees for other methods are somewhat limited. As detailed in Table the guarantees for some methods only hold for fully observed matrices, or their allowed corruption level strongly depends the matrix rank and condition number.

---

RMC AOP RPCCAGD - HOAT
RMC + AOP + RPCA-GD + HOAT
HUB -RRMC
RGNMR-BS
HUUB RRMC RGNMR-BSS +RGNMR
10
failure probability
median error
10.5
0.4
10'10
0.2
10
overparametrized rank
overparametrized rank
Figure 2: Performance of RMC methods under overparametterizatin with input rank of 5 for i E [0, (left) Median rel-RMSE; (right) Failure probability (+1.99 SE). The matrix I has a condition number 2 and the oversampling ratio is [[]
tm rT 12. The corruption fraction is
5%
These shortcomings raise the following challenges: (i) Develop a computationally efficient RMC method able to handle ill-conditioned matrices, overparameteriattio, and a small number of observed entries; (ii) derive for this method strong recovery guarantees that improve upon those of existing methods.
Our contributions. In this work we make step towards resolving this challenge. We propose novel RMC method, denoted RGNMR, which overcomes the above limitations. Our proposed method a simple iterative algorithm based on Gauss-Newton linearization and removal of entries suspected to be outliers. As seen in Figures underlying matrices with significantly fewer observed entries than existing methods. Furthermore, the performance of RGNMR is not affected by overparameterized rank or by the condition number. In Appendix B we show that RGMMR continues to outperform other methods under broader conditions, including combination of outliers and additive noise, non-uniform sampling, higher rank matrices, range of fractions of outliers, etc. Furthermore, we show that RGNMR performs well on a real data set from computer vision, involving background extraction. In addition to its excellent empirical performance, in Section 3 we derive thcoretical recovery guarantees for RGNMR. Specifically, we present two theorems. Theorem Itaaes that given a suitable initialization, RGNMR recovers the target matrix at linear rate. This theorem holds under the weakest known assumptions for factorization based RMC methods. Theorem 3.2 establishes that the initialization scheme propose yields sufficiently accurate initial estimate for Theorem 3.1 to hold.
and empirically RGNMR can successfully recover the
states
2 The RGNMR algorithm
To describe RGNMR, we first introduce some notation. For a subset C [ni] x [m2], we denote by Ps the following projection operator
Pa(A)es = ( [As
(1, E Ω
10 (i,j) & Ω
For matrix A and set S2 denote ||A| | [Pn( -E Aly. Finally, we denote the set of corrupted entries by A. = {(i.j) E Q S * 0} and the number of corrupted entries by
k = |..] Both A, and k-" are unknown.
The optimization variables of RGNMR are two factor matrices U E R" V E R and subset Ω which estimates the locations of the corrupted entries. RGNMR receives as input the following quantities; the subset of observed entries {X,., (i,j) E S); the rank of the target matrix an upper bound & on the number of corrupted entries; initial guess (Uo, Vo) for the factor matrices and Ag C Ω for the set of corrupted entries.

---

RMC AOP RPCA-OD - HOAT
RMC + AOP + RPCA-GD + HOAT
-RAMC RGNMR-BS RGNMR
+HU RRMC RGNMR-BS 11RGNMM
100
failure probability
median error
0.8
10
10
0.2
164
3
condition number
condition number
Figure 3: Performance of RMC methods function of the condition number. (left) Median rel-RMSE; (right) Failure probability (#:1.6 SE). The oversampling ratio to(m) corruption fraction is = 5%.
[Q] 12. The
At each iteration RGNMR performs the following two steps: (i) given the current set of suspected outlier entries A, update U, V using the remaining entries ParA (X); (ii) given the updated matrix L, recompute the new set of suspected outliers A, by the k entries with largest magnitude in Pa(X L).
Let us provide some motivation for the above two steps. If the estimated set of non corrupted entries, Ω \AA, A. is large enough and contains only non-corrupted entries, namely A, C. A, then the matrix L could be recovered exactly from PAAAA (X) = Par,A (L") by solving a vanilla matrix completion problem, with outliers noise. Regarding the second step, consider ideal case where after step (i) of some iteration RGNMR obtained = L' Then at all the non-corrupted entries (i,j) E Q A., the residual X;, Lijj and L' is fixed point of the algorithm. Therefore, given L it is reasonable to estimate the corrupted entries by the entries with largest magnitude in Po L). Iterating this process we hope identify a sufficiently large subset of Ω A. and consequently recover L.
We now describe the two steps of RGNMR. The first step builds upon the matrix completion approach of Zilber and Nadler (2022). Formally, given the estimate A, of A, and the current factorization (Ue, Vi), the updated matrices (U++1 Vi+1) are the solution of the following least squares problem,
(U1+1. Vi+1) = arg min Cly, (U, V) arg min |IU.V + +UV -UVV X(I
(1)
U.V
U.V
This problem rank deficient with infinite number of solutions. As in Zilber and Nadler (0022)
we choose the new estimate to be the solution with minimal norm ||U++1| + V++1
For the second step, construct new estimate of A, by the k largest residual entries in
A++1 = arg
min ACO,JA/=k
|UVE + V. U,V,T - X(
(2)
RGNMR iterates these two steps until convergence or until a maximal number of iterations is reached. Algorithm| presents an outline of RGNMR.
Remark 2.1. In general, removing some of the observed entries, as in ② may be detrimental. For example, if after removal of entries suspected as outliers, only less than entries remain specific row or column, then the resulting matrix completion problem is ill- ill-posed and exact recovery of L is possible. As illustrated empirically in Zilber and Nadler (2022), GMMR is able to complete low rank matrices even if the number of observed entries is near the information limit. Therefore, as long as the number of remaining observed entries in each row and column above r, our method is often still able to recover the targel matrix.
Remark 2.2. As shown in Zilber and Nadler (2022). the absence of outliers, GNMR which iteratively solves [b. can successfully recover ill-conditioned low rank matrices, from relatively few observed entries. However, as illustrated in Figure 3 in the appendix, GNMR is not robust and fails completely in the presence of even small fraction of corrupted entries. Since in the first few iterations the set A₁ typically includes oulliers, employing GNMR would not result in a significantly better update of (Ue, Vi) than that of single optimization step. Therefore, in our scheme do not run GHMR till

---

Algorithm RGNMR
Input:
(Xig (1,j) E [2} observed entries
r rank of T,*
k upper bound on the number of corrupted entries
Uu Vo
(R()) initialization
Ao initial estimate of the of corrupted entries
- maximal number of iterations
Output: 1. of rank
for t = 00.. do
Un+1 Vi+1
arg min UUV +UV, UVV -XIIP(AA U.V
A+11 arg
min ACR,JA/=k
|UAV + U..VV -UVV X(F((A)
end for return PU U - -V-VV
convergence. Instead we re-estimate A after each update of (U,, Vi). This approach avoids redundant iterations of GNNR and yields considerable savings in terms of runtime.
2.1 Estimating the number of corrupted entries
One of the input parameters RGNMR is k. each iteration RGNMR removes the & entries with largest residual error, and performs low-rank matrix completion on the remaining entries. For RGNMR to succeed, it is crucial for & to be a tight upper bound of the true number of corrupted entries k", Indeed, if k > k= then too many entries are removed and on the remaining entries the corresponding matrix completion problem ill posed. As the true number of corrupted entries k-* is unknown, important to develop method to tightly upper bound it. Here we propose a scheme to do so.
Our approach is motivated by the empirical observation that the estimates A, of RGNMR behave differently if k < k* or k >> ka. If < ke then the estimates A, of the set of corrupted entries converge after several iterations. However, if k", the sets A, do not converge. This illustrated in Figure in the appendix. and we provide some intuition for this behavior below. Building upon this observation, we propose binary search algorithm to estimate k", assuming belongs the range [kiiny ]- In practice, we may take Kmin = 0 and kmax /22/22 (namely at most 50% corrupted entries). At each step we run RGNMR with we update kmin k. Otherwise, we set kmax = k. After log, (kmax kinin) steps we obtain a tight upper bound on k.
(kmin + 1 the sets A, converged, then
To provide intuition to why RGNMR behaves differently with & S Ae or scenario. Assume that l < k* and that some iteration, the set A, of k entries with largest current residuals, satisfies that A, C A.- The next estimate T4+1 of I.* minimizes [|PRY (l. X)I| ignoring the entries in As, which by assumption are all outliers. Hence, Lr+1 tries to fit low rank matrix to the remaining entries, and thus we expect the entries in A, to remain the & largest residual entries. Therefore, A, A4+1 and the same argument holds for all subsequent iterations the sets A, converge. In contrast, if & >> k- then at any iteration t, the set A, contains at least & - k* non-corrupted entries. Assume that some iteration the method successfully detected all outliers, ie. A. C. A₁. Then, if lo is not too large, the next estimate should be very close to the true low rank matrix Le+1 Rs L" As the computations are done finite precision, the residuals at both as well as at A, \ A, are not precisely zero but rather, due to rounding errors, appear very small random values. Therefore, even though C A4+1 remaining k k- entries are not the same as those of A, A,, but rather change each iteration t. Hence, the sets A, do not converge.
k k*, consider the following
A,
5

---

Algorithm 2 RGNMR modified
Input: All the inputs of RGNMR and the following additional parameters:
/ incoherence parameter of I."
a bound on the fraction of outliers each row/column
7 over-removal factor
6 neighborhood parameter
Output: L' of rank
for O...T do
A. support (Tza (UNVe -X
UU+1 Ve+1
= arg min {IUiV UU. - -UV (UPr (U,) e C,
Vn V. (4r)
U,V
end for
return LT V7
To demonstrate that our binary search scheme successfully bounds the number of corrupted entries compare variants of RGNMR. The first, denoted simply RGNMR, is given the true number of corrupted entries k* as input, k = k". The second variant, denoted RGNMR-BS, first upper bounds k" using our binary search scheme and then uses this upper bound k as input, h: = k. As illustrated in Figures | and RGNMR-BS performance similar to that of RGNMR, which implies that our method obtains sufficiently tight upper bound on k..
Remark 2.3. Several RMC methods aim to remove the corrupted entries and require an estimate of k* (Yan et al. 2013 Yi el al. 2016). Since the intuition provided above holds also for these methods, a similar scheme to estimate can be incorporated there as well. We note that in the simulations we conducted these methods were provided with the exact mumber of outliers. Still, in various settings, these methods failed to recover the underlying matrix. whereas RGNMR succeeded. This highlights that novel scheme for estimating the number of outliers is not the sole advantage of our proposed method.
Recovery guarantees
In this section we present recovery guarantees for RGNMR. Recall that the goal is recover rank matrix L E X from a subset Ω of the entries of X = L + S*. We start with some notations and the assumptions made in our theoretical analysis.
Notations. The i-th largest singular value of the matrix L E X is denoted by aj and its
condition number denoted by of/ / We denote the operator norm of matrix (a.k.a. spectral norm) by ||Al|ops its Frobenius norm by |A]]e, its i-th row by Ag.,). its column by A its largest row norm by ||A = max; [ and its zero norm by || = [{(i,j) E [m1] x [ma] Ar.j * OH. We define the matrix |A] by [A((s.)) = |A(i,)) We denote by (.(A) the best rank r approximation of A in Frobenius norm, namely the projection the subspace spanned by the
singular vectors with largest singular values. We denote l(.,)) = {i (i.)) E Ω). l(i = {j
(i,j) E 2} and Cj = (9 r, = [Q The Procrustes distance between Z1, 72 E RRar
dp Zz) = min [ - ZePl|e | || E Rx
xM is orthogonal
(3)
For a vector u we denote by (*)) its k-th largest entry in absolute value.
Assumptions. For the RMC problem to be well-posed, we make three standard assumptions.
Assumption 1. The underlying matrix L is incoherent with incoherence parameter μ.. Formally, if UEV is the SVD of L" then
||1|,,,00 S Vur/ni, ||V| I Vur/n2-
(4)

---

Table 1: Recovery guarantees requirements of various RMC methods, up to multiplicative constant factors. The weakest conditions for each category of methods are in bold.
Method
Sample Complexity
Corruption Rate
Method
Category
(pn2 2)
(a S)
Zheng and Lafferty
(016)
max { pr log 1,, / 2 22² a 0, No Corruption
Tong et al.
(021))
p = 1, Fully Observed
Factorization Based
Cai et al.
(0244
1, Fully Observed
JM ruN""
Yi al.
(0016)
1 log n4
Our Theorem
3.1
max log n1, p x²²
Full Matrix
Cherapanamjeri et al. 2017)
12222 log (uroū) log* n 1 log
Wang and Wei 2024)
For future use, we denote by M(n,, n2, (,, the set of n, n2 matrices of rank incoherence parameter ja and condition number k.
Assumption 2. (Bernoulli Model] Each entry X is independently observed with probability p. Hence, the number of observed entries is not fixed, but rather [[]] ~ Bin(nnnng (2,
Assumption 3. In each row and column, the fraction of observed entries which are corrupted is bounded. Formally, for a known
L, we assume that S* E S.. where
S α { x Vi: (Pa(S) S ar, Avj (Pa(S) S oey).
(5)
Assumption was introduced by Candes and Recht (2012). Assumptions 2 and 3 or variants thereof'
are common in theoretical analyses of matrix completion (see for example, Candès et al. 201 Yi
et al. 2016 Cherapanamjeri et al., 2017; Wang and Wei 2024).
Similar to other works on robust matrix completion, we derive guarantees for a slightly modified variant of our proposed method. Specifically, we make the following two modifications.
First, the of corrupted entries A, is estimated differently. In the original method A. is estimated as the set of largest residual entries. However, motivated by Assumption [3 that the fraction of corrupted entries in each row and column bounded, in the modified algorithm we remove only a bounded number of entries from each row and column. To this end we introduce the following thresholding operator (A, S2). Given an input matrix A, subset Ω and parameter 0 (0, 1). the operator (A .2) keeps only those entries (i, Ω which belong to the largest 8-fraction of entries in both the respective row and column j. and zeros out all the remaining entries. In case of entries having identical magnitude, ties are broken arbitrarily. Formally,
{ (Pa(A)ss [0,
|A, [IPa(A)((.)) (16r1) A |Ar,1 [IPa(A) (1)) (10g,))
(2)
(6)
otherwise.
At each iteration given the current estimate L, = UUV,, the estimated set of corrupted entries is
A, = support (To (L, - X,))).
(7)
As in the original method, entries are still removed based on the magnitude of their residual but in this way the number of removed entries from each row and column is bounded. For RGNMR to be able to remove all outliers, necessary condition is that 0 2 a. In what follows, we choose 0 = aa where 7 is the over-removal factor.
The second modification to RGMMR is to constrain the update (U++1, V(41) to be in the vicinity the current pair of factor matrices (U,, Vi) and to have bounded row norms. Formally, for parameter
7

---

5; > 0 we define the ó, neighborhood of the current estimate (Ut, Vi) as
{
C(U,, Ve, de)
R (m)=-))))
xr
I/0 Uzll + |I Vill S
(8)
and denote the subset of factor matrices with bounded row norms by
B, =
U
E (m()++s)xx
|1 S
3uroi
| S
3uroj
71
11/2
where the constant arbitrary. Instead of Eq. updates the factor matrices as follows,
T for a suitably chosen 6 > O, the modified RGNMR
8 (U++1, Ve+1) arg min (U, ( nc Un, Vv, 4et1 }}
(10)
Similar constraints were employed by Zilber and Nadler 2002) and Keshavan et al. (2010), in deriving theoretical guarantees for their (non-robust) matrix completion algorithms. As these constraints quadratic, the above problem may be written as convex optimization problem with quadratic regularization terms. Hence, it can be solved computationally efficiently. The modified RGNMR is described in Algorithm 2
Main theorems. To state our recovery guarantees we introduce the following definitions. For rank matrix L with smallest singular value or, define the following sets, in Zilber and Nadler (202)). First, we denote all factorizations of rank-r matrices with a bounded error from L L"by by
(c = {UU E to)+
|UVT L' S 3
(11)
In particular, denote by B (0) the set of all exact factorizations of L*,
B (U.V) R (mi+)))
UVV =VT==1+
(12)
We say that U, V are balanced if U = VTV, and measure the imbalance by We denote all the pairs of factor matrices which are approximately balanced by
-VTU-
(5t(()) (U.V) +n))+ - 50
(13)
Our first theorem states that starting from sufficiently accurate balanced initialization with bounded row norms, the modified RGNMR of Algorithm 2 recovers L with high probability and with linear convergence rate.
Theorem 3.1. X S*, where L E M(ni, n2, v. μ, k), and without loss of generality n1 2 n2. Let the set of observed entries Ω follow Assumption 2 and the corruption matrix S* satisfy Assumption 3 for some known (0,1). For large enough absolute constants C, c₁ Ces Ca. C, the following holds: the fraction of corrupted entries small enough, -1 and the probability to Cpr
"crpu
observe an entry is high enough, p
max nı, prx?), then w.p. at least n, Algorithm Eak' over removal factor e, S 7 S Vca and an initialization
6
n2
2 with parameter 250". Ctr
< S
(Uo, Vo) Berl (ex( n Buin 2 B, converges linearly L That is, after t iterations the
estimate L1 =UVVT satisfies
of 14, -4- -' S 2 CEVE
(14)
Our second theorem states that under suitable conditions it is possible to construct an accurate initialization that satisfies the requirements of Theorem 33. To do so we employ the spectral based initialization scheme proposed by Yi et al. (2016), followed by a normalization procedure on rows of the factor matrices. Similar normalization procedures were employed by ZZheng and Lafferty (2016) and Zilber and Nadler (2022) for their analysis of matrix completion without outliers. Our initialization scheme, outlined Algorithm 3 is described in detail in Appendix
8

---

Theorem 3.2. Let - L' E MM (ii,nn D2,T,RRR) S E S2 and without loss of generality, n1 2 n2. Then for any c₁ for large enough constants Ca. C the following holds: If a cak2r2p
and p 2 C log then w.p. at least
G.
Algorithm
oulputs a pair (Uo, Vo) that satisfies
1
1
(Uv, Vo) Ber
n Bein
n n
(15)
CevT
2c
Remark 3.1. Theorem 3.1 holds for 25 S Exx In principle to provide valid value of in this cg interval requires knowledge of oi and o. We note that several other works also required knowledge of of or of or both for their methods (see) Yi et al.) [016]] Sun and Luo 2016 Cherapananjeri eet al. (2017). In fact, for our approach it suffices to estimate these two singular values up constant multiplicative factors. Moreover, within the proof of Theorem 3.2 we show that under its assumptions. it is indeed possible to estimate of and o. up to constant factors.
Remark 3.2. Theorems 3.7 and 3.2 require that the parameters μ and a are known. Similar assumptions were made in previous works (e.g. YYi et al. 2016; [herapananjerii et al. 2017 Sun and
Lu0 2016 Zilber and Nadler 2022).
Comparison to other recovery guarantees. We compare our theoretical results to those derived for both factorization based methods as well as methods that operate on the full matrix.
For the vanilla matrix completion problem, where the observed entries are not corrupted, the smallest sample complexity requirement for factorization based methods was derived by ZZhng and Lafferty) (2016). Remarkably, Theorem 3.1 matches this result for RGNMR even in the presence of corrupted entries. The number of samples required by Theorem 3.1 is smaller than those required for other RMC methods YYi et al. 2016 Wang and Wei 2024) and if C Colog (log(ura)) log 11, for suitable constant C, it is also smaller than the requirements in Cherapanamjeri et al. (2017).
In terms of the fraction of corrupted entries, the recovery guarantee with the highest for factorization based methods was derived by Tong et al. assumption that the matrix is fully observed. Theorem 3.1 improves upon this result by a factor of O( D(T),, even though the matrix is only partially observed. Hence our recovery guarantee holds under the weakest known conditions for factorization based methods. For general RMC methods the recovery guarantee with the highest a was derived by Cherapanamjeri et al. (0177) Theorem 3.1 requires smaller than in Cherapanamjeri et al. (2017) by a factor of (R)) Table summarizes the sample complexity and corruption rate requirements of different methods.
(2021) and by Cai et al. (2024), under the
Next, for constructing suitable initialization the requirements stringent than those for the recovery guarantee of Theorem 3.1 This separation common in other works matrix completion (Zheng and Lafferty| 2016 Yi et al. 2016: Zilber and Nadler 2022). In terms of sample complexity Theorem 3.2 still improves upon the results in Yi et al. (2016) and Wang and Weil (0244) and in some parameter regimes also upon the result in Cherapanamjeri et al. (2017). In terms of the fraction of outliers the condition in Theorem 3.2 is more stringent than in Yi (016) and Cherapanamjeri al. (2017). Since empirically RGNMR succeeds even with random initialization we believe the condition imposed by Theorem can be relaxed. This would allow for less stringent conditions in Theorem 3.2 We leave this for future work.
and p in Theorem 3.2 are more
4 Numerical results
This section details the simulations conducted to compare the various RMC methods. The results are illustrated in Figures I 2 3 and in Appendix(] Each instance consisted of generating a random matrix L E " X22 of a given rank r, condition number K, subset of observed entries Ω2 S [Mı] x [T2]] and corruption matrix St. We generate L following Tong al. (202I). Specifically, we construct U E Ra xP V E R with entries i.i.d. from the standard normal distribution and orthonormalize their columns. We then construct Σ E "x" as a diagonal matrix with evenly spaced values between 1 and on the diagonal. We set L UEVT. Next, to generate l we follow Zilber and Nadler ( Given an oversampling ratio p we sample Ω of size [pr(n) + ni - -r) randomly without replacement and verify that it contains at least entries in each column and row. To construct the corruption matrix S we first sample its support A, S Q as follows. Given fraction a of corrupted entries we sample [a- [[2l entries out of Ω randomly without replacement. We then verify that the

---

set 52 \ A. contains at least r entries in each column and row. Similar to Cai et al. (2024) and Wang and Wei (2024). we sample the value of each corruption entry uniformly between max:,; [ and maxi, a Each method is then provided with the matrix Pa(L +,*), the set of entries f and the matrix rank r.
We compare RGNMR to AOP Yaan al. 2013), RMC (Cambier and Absil 2016), RPCA-GD Yi al. 2016). RRMC (Cherapanamjeri et al. 2017). HUB (Ruppel et al.) 2020) and HOAT (Wang et al. 2023) In addition, as described in Section 2. we compare RGNMR to RGMMR- --MMR-B...AA Implementations of all methods except RRMC are publicly available. An implementation of RRMC was kindly provided to us by Waag and Wei (2024). MATLAB and Python implementations of RGNMR are available at github. wethub.ccm/44 wwte:eee/nnnn/// htmm//elnn99/RRNRRR RGNMR, All simulations were run on a 2. IGHZ Intel Core i7 CPU with 32GB of memory.
Each algorithm was executed with its default parameters, with the following exceptions: (i) To improve RPCA-GD and HUB performance we increased their number of iterations by using stricter convergence threshold than their default; (ii) In RPCA-GD we employed an over removal factor y of 4 as it significantly improved its performance in our simulations; (iii) We tuned the parameter & in HOAT to 30; (iv) We provided AOP the exact number of corrupted entries; (v) For RRMC we use the same parameters used in Wang and Wei (2024).
In Appendix B we illustrate the performance of RGNMR under a broad set of additional scenarios. Specifically, Figure 0 shows that RGNMR can handle a large fraction of corrupted entries. Figures
7 and 8 show that RGNMR outperforms other methods also under non-uniform sampling. Figures
9 10 and [T illustrate its performance under combination of additive noise and outliers. Figure
12 demonstrates that RGNMR can recover matrices with a high rank even the number of observed
entries is relatively small. Figure 13 illustrates that RGNMR performs well on real dataset invol
background extraction in video. This is a standard benchmark for RMC methods (Yi et al. 2016
Cherapanamjeri al., 2017 Huang al. 2021 Cai et al. 2024 Finally, Figure 14 shows the runtime of RGNMR and illustrates its performance on large matrices.
Limitations and future research
In this section we discuss the theoretical and empirical limitations of RGNMR, These suggest several promising directions for future research.
On the theoretical front, though our analysis improves upon existing results, it does not fully account for the remarkable empirical performance of RGNMR. For example, the conditions in Theorem [3.1 on both a and p depend on the condition number while empirically the performance of RGNMR is not affected by k. addition, our analysis did not consider the case of overparameterization. These are open directions for future theoretical analysis of RGNMR.
On the empirical front, although RGNMR performs well in cases where most RMC methods fail, it is more computationally demanding than some of them. This is because each optimization step of RGNMR requires to solve large system of linear equations [[). whereas some other methods require only a gradient descent step. As we illustrate in Figure [4] the runtime of RGNMR grows quadratically with n. Improving the runtime of RGNMR is therefore an interesting direction for future research.
Another possible line of research is to employ RGNMR to the problem of robust matrix recovery al. 2220b] Ding et al., (202T] Ma and Fattahi 2023). As discussed in Remark 2.2 RGNMR is closely
related to the GNMR method (Zilber and Nadler 2022). Since GNMR was proven to successfully handle the problem of vanilla matrix recovery, where data is corrupted, believe the same can be achieved for RGNMR in the presence of corrupted data.
Acknowledgments B.N. is the incumbent of the William Petschek Professorial Chair of Mathemat- ics. The research of B.N. was supported in part by grant 2362/22 from the Israel Science Foundation. We thank Tianming Wang and Ke Wei for sharing the code of their work (Wang and Wei 2024). We also thank the anonymous reviewers for their valuable feedback that improved the quality of our manuscript.
10

---

References
Bauch, J., Nadler, B., and Zilber, P. (2021). Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries. SIAM Journal on Mathematics of Data Science, 3(1):439-466 465.
Bennett, J., Lanning, S., et al. (2007). The Netflix Prize. In Proceedings of KDD Cup and Workshop. volume 2007, page 35. New York.
Boumal, N. and Absil, P.-a. (2011). RTRMC: A Riemannian trust-region method for low-rank matrix completion. Advances in Neural Information Processing Systems, 24.
Boumal, N. and Absil, P.-. (2015). Low-rank matrix completion via preconditioned optimization on the grassmann manifold. Linear Algebra Appl., 475:200-239,
Cai. H., Cai, J.-F, and Wei, K. (2019). Accelerated alternating projections for robust principal component analysis. Journal of Machine Learning Research, 20(20):1-33.
Cai, H., Kundu, C., Liu, J., and Yin, W. (2024). Deeply learned robust matrix completion for large-scale low-rank data recovery. arXiv preprint arXiv:2501.000 000677.
Cai, J.-F., Candès, E. J., and Shen, Z. (2010). A singular value thresholding algorithm for matrix completion. SIAM Journal Optimizatioo,, 20(4):1956-192.
Cambier, L. and Absil, P.-A. (2016). Robust low-rank matrix completion by Riemannian optimization. SIAM Journal on Scientific Computing, 38(5):5440-$44
Candes, E. and Recht, B. (2012). Exact matrix completion via convex optimization. Communications of the ACM, 111-111
Candès, J., Li, X., Ma. Y., and Wright, (2011). Robust principal component analysis? Journal of the ACM (JACM), 18(3)
Chen, Y., Fan, J., Ma, C., and Yan, Y. (2021). Bridging convex and nonconvex optimization in robust pea: Noise, outliers, and missing data. Annals of Statistics, 49(5):2948.
Chen, Y., Xu, H., Caramanis, C., and Sanghavi, (2015). Matrix completion with column manipula- tion: Near-optimal sample-robustness-rann -ran tradeoffs. IEEE Transactions on Information Theory, 62:1-1.
Cheng, C. and Zhao, Z. (2024). Accelerating gradient descent for over-parameterized asymmetric low-rank matrix sensing via preconditioning. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7705-7709. IEEE.
Cherapanamjeri, Y., Gupta, K., and Jain, P. (2017). Nearly optimal robust matrix completion. In International Conference Machine Learning, pages 797-805. PMLR.
Davenport, M. A. and Romberg. J. (2016). An overview of low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics in Signal Processing, 10(4):608 622.
Ding, L.,, Jiang, L., Chen, Y., Qu, Q., and Zhu, Z. (2021). Rank overspecified robust matrix recovery: Subgradient method and exact recovery. arXiv preprint arXiv:2109. /1
Drineas, P., Javed, A., Magaon- M., Pandurangan, G., Virrankoski, R., and Savvides, A. (2006). Distance matrix reconstruction from incomplete distance information for sensor network localiza- tion. In 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks, volume 2, pages 536-544. IEEE
Eriksson. A. and Van Den Hengel, A. (2010). Efficient computation of robust low-rank matrix approximations in the presence missing data using the I.-1 norm. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 771-778, IEEE.
He, Y., Wang. F., Li, Y., Qin, J., and Chen, B. (2019). Robust matrix completion via maximum correntropy criterion and half-quadratic optimization. IEEE Transactions on Signal Processing, 68:181-195.

---

Hsu, D., Kakade, S. M., and Zhang, T. (2011). Robust matrix decomposition with sparse corruptions. IEEE Transactions on Information Theory, 57(11):221--234.
Huang, M., Ma, S., and Lai, L. (2021). Robust low-rank matrix completion via an alternating manifold
proximal gradient continuation method. IEEE Transactions Signal Processing, 69:2639-2653
Jain, P., Meka, R., and Dhillon, I. (2010). Guaranteed rank minimization via singular value projection. Advances in Neural Information Processing Systems, 23.
Jain, P.. Netrapalli, P., and Sanghavi, S. (2013). Low-rank matrix completion using alternating minimization. In Proceedings of the Forty-Fifth Annual ACM Symposium Theory of Computing, pages 665-674.
Jiang, X., Zhong. Z., Liu, X., and So, H. C. (2017). Robust matrix completion via alternating projection. IEEE Signal Processing Letters, 24(5):579-3
Ke, Q. and Kanade, T. (2005). Robust L1 norm factorization in the presence of outliers and missing data by alternative convex programming. In 2005 IEEE Computer Society Conference on Computer Vision and Putlern Recognition (CVPR'05) volume 1, pages 739-746. IEEE.
Kennedy, R., Balzano, L.., Wright, J., and Taylor, C. J. (2016). Online algorithms for factorization- based structure from motion. Computer Vision and Image Understanding, 150:139-152.
Keshavan, R. H., Montanari, A., and Oh, S. (2010). Matrix complction from a few entries. IEEE Transactions on Information Theory, 56(6):2980-2998
Klopp. O., Lounici, K., and Tsybakov, A. B. (2017). Robust matrix completion. Probability Theory and Related Fields, 169:523-55555 -64.
Kümmerle, C. and Verdun, C. M. (2021). A scalable second order method for ill-conditioned matrix completion from few samples. In International Conference on Machine Learning, pages 3872-5883. PMLR.
Lejun, G., Like, Y., Xinyi, W., Shehai, Z., and Shuhua, X. (2025). Seqbme: Single-cell data processing using iterative block matrix completion algorithm based on matrix factorisation. IET Systems Biology, 19(1):e70033.
J., Cai, J.-F. and Zhao, H. (2020a). Robust inexact alternating optimization for matrix completion with outliers. Journal of Computational Mathematics, 38(2):337-354.
Li, L., Huang, W., Gu, Y.-H., and Tian, Q. (2004). Statistical modeling of complex backgrounds for foreground object detection. IEEE Transactions Image Processing, (3(11):1459 1472.
Li, X., Zhu, Z., Man-Cho So, A., and Vidal, R. (2020b). Nonconvex robust low-rank matrix recovery. SIAM Journal on Optimization, 30(1):660-68)
Lin, Z., Chen, M., and Ma, Y. (2010). The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv preprint arXiv: 1009.5550
Lin, Z., Xu, C., and Zha, H. (2017). Robust matrix factorization by majorization minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(1):208-22)
Liu, Z., Han, Z., Tang, Y., Zhang, H., Tang, S., and Wang, Y. (2025). Efficient over-parameterize matrix sensing from noisy measurements via alternating preconditioned gradient descent. arXiv preprint 0rXiv:2502.004465
Ma, J. and Fattahi, S. (2023). Global convergence of sub aub-gradient method for robust matrix recovery: Small initialization, noisy measurements, and over-parame wer-parameterizztionn. Journal of Machine Learning Research, 24(96):1-8) 84.
Ma, S., Goldfarb, D., and L. (2011). Fixed point and bregman iterative methods for matrix rank minimization. Mathematical Programming, 128(1):321-355
Meka, R., Jain, P., and Dhillon, I. (2009). Matrix completion from pawer-law distributed samples. Advances in Neural Information Processing Systems, 22.
12

---

Meng, D., Xu, Z., Zhang, L.,, and Zhao, J. (2013). A cyclic weighted median method for 11 low-rank matrix factorization with missing entries. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, pages 704-710.
Miao, and Kou, I. (2021). Color image recovery using low-rank quaternion matrix completion algorithm. IEEE Transactions on Image Processing, 31:190-201.
Muma, M., Zeng, W.-J., and Zoubir, M. (2019). Robust m-estimation based matrix completion. In ICASSP 2019 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5476-5480. IEEE.
Netrapalli, P., UN, N., Sanghavi, S., Anandkumar, A., and Jain, P. (2014). Non-convex robust pea. Advances in Neural Information Processing Systems, 27.
Nic, F., Wang, H., Cai, X., Huang, H., and Ding, C. (2012). Robust matrix completion via joint Schatten p-norm and Ip-norm minimization, In 2012 IEEE 12th International Conference on Data Mining, pages 566-574. IEEE.
Okatani, T.,, Yoshida, T., and Deguchi, K. (2011). Efficient algorithm for low-rank matrix factorization with missing components and performance comparison of latest algorithms. In 2011 International Conference on Computer Vision, pages 842-849. IEEE.
Recht, B. and Ré, C. (2011). Parallel stochastic gradient algorithms for large-scale matrix completion. Mathematical Programming Computation, 5.
Ruppel, F., Muma, M., and Zoubir, A. M. (2020). Globally optimal robust matrix completion based on M-estimation. In 2020 JEEE 30th International Workshop on Machine Learning for Signal Processing (MLSP), pages 1-6. IEEE.
Shen, Y. and Sanghavi, S. (2019). Learning with bad training data via iterative trimmed loss minimization. In International Conference on Machine Learning, pages
PMLR.
Shen, Y., Wen, Z., and Zhang, Y. (2014). Augmented lagrangian alternating direction method for matrix separation based on low-rank factorization. Optimization Methods and Software, (9(2)233 263.
Sun, R. and Luo, Z.-Q. (2016). Guaranteed matrix completion via non-convex factorization. IEEE Transactions Information Theory, 62(11):6535-60
Tong, T., Ma, C., and Chi, Y. (2021). Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. Journal of Machine Learning Research, 22(150):1-63.
Tulyakov, S., Alameda- Mlaeeda-Pineda, X., Ricci, E., Yin, L., Cohn, J. F., and Sebe, N. (2016). Self- adaptive matrix completion for heart rate estimation from face videos under realistic conditions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
Wang, B. and Fan, J. (2024). Robust matrix completion with heavy-tailed noise. Journal of the American Statistical Association, pages 1-13.
Wang, T. and Wei, K. (2024). Leave-one-out analysis for nonconvex robust matrix completion with general thresholding functions. arXiv preprint arXiv:2407. 19446.
Wang, Z.- Li, X. P., and So, H. C. (2023). Robust matrix completion based on factorization and truncated quaadatdd loss function. IEEE Transactions on Circuits and Systems for Video Technology, 33(4):1521-153
Waters, A., Sankaranarayanan, A., and Baraniuk, R. (2011). SpaRCS: Recovering low-rank and sparse matrices from compressive measurements. Advances in Neural Information Processing Systems, 24
Wong, R. K. and Lee, T. C. (2017). Matrix completion with noisy entries and outliers. Journal of Machine Learning Research, 18(147):1-25.
13

---

Wu, D., Li, Z., Yu, Z., He, Y., and Luo, X. (2025). Robust low-rank latent feature analysis for spatiotemporal signal recovery. IEEE Transactions on Neural Networks and Learning Systems, (6(2))2829-2842
Xu, X., Shen, Y., Chi, Y., and Ma, C. (203)). The power of preconditioning in overparameterizee low-rank matrix sensing. In International Conference on Machine Learning, pages 38611 1-38654. PMLR.
Yan, M., Yang, Y., and Osher, S. (2013). Exact low-rank matrix completion from sparsely corrupted entries via adaptive outlier pursuit. Journal of Scientific Computing, 56:433-449.
Yi, X., Park, D., Chen, Y., and Caramanis, C. (2016). Fast algorithms for robust pea via gradient descent. Advances in Neural Information Processing Systems, 29.
Zeng, W.-J and So, C. (2017). Outlier-robust matrix completion via lp-minimization. IEEE Transactions Signal Processing,
Zhang. J., Fattahi, S., and Zhang, R. Y. (2021). Preconditioned gradient descent for over wer-parameterized nonconvex matrix factorization. Advances in Neural Information Processing Systems, 34:5985- 5996.
Zhao, L.. Babu, and Palomar, D. (2016). Efficient algorithms robust low-rank matrix completion against outliers. IEEE Transactions on Signal Processing, 64(118)4476744780
Zheng, Q. and Lafferty, J. (2016). Convergence analysis for rectangular matrix completion using Burer-Monteiro factorization and gradient descent. arXiv preprint arXiv:1605.07055 07051.
Zheng, Y., Liu, G., Sugimoto, S., Yan, S., and Okutomi, M. (2012). Practical low-rank matrix approximation under robust 1-norm. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 1410-1417. IEEE.
Zhu, Z., Li, Q., Tang, G., and Wakin, M. B. (2018). Global optimallty in low-rank matrix optimization. IEEE Transactions Signal Processing, 66(13):3614-322
Zilber, P. and Nadler, B. (2022). GNMR: A provable one-line algorithm for low rank matrix recovery. SIAM Journal on Mathematics of Data Science, 4(2):909-934.
14

---

k [A++ Ω A.
100
50
Iteration
Figure 4: Empirical convergence coneeonvee of A, function of the iteration t of RGNMR for & < k" (red), k = k* (black) or > k* (blue). The assumed number of corrupted entries was in the range & E [0.95, 1.05) k=" As shown, if k k= A, does not converge.
A Initialization procedure
Theorem 3.1 shows that starting from sufficiently accurate balanced initialization with bounded row norms RGNMR recovers L*. Therefore, the goal of our initialization procedure is to construct such initialization. Our proposed scheme starts by constructing initial estimator of S*, which we denote by Sina- To this end, the function Ta (defined in eq. (6) is applied to Pa(X). Formally,
Sint = Ta (P)
(16)
If the initial estimate of 5 is accurate enough, Sinit = S", then (Pa((X) - Sinit) a E[Pn(L")], should be a sufficiently accurate estimation of L Denote by ÚÊVT the SVD of Pr (H Smiit) To obtain a balanced factorization of ( Stna) we use the following operator,
(P((X) SSnst)
(v)
1
(17)
Note that the output of this operator is perfectly balanced factorization which satisfies U = VTV. To bound the row norms of the factor matrices we apply a clipping operator R. with suitably chosen The operator is applied to vector x and it is defined as
x
X X
S 7 >
Rx
(18)
For matrix A, we define (A) as the matrix obtained by applying Ry to each of its rows. For every row i, R., (A.) (i.))) Algorithm outlines this initialization scheme.
B Additional simulations
We present here results of additional simulations under various settings beyond those described in the main text.
Ossows the performance of various RMC methods function of the fraction of corrupted entries a. We only compare methods that performed well at an oversampling ratio of P(2. F = with a = 5%, see Figure excluding RPCA-GD, HOAT and RRMC. As shown in the left figure if the number of observed entries relatively small, at oversampling ratio of 8, then RGNMR can handle larger fraction of corrupted entries than other methods. In the right figure we show that if the number of observed entries is relatively large, oversampling ratio of 12, then methods such as RMC and AOP can handle larger number of corrupted entries than RGMMR. We note that if the condition number is high then RGNMR still outperforms these methods.
Fraction of outliers.
15

---

Algorithm 3 Initialization procedure for Robust Matrix Completion
Input:
(Xi,) (4,j) e [2} observed entries
# incoherence parameter of I.*
7 rank of L'
p probability of observing an entry
the maximal fraction of outliers in each row/column
Output: (Uo, Vo)
Sinit Ta (Pa( x), An estimate of 5* - Simit)
U
set Z =
= b-SVD, [1 (Pn(X)
set 1/1
llop and 1/2
12
n2
Rm (Uo)
Z
Ryp (Vo)
return (Uo, Vo)
Non-uniform sampling, In many applications, the entries of the matrix are not sampled uniformly (Meka et al. 2009 Okatani al. 201T). Hence we made simulations where the observed entries followed power law sampling scheme similar to Meka et al. (2009) and diagonal banno pattern as in Okatani et (20IT).
For the power law scheme, given an oversampling ratio we define w pp pp.r (m1 + n2 r).
We construct two sequences (p1 ... pr,) and (#1 .....))))))))) such that p. = i- 3, qs = i We then normalize them construct two new sequences
Ds Σ,
Pt = w.
Σ,
Note that E.p:= w. We sample each entry (i. with probability peg The expected number of observed entries is then E[s] w. Figure 7 we illustrate that RGNMR performs better than most methods when the entries are sampled under this scheme.
For the diagonal- baand pattern, we generated n X n matrices of rank r with a diagonal bandwidth of length pr across different values of This results in approximately (n 12) pr observed entries and therefore is approximately the oversampling ratio. As illustrated Figure 8 though RGNMR requires larger oversampling ratio than in the uniform pattern succeed in this task, it stills outperforms other RMC methods.
Outliers and additive noise. In Figures 9 10 and illustrate that RGNMR still outperform most RMC methods even under additive noise. these simulation, all observed entries are corrupted by additive white Gaussian noise with known standard deviation a, in addition to the few outliers entries. this scenario inliers entries are corrupted with random noise. Note that our method for upper bounding k." based on the assumption that the error in those entries is the result of rounding errors, see 2.1 To overcome this problem, when searching for an upper bound on k* we terminated RGNMR once
- XXIleee [[]]F((A
Vo.
High rank matrices. In Figure 12 we compare the performance of various RMC method as
function of the rank of the target matrix L*. Following (Huang et al., 2021 Wang and Weil 2024)
[92] we fix the corruption rate a 0.1 and vary the rank and the fraction of observed entries mi As shown, RGNMR successfully recovers L from a small fraction the observed entries even the rank of L is relatively high.
Real data: Background extraction from video. In Figure 13 we illustrate RGNMR performance for video background extraction. We use the data from Li et al. 2004), kindly provided to us by the
16

---

RGNMR + GNMR
RGNMR GNMR
10
fallure probability
0.8
median error
10
0.6
10:10
0.2
10
0
0
0.02
0.04
0.06
0.08
0.1
0
0.02
0.04
0.06
0.08 0.1
fraction of corrupted entries or (%)
fraction of corrupted entries ar (%)
Figure 5: RGNMR performance compared to that of GNMR (Zilber and Nadler 2022) under small fraction of corrupted entries. (left) Median rel-RMSE (right) Failure probability defined as P(re1-RMSE > 10-3). The underlying matrix L is of size 500 x 500 has rank and condition
number K 2. The oversampling ratio is Fin fnn 12 and the fraction of corrupted entries o varies. Each point corresponds to 50 independent realizations.
[0]
authors of (Huang et al. 2021). The data contains a sequence of grayscale frames. By stacking the columns of each frame of the video into long vector, obtain matrix whose columns correspond to the frames. This matrix can be decomposed to a low rank matrix corresponding to the static background plus a sparse matrix corresponding the moving foreground. Following (Yi et al. 2016 Cherapanamjeri et al.) 2017 Huang et al. 2021; Cai et al. 2024) we sample uniformly at random 5% of the matrix entries. All method are then given the sampled entries and an input rank of 1. As
shown RGMMR performs well on real data and successfully extracts the background.
Runtime. Finally, In Figure 14 we illustrate that RGNMR scales well with the matrix size. We show that for matrix of size n x the runtime of RGNMR and RGNMR-BS increases quadratically with n. In addition, we illustrate that even on large matrices RGNMR still requires relatively small number of observed entries to succeed.
C Proofs of Theorems
3.1 and 3.2
To prove Theorems
3.1 and 3.2 we make use of several auxiliary lemmas. These are outlined in
subsections C.1 and
The proofs of the two theorems appear in subsections C.2 and C.4
C.1 Auxiliary Lemmas For Theorem
The first three lemmas are results from (Zilber and Nadler 2022). The first one is combination of Lemmas SM5.3 and SM5.5 from (Zilber and Nadler 2022).
Lemma C.1. Let I." E M(ni, n2, V. (6) 1) and let follow Assumption 2 with probability p. Let 6
(0, 1). There exist constants C, et, such that the following holds: If 2 Cmax logn1 2²,²n²
azc"
Then w.p. at least 2. any (U, V) E Bor(e/ce) n Bota (1/a) nB, with L = UVT there exists
(U", V*) E B* Bp such that
25
IU U- + I| v- <
-UV - 1'
(19a)
40;
1 [(U - - - V*) Mr S I Li
(19b)
The second lemma Lemma SM5.4 in (Zilber and Nadler 2022).
Lemma C.2 (uniform RIP for matrix completion). Let I.* E M(1n, 02, V. k) and let St follow Assumption with probability p. Let 1). There exist constants C, Ct Ce such that the
17

---

RMC
AOP
+HB
RMC +AOP
+ HUB
RGNMR-BS + RGNMR
RGNMR-BS + RGNMR
failure probability
failure probability
0.8
0.8
0.4
0.4
0.2
0.2
3
12
24
fraction of corrupted entries a (%)
fraction of corrupted entries (%)
Figure 6: Failure probability (#1.96SE) of RMC methods function of the fraction of corrupted
entries a. (left) Oversampling ratio of r(m1+-g--))
[|]
8; (right) Oversampling ratio of r(ma-t2-r)
[[]
12. The underlying matrix L of size 3200 x 400 has a rank r = 5 and condition number x Each point corresponds to 100 independent realizations.
following holds: p 2 C Clogny Then w.p. at least 1
3 nt. for all matrices T. = UVT where
(U.V) E Ben(e/ce) n Botn (1/ca) n B,, following holds.
(1-+)l|L- L*Il= S J PP - s (1 (1+ L'
(20)
The third lemma is Lemma SM5.6 in (Zilber and Nadler 2022), which in turn is a direct consequence
of Lemma 7.1 in (Keshavan et al. 2010). In (Zilber and Nadler (022) the result is stated with an unspecified constant Tracking its proof it can be shown that it holds with = 2. which is how the lemma is stated below.
Lemma C.3. Let follow Assumption 2 with probability p. There exist a constant C' such that the 22r²
following holds for any p. p,t,e >> Ifp C Caxx
log 12
aze ). Then w.p. at least 1 2 for any nx
n2
(U,V) (2( such that
| S 4 W/jrt/mm
| S Wurt/n2.
(21)
have
1 L ((() <
U + IV 2
(11 + [IVI12) + (67)
(22)
The following two lemmas provide bounds on the estimates constructed by RGNMR at each iteration. The first lemma states that starting from an approximately balanced and sufficiently accurate estimate of L", if each new pair of factor matrices is sufficiently close to the previous one, then all factor matrices continue to be approximately balanced, and remain not too far from L Its proof appears in Appendix D.
Lemma C.4. Les I." E EM(n n2,T, x) with r-th singular value o7. For large enough constants et ce the following holds: If (Uo, Vo) E Berl (.vrr) n Bain 2cj n B,, and for every 1 S 1,,
(Us, V.) E C(U.-1, V.-1, T T(x)) then (U141, Ve-1) E Berl (122) (2)
The second lemma bounds the distance between L and the updated estimate L as function of various quantities of the current estimate Lt. Its proof appears in Appendix D.2
Lemma C.5. Let L, U.V,T be the estimate of L at iteration Let L U be the updated estimate, where (U++1, Vi+1) are computed by (10) with some 8 > O. Assume that Le is sufficiently close to L", so that the set A, = B n B, n C (Uz, Vz, पहा)) is non empty. Let (U*, V*) E A, and denote AU; = U, - U*, AU = U U, with similar definitions for AV,
5
and &V Then, the error on the non removed entries Ω Ω \ Ax of the updated estimate satisfies
|| [141 T( AV [L + /2
(23)
+ (1
18

---

RMC AOP RPCA-OD - HOAT
RMC + AOP + RPCA-GD + HOAT
RRMC RGNMR-BS RGNMR
+HUB RRMC RGNMR-BS -1-GNMR
10
failure probability
14
median error
0.8
10
0.6
0.4
10
0.2
10
oversampling ratio
oversampling ratio
Figure 7: Results of RMC methods as function of the oversampling ratio under power law sampling. (left) Median rel-RMSB (right) Failure probability defined as (P(relRMMSE > 10-3). The underly- ing matrix I." is of size 1000 1000 has rank r 5 and condition number x The fraction of corrupted entries is a 5%. Each point corresponds to 50 independent realizations.
Before we present the last lemmas, whose proof's appears in Appendix D.3 recall that each iteration I, RGNMR removes from Ω the entries in A, = support(T<,. (L, (X,2)). If RGNMR was unable to identify all the corrupted entries, then the (52 Ae) n A., where A. support(S*). is not empty. The following lemma bounds the magnitude of the entries of S in (Ω) A,) n A., for matrices L, that satisfy a suitable condition.
Lemma C.6. Let X = S-" where T.* 2M(n1, n2, T2 k) and the corruption matrix S satisfies Assumption 3 for some known 0 < a < 1. Let the set of observed entries SL follow Assumption P with 2 C log mh for some constant C. Ler L = UV be an estimate of L' such that (U,V) E By-
Suppose that the set of corrupted entries is estimated by A = support (Txa (L - X, with an over removal factor of 1 < S L. If there exists factorization (U*,V*)= B n B. of L' such that
25
- U- +
IV
< 4
L T. 1
(24)
then the magnitude of the remaining corrupted entries in (9) \. A) AA, is bounded follows,
(S( S 18/papprk|] - L' + V I ["
(25)
The last lemma bounds the error term [T. T, [F(A) for a matrix that satisfies a suitable condition.
Lemma C.7. Let L E M(11, n2, r, (4, k) and let the set of observed entries Q follow Assumption 2
with 2 Clog n1, for some constant C. Let L = UVT be an estimate of L* such that (U, E B,
w2 and assume there exists factorization (U*, V*) E B n BB of Lt, If A = support (Tya (A, ()),)).
some matrix A, then
L' S 27 27 37 (IUU U
V VVVV V*
(26)
C.2 Proof of Theorem
The proof relies on lemmas C.I C.7 above. We first note that since Ω follows Assumption 2 with
p > Cue max (log n1, prk² ), we may apply these lemmas. Specifically, for large enough C' the
ne
conditions required by C.1 and C.2 with 2 I. hold and condition of Lemma C.3 holds with
20
e
Proof of Theorem 3.1 We prove by induction on the iteration step that
(Ue, Vi) E Bor
n Boto
n By..
(27)
19

---

RMC + AOP + RPCA- GD *-HOAT
RMC +OOP + RPCA- GD + HOAT
HUB RAMC RGNMA-EE -S RGNMR
HUB + RAMC + RGNMR-BS + RGNMR
10
failure probability
0.8
median error
10
0.6
10
0.2
10
10
12
14 16 18 20
10
12
14
16
18
20
oversampling ratio
oversampling ratio
Figure Results of RMC methods as function the oversampling ratio under diagonal-band pattern sampling- (left) Median rel-RMSE: (right) Failure probability defined as P(re1-RMSE >> 10 10-3). The underlying matrix L of size 500 x 500 has rank and condition number x 2. The fraction of corrupted entries is
5%. Each point corresponds to 50 independent realizations.
Eq. eq. 14 then follows immediately by the definition of Ber, see eq.
Eq. 27 for t follows from the assumption that the initialization is sufficiently accurate, balanced and has bounded row norms (Un, Vo) Bar( 1 ( )B 20r )r Next assume (U,, Vú) satisfies eq. and prove that the updated matrices also satisfy this equation. Since all intermediate steps 1 S < L + 1, (Us, V.) are updated by eq. (10) (U,, V.) E C(U.-I,, Va-1,
o² Pee r B,,- Hence by
Lemma C.4 (U++1, V2+1)= E Botn (
It remains to prove that (U++1, V(+1) Berl2ttio. namely that ||L++1 L' I of The proof consist two parts. First we bound the error restricted to the set Q2 = S \ Ae, i.e. this result to bound the on the entire matrix.
24tlca
||L++1 L (((.))) In the second part
For the first part, to bound || - (l(() we apply Lemma C.5 To this end we first prove its conditions hold. In particular that the set A, B" n B, n (U,, Ves
4tt1 is non empty. Indeed
8
this follows by applying Lemma C.I Specifically, since (Ue, Vi) Bar
2 Bain
n
for a large enough Ce. (U,, Vi) satisfy the conditions of Lemma
C.1 with
Consequently.
20
w.p. at least 2 there exists a pair (U*.V*) E B* n B3 that satisfy eqs.
(9a) and (9bb) with
U U, V V.. Combining eq. (9a) with the assumptions
25
< 5 and
[ I.
of
2
2'c. VR
yields
25
25 o²2
5
I1 - U 1 V
V- 1 <
L,
1
<
<
40;
40 4'ekk
41
Therefore (U*, V*, E E nB, Nc C (U,, V1, /
We now apply Lemma C.5 which gives
||++1 L" (l))) SV2
|AU P())) ||U4+1 A AV.T (F()))
T2
(28)
+ (1 22) S F((CAA))
We upper bound the term Ti, T2 and Tg. The first term Ti is bounded by eq. 19b) of Lemma C.I
with
20
/P I L|FF
Vio;
T = =A=,AU;AV>'I I ||AU;AK <
(29)
120
20-6
20

---

RMC
+ AOP + RPCA-GD + HOAT
HUB AAMC RGNMR-BS RGNMR
1e+00
median error
16-02
16:04
1e-08
1e-10
1e-08
1o:06
1o-04
16-02
standard deviation
Figure 9: Performance of RMC methods in the presence of additive noise. The y-axis is the median rel-RMSB The x-axis is the noise standard deviation. The underlying matrix I size 3200 x 400 has rank and condition number 2. The fraction of corrupted entries is 5%. Each point corresponds to 50 independent realizations.
To bound T2 we note that
- S II V (
T2
To bound the above term apply Lemma C.3
We first show that (AU++1; AV+1) satisfies eq.
21
Since (U++1, V(+1) and (U,, Vi) are Bp then
3pror Th
|AU++1l22 c2 I |10,+1122,00 + Well2,00 <22
4
711
and similar inequality holds for A AV++1 Hence eq. 21 holds with / = o Consequently by eq.
(2
of C.3 with
&JeCk w.p. at least 1
p AU
1 + AVV A
2 2 + |4V++1112)
of
64c
Next we explicitly bound ||
||V P. Since (U--1, V411 E C CU,, Vl, 1r=1
|| + 11AV++1 S म Hence
5
07
82 2. 2.42++2
80
Te VPI
2
S SVD
2 4++1
4
64cmN
128c 4 K
Since 8 <
0.2
oz² S VPV
yp
S vPV E2 24
+
(30)
c2R²
22549
22x2.224433 221+3.8
CevR 2
In order to bound T3 we invoke Lemma C.6l The condition of this Lemma, eq. 24 holds since we proved that (U,, V/)) satisfy eq. (9a) of Lemma C.I employ Lemma C.6 which gives
Since A, support (Ta (Le
X)) we can
2 [a L* [F()))
T3 18 18 pppppprrsl L"Ile
(31)
y
Since (U,, Vi) Ban ( ceev
). for a large enough ce, (U,, Vi) satisfy the conditions of Lemma C.2
with
1 Therefore by eq. 20 w.p. at least 1
3 n
20
2 7 [L L 1 (1+ 2 y
1
2p
3p
|| L* V 7- | L L'
(32)
21

---

RMC +OP RD -HOAT
RMC AOP + RPCA-GD HOAT
HUB -RRMC- + RGNMR-BS RONMR
HUB - RRMC + RGNMR-BS + RGNMR
10
failure probability
median error
10-1
0.8
0.6
10
0.4
0.2
10
10
3
3
condition number
condition number K
Figure 10: Performance of RMC methods as a function of the condition number under both outliers and additive noise. (left) Median rel-RMSE; (right) Failure probability (=1.96 SE). The underlying matrix L is of size 3200 x 400 has rank 5, the fraction of corrupted entries is a 5%, the standard deviation of the white Gaussian noise is 10-6 and the oversampling ratio is 12. Each point corresponds to 100 independent realizations.
Combining eq. (31) and eq. 32) gives,
3
T3 S vp 18
7--1 - |4, - L*
Since a < copret I and by the induction hypothesis
11 - -1:l|r S
then
T3 S vD [88/aurk + V 7-1
3
of
S VDD
18
3
o
Ca
V
Cy
2
For large enough and Cy this yields
Vo
T3
(33)
20 C. va(1
+ 22)
Inserting the bounds on T1, T2 and T3 from equations
29
30
and (33) into eq.
28
gives
Vioa" |1+11 L"IlF(a.)) S 24+1c V
po
(34)
24.5
20.4
2
10
2
Ce V
Eq. 34 provides bound on L++1 L", but only the set Ω4 In what follows show that this is sufficient for bounding the overall error on all entries, [L+1 L|lP. Since Ω4 = Ω \ As then
|L
|| L 1 (())
[
L 1=11)((0))
(35)
To upper bound ||4++1 L (( we apply Lemma C.7 with (U++1, Ve41) which indeed by
their definition in eq. (10). belong to By, and with specific factorization (U*, V*) specified below.
Specifically, show that there exists a pair (U*, V*) )= BB, that is in the vicinity (U++1, V(+1).
By Lemma C.4 (U++1, Ve+1) Bar yoe Bonn (1) B,.. Therefore, for large enough c, Lemma
C.
guarantees the existence of factorization (U* V*) E B n Bμ that also satisfy eq.
19a with
Lit1 = Ut41 VIT11 Hence, by eq. (26) of Lemma
C.7
|[441 - L I1 S 27 37737appro
- U V1 V*
(36)
Combining eq. 19ab and the assumptions a S aoppen
7 eaa gives
[T41 T.'1P(ca (27V3rppur)
1
25 of
[T441 1/
CaHTRE 4 o
= -27V3p)
25
L1+1 1
(37)
4/ca
22

---

RMC AOP RPCA-GD -OOT
RMC +-APP RPCA-GD + HOAT
+UB RRMC - RGNMR-BS RGNMR
HUB RRMC
RGNMR-BS + RGNMR
10
failure probability
median error
10"1
0.8
0.6
10
0.4
0.2
10
10
2
<
16
oversampling ratio
oversampling ratio
Figure 11: Performance of RMC methods as function of the oversampling ratio under both outliers and additive noise. (left) Median rel-RMSE; (right) Failure probability (=1.96 SE). The underlying matrix L of size 3200 x 400 has rank r 5, the fraction corrupted entries is a 5% the standard deviation of the white Gaussian noise is a = 10 and the condition number is 2. Each point corresponds 100 independent realizations.
Next we lower bound (U6+1, Vi+1)= Barl Ve. Buta ) B,.. Hence, for large enough Ce, (U6+1, V++1) satisfies
|[441 I ((
((() we apply Lemma C.2
Recall that by Lemma C.4
the condition of Lemma with
20 By Lemma C.2 w.p. at least 1
|141
L 1 1 2
20
)
Le+1 L -
(38)
Inserting eq. (37) and eq. (38) into eq. (35)
yields
[L+1 L' (P)))
2p
95
2753-25 LV7
|| - 1' p()) [ 11 1'
where the last incquality follows for large enough ca. We conclude that
10
[|++1 [>
V T141 T," I=
9/P
By eq. 34
the right hand size is upper bounded by gotice which implics that (U++1, Vo+1) e Since (U++1, Vi+1) (bnn n B,, was proved at the beginning, (U1+1, V(+1)
Barr
2 c VK
satisfy
27
which concludes the proof.
C.3
Auxiliary Lemmas for Theorem 3.2
The first result is Lemma SM2.7 in (Zilber and Nadler 2022 Lemma C.8. Let Z ( ) Z = (V)) E tx2) Denote
(v2 (U),
+)+ jdp(t', (2)(z dp(Z',
(39)
Then
- - -V < S - VTVl - +
(40)
I |F Sa
(41)
The second lemma is proven by ei al. (2016) as part of their proof of Theorem 3. It bounds the spectral distance of an initial estimate of T," obtained by removing the maggest entries and projecting rank-r matrices.
Lemma C.9. Let X L + S* where L E M(n n,, (1) with singular values of .... o and S* satisfies Assumption for some known 0 constructed according to the jollowing equation,
1. Let L =VV be an estimate of L*
(U.V) b-SVD, [ (Pa(X) - To (Po(X).
(42)
23

---

08
08
08
0.
rank
rank
1.2
0.4
0.4
14
03
14
03
02
0.2
16
16
0.1
fraction of observed entries (%)
fraction of observed entries (%)
(a) RGNMR
(b) HUB
00
0.
07
0.7
0.6
0.5
rank
10
0.5
10
85
12
12
16
81
0.1
18
18
0
fraction of observed entries (%)
fraction of observed entries (%)
(c) RMC
(d) AOP
0.
08
rank
0.5
0.5
0.4
0.4
14
83 14
0.5
02 16
18
fraction of observed entries (%)
fraction of observed entries (%)
(c) RRMC
(f) HOAT
Figure 12: Performance of RMC methods function of the rank and the fraction of observed
entries [0
R2 Deep blue corresponds to 0% failure, white corresponds to 100% failure. The matrix
of size 1000 x 1000, the fraction of corrupted entries a = 10% and the condition number x Each point corresponds to 20 independent realizations.
24

---

(a) Original Image
(h) Sampled Image
(c) RXC
(d) AOP
(e) RGNMR
(I) RPCA-GD
(g)
HOAT
Background extraction for "Hall" video data. The frames recovered from 5% of the original entries with an input rank r
Figure 13:
There exist constant such that if 2 4 ur logni, then w.p. at least 1 between L and L is bounded as follows,
the spectral distance
m1
2cEo VT
| L' S 16auro +
(43)
The third lemma is a direct consequence of Lemma SM2.4 in (Zilber and Nadler 2022).
Lemma C.10. Let L be matrix of rank r and let Z b-SVD,(LL] For any Z that is
perfectly balanced, namely IITTU -VVl 0, it holds that
22r
dr(Z,
LUV
I 1o
(44)
V V(V2 - 1)
Recall the definition of Smit: eq. 16). The following lemma bounds the operator norm of Z b (Pa(X)= - -Sintt] Its proof appears in Appendix D.4
Lemma C.11. Let I= E M(n1, r. with largest singular value oa. Let 7- U
V'
b-SVD,(L*] and Z (U) V
where U, V are perfectly balanced. ISUV L L*llop S o then
1 = (0 S V oo
(45)
In the last step of the algorithm we apply the clipping operator Ra, see eq. (18). The following lemma, whose proof appears in Appendix D.5) state that under some conditions applying the clipping operator with right 1) reduces the Procrustes distance.
( (')
U
Lemma C.12. Let L. E M2, Z- =
b-SVD,[L"] and z =
b-SVD,[A] for some matrix A E RuIxao, If T 1'plop S 4 then for Th
2|lopp
Rm, (U)
122
n2
Z Zllop and Z'
Ropa (V)
it follows that
dp dz(Z', 0²) < dd((Z
(46)
25

---

RGNMR-BS RGNMR
RGNMR-BS RONMR
10
10
10a
median error
median time
10:13
10
10"14
10!
(
10
10:15
500
1000
2000
4000
8000
16000
500
1000
2000 4000
8000
16000
dimension n
dimension n
Figure 14: Effeec of the matrix size RGNMR performance. Both and y axes are log scale. (left) Median run time of RGNMR and RGNMR -BS for a matrix of size n x n as a function of n. The dashed lines have slope of 2. (right) Median Error as function of the matrix size. The matrix has rank r = 5 and a condition number x = The oversampling ratio is p r(2-r) and the fraction of corruption is 5%. Each point corresponds to 20 independent realizations.
|
C.4 Proof of Theorem 3.2
Proof. First we would prove that Lo = VoVo is a sufficiently accurate estimate of L* and that it is balanced. Formally we would like to bound the terms | Uo Vo Volla and | - F... We
U
(Uo
denote Z
b-SVD,[L"] and recall that Zu = Vo
We denote
V*
a a= (V207 + dp Zo. z²)) dr Zo. Z*)
2
Since U* V-T | V
0 and U+ L by eq. 40 and eq. 41 of Lemma C.8
UU0 Up V0 Voll= - 2a.
(47)
L L''l= S
To bound a we need to bound dp(Zo, -²). We do so by showing that by Lemma C.12 dp(Zo, I*) I ("). To apply the lemma we first prove its conditions hold. Specif-
ically we prove that -IUT 1= I 4. Recall that Sinit = Ta (Pa()), and that
2 = b-SVD, | (Pa(X) - Sinst) ]. Since Ω follows Assumption 2 with 2 Curr logni
U
for large enough C, we can apply Lemma C.9 with c
1 By Lemma C.9 w.p. at least 6 m
16.
|UV 1l I 16aprot + 2ceo
oi 8vr
s 16aprot
Vr
Since we assumed a <
for a large enough Ca 2 2
160
+ of
< of
|UVT - L S
can2 /F 8yT 4
Run (U)
Since 771
pT m
Z
op: 172
V
ng
Hr Z op and Zu
(V)
by Lemma C.12
dp(Zo. Zz) < dp(Z,Z").
Hence,
1
a (V20) - -
(48)
2
26

---

Next we explicitly bound dp(Z,Z"), Since Z is obtained using b-SVD,, - -- 0. Therefore by Lemma C.10
2r
dp(2,Z)) <
UVV - lopp
(49)
V(v2 - 1)07
To bound llUVT - L llop we apply Lemma C.9
Since Ω follows Assumption
2 with p
2
C Czur xx logni we can apply Lemma C.9 with
This gives that w.p. at least
VCK²
n
dr dr(2,77) 7*) <
22
16auroo
2ctoj )
3 16Gauuas²
4c VCR.
V(V2 1)0;
/r
Since assumed S
16
4c
Vor
16
4c
dp <3300
3
+
(50)
Cak
VCK
R
Ca
vC)
Denote 5 =
10 Cev
+
Inserting eq. (50) into eq. (48) gives
vC
222
Vo 3 Vorg= of
9 (3/2+
VK
Note that for any > 0 for large enough C, Ca it follows that < E. Therefore for large enough constants 6n and C
of
a S min
CovK' 4ea
Inserting the above bound into eq. (47 gives
(Uo, Vo) E Ban
n Botal
vK
2cr
Ug
Next prove that (Uo, Vo) By,, which requires to bound ||Uoll,, and Vo Since
Vo
Rmm (U)
Rip (v)
by the definition, eq. (18), of the clipping operator Ra
pr
J. 7
1 2,
1
1|
||Vol2,00 2,00 I
1/2
71lop-
722
Since proved that | into the above inequality completes the proof as it gives
L
si
apply Lemma
C.11
Specifically inserting eq.
45
( 11
5 pr mi
3uroi
2
Z
op
711
711
(UVT
50 pr 2 112
3pror
|Vol12,00 5
V
S
n22
712
112
D Proofs of Lemmas C.4
C.5
C.6
C.11
and C.12
D.1 Proof of Lemma C.4
To prove the lemma the following auxiliary result, whose proof appears in Appendix E.1
27

---

Lemma D.1. Let Zi be the estimated factorization after t steps as defined in Algorithm 2 and let Z+41 be the factorization at iteration + 1. Denote
max (I (V:)dd Z,) + [dp( Ze). ar
For large enough constants Ce, the following holds. If (U,, Vo) E
Buta (1tt(1/2cz) (1/2aa)BBB)) BBp
and (U,, V.) E CC(U,-1, Vo-1, P for every S 8 - t + then
20 +
of
a 2 Vce
2 c.r
(51)
Proof of Lemma C.4
We start by proving that (Ut+1, V(+1) Buta (..) By eq. 440 of Lemma C.8
1UZT, VIL Ve+ill S |0, U2 - -V, Voll + 20.
Therefore, by induction
11411 Vi Vi+all S 10 Uo Vol Voll + 2 Σ ok.
(52)
By eq. 51 of Lemma D.I for large enough ce, for each iteration step 0 S k S t
of Oh S
(53)
2
Inserting eq.
53 into eq. 52 gives,
|1 VilVVllll s 110/ Uo Vo_ Voll +
of
26+2
| Uo Vo Voll +
or
201
Since (Uo, Vo)
Buin (1/2c) the above inequality implies that (U++1, V++1) Batn(1/a)
Next, we prove (Uz+1, V(+1) E Ben ). By the triangle inequality
||,++1 4+1
1 F S ||0 V U.V. ll + |U,V, -L
By Lemma C.8 U1e+1 Vita U.V, || a, and therefore,
||0- L"1l S + lUVV L' 1'
By induction it follows that
UU++1 VII1 - 1= S 116VV - 11'l + Σ Okk
(54)
k==
Next use D.I to bound Øg. Note that for ce 2 1 since K 2
4 20 ak I 2 Vce
4 4/20;
4 20
4/20;
+
S
+
2
2.+++ V
2 Vce
2 Vce
2 /Ce
As result of the above inequality
Σ
t
as I
4v20
1
8v20
(55)
/ce
2
Vce
k=
k=
By the assumption (Uo, Vo) E Ban (ovT: inequality and eq. (55) into eq.
follows that ||UVVO L* S o² cov
Inserting this
(4)
gives
10 S of
(8
130
UV+VV
+
ceVR
Vcee
Vce
We conclude that (U++1, V(+1)= E Borl 13
Buu (2).
(e,
28

---

D.2 Proof of Lemma C.5
To prove the Lemma we use the following four auxiliary lemmas, whose proofs are in Appendix
E.2 All of them consider the following setting. Let L, V. and A be the estimates of L and
A. at iteration I, respectively. Let L++1 = U be the updated estimate, where (U++1, V4+1) computed by (TO) with some å O. Denote AU;
U1+1 - U, with similar definitions for AV; and A Denote by S2 = Q \ A, the set of non removed entries, by I S2 A the of non-removed entries which are true inliers and by 1 S4 A.A the set of non-removed entries which are outliers. Finally, recall that for factor matrices (U, V) and subset of entries A the objective function value is
U, U*, AU++1
(U, V) = arg min | +UV, U.V, X((e(A) U.V
Lemma D.2. The error restricted to the set 1 is bounded as follows,
| - L (rrr S L (U++1. Vi+1) + | A AViallress
(56)
To upper bound the first term the RHS of eq. (56 the following lemma.
Lemma D.3. Assume that La is sufficiently close to L in the sense that the set Ar = B3 nB,
8 C (U,, Ve, πUF is non empty. Then
Cip (Ur-1, Vi+1) V441)
S V2Cb, (U", Cip (Ur41, Vo-1),
(57)
for any (U*,V*) E Ar, an exact factoriiztinnno of L*.
To upper bound the RHS of eq. (57) employ the following two lemmas. The first lemma upper bounds the first term and the second lemma lower bounds the second term.
Lemma D.4. For any (U*, ( E
(U*,) |AU,AV; (IF(,.) + [|S))
(58)
Lemma D.5. Under the above assumptions,
Sige (U41,, V4+1) 2|| - I -1' - |U 1 AI
(59)
Proof of Lemma C.5
Our goal is bound [| I," [(())) Since Q = Iin rout
|++1 - L'I( & ||4++1 - L 11r()))))) + |[411 - L 1'((
Lemma
D.2 bounds || - L -=*1
[1t1 1'())(()) SC + ||U (lr(p) + [[44 T." (l
(60)
To upper bound Ci (U1+1, V(+1) we insert
59 and eq. (58) into eq. 57) which yields,
(Ue41, V4+1) S /V2] AV, F())))) + v2 F(O.)
(61)
|AU+ + [I |T+1 I S 1*
Inserting eq. (6 into eq.
160 and using the fact that [| = ||5 |F gives,
J1t1 I. (())))
SV2| AVT
(1 + /21
+ | AV All + AAU++AVV
(62)
+ [T441
I. 11 - [[T I," -5 -
To bound the term A above we note that,
||U AV 1ll + ||AH++ BPrey -VAU 1r
29

---

Using the inequality a a v2va2 - b ba yields
A < /2 AU L AV Ailllo
(63)
By the triangle inequality Inserting eq.
| -1"l (F(()) |1+1 - L' (71(F( S 1|5 1|
(64)
66 and eq.
(64 into eq. 62 gives.
[1 L (F(())))
[v2 (F(O)) ||U AV AVttall
+ (1 + 22) | |F(T")
D.3 Proofs Lemmas C.6 and C.7
Before we prove the lemmas we present three auxiliary lemmas. The first Lemma 10 in (Yi et al. 2016). establishes that if the sampling probability p is sufficiently high, then the number of sampled entries in all rows and columns of Ω concentrates around their expected value.
Lemma D.6. Let Ω C [n1] x [nz] with 2 n2 satisfy Assumption 7 namely its entries are sampled
independently with probability p. There exist a constant C such that if p 2 C log an then w.p. at least
u2
1 uniformally over all E [mi] and j, E [m2]
Ins - 1r2p < p222 loj - pmpl S 2m
(65)
The second result is Lemma 14 in (Yi et al. 2016) provides an upper bound on the error |UVT U* ([F(A) for a sufficiently well spread out subset A of the entries.
Lemma D.7. Let L* have rank r, largest singular value of and decomposition (U", V*) E B, Bp-
Let U E Rux'r V E Ruax* be a pair of matrices, such that (U, V) E B,,. and let 0 E (0, 1). Assume
that C [n1] x [nz)] satisfies AAG,)) S for all i [n1] and (A())) I for all E [mg] then
|UVT U
1P S 18v30rpo (IIU U 1 + V - 1
(66)
The third lemma bounds the impact of the entries in (Ω Ar) n A, on the error term IL, - X ([()) The lemma is based work presented in (Yi et al. 2016 (as part of their proof of Lemma 2), its proof appears in Appendix E.3
Lemma D.8. Let x S", and Z C [n,] x [mz], where the corruption matrix S satisfies Assumption for some known 0 < a of corrupted entries is estimated by A support (Taa (L X, (2)) with an over remvoal factor 1 < 1. Then the error on the remaining corrupted entries (22 A)) where A support(S") is bounded as follows,
< 1. Suppose that for given estimate L of L", the set
2
I XIIF((AAAAAA)) & V 7
|T
1. [[
(67)
Proof of Lemma C.6
By the triangle inequality
|| = I|L - (L* + S - (L L'))l L'))ll((a
< I I 1' + [[[ IT) - S S*(IF(((AAA))))
(68)
Wi
W3
First we bound Wi. To this end note that since Ω follows Assumption with p 2 Lemma D.6 w.p. at least
C
log nu by
122
for every i E [mi] and E [nz] nn
1
Ir: - 1rep - pm,, 1cg - 1m11 I 2 pm.
30

---

By Assumption 3 S E S and therefore
(A.)), ar, ((A)) s acj,
Since (2\) A CA.
[((2) A.) n.)a (Av)aa)) S or; - 2 2
and similarly (())) - oopn Therefore we can invoke Lemma D.7 with 0 = ap to obtain the following bound on W1,
W = |IUV UV ((COAA)A))) & Bly U - + ||V - 12))
Since (U", V*) satisfy eq.
24 it follows that
25
W1 S
27 3o
4o; I - < a8pap L L'|
Next bound W2 in eq. (68 To this end we invoke Lemma
D.8 which gives,
2 [ L 1=
W₂ L L S'IIF((AA)A)))) $
Inserting the bounds on W and W2 into eq. (68) yields eq. (25)
Proof of Lemma C.7 Since Ω follows Assumption 2 with 2 C
log n. by Lemma D.6 w.p. at least n1g
for every [ni] and j [m2]]
1 Ira - pnzll S pm 1e--pm) S pm.
By the definition of Taa eq.
6 for any matrix A, it follows that if support (Tya (A, then
3 (A) S yar; I 7apm2, I(A) sac, S 2 7apn,
3
Using Lemma D.7 with A and 0 = aap obtain eq. 26
D.4 Proof of Lemma C.11
Proof. First we bound (UV By the assumption |UVT - -r S si inequality,
and the triangle
4
a1 (UV 7..
Next we bound |7llop Since U, V are perfectly balanced, there exists E Ruxxx V E Bexx unitary matrices and Σ ggrx diagonal matrix such that
U T= =Ū and VSL.
Note that UVT = ÜYV, and thus σ1 (UVV (E)) In addition, = -UN=UT++VV = 2 Hence,
50
1| = / (1(ZTT) (11(E 2000 $
31

---

D.5 Proof of Lemma C..22
To prove the lemma we use the following auxiliary lemma which Lemma 11 in (Zheng and Lafterty 2016). Lemma D.9. Let E R" be vector such that || S 7/- Then for any x E IK"
[1 y1² < I| y11
(69)
proof of Lemma C.12 Recall that
dz'Z' min -2'- d,(2,2)) min 2 20--PPl Pl
where orthogonal. In what follows we prove that for any orthogonal matrix || - 7' 7'Pl|F S I -" Pl Let P be an orthogonal matrix,
11 +1
| - P1
Σ
Bm (U(+.) (U' P)
Σ
(V(.)) P),)), (70)
In order to bound R - -UU)))((U)))).)))) and [| (Va.)) (V.)) Il using Lemma D.9
we first need to prove that [I(U** P) I m,,1((V* P) I 12. Since I," has an incoherence parameter of j
ppo
THOo
1U V
||
n22
Since we assumed |VT - 10 S <i by the triangle inequality of S 20 (UVT). Therefore
(UVT)
12,00 S
11
n1
21 2ruor((UV) (UVT)
IV
12,,0
S
12
11
By Lemma C.11 22 (UVT)
hence
|00
112.00 S
V
|
llop
= 7/1
n1
||
S
V
||
llop
1/2-
122
Let P be an orthogonal matrix then
|0 p1l2,x < 11 PT lop = | |2,000
| 2, < | PT llop |
12,00
Therefore, |I () $ m. |I(V* (((V*))(e)) () 72- By Lemma D.9
[|,,,, (U(r.) - (U P) < [1a,,)) (U" P).
and a similar result follows for V with 1/2. Inserting these bounds into eq.
70 gives
I - T <
U (U* (U)
Σ
IIaa (V*P) P),)) -
- 2" P1p
i=
Since this is true for any orthogonal matrix it follows that
dr(Z', dp((Z
32

---

E Proofs of Lemmas D.1
D.2
D.3
D.4
D.5 and D.8.
E.1 Proof of Lemma D.1
As part of the proof we use the following lemma, whose proof appears in Appendix F
Lemma E.1. There exist constants ce. such that the following holds. If (Vo, Vo) E Ben 1
n
CoVR
Bbin 2es
n By then
max(o2(Uo).o $2v0;
(71)
Additionally for every 15 1 (U,, V.) C(U,-1, V vc.a then
at
(1 < <4
(72)
Proof of Lemma D.1 Recall that
at = v2 ( Zτ) (Ztt1
Since for every 1 $ t, (U.. E C(U,-1, V-1,, Vo- by Lemma E follows that
(n) < 4 प.. Therefore
$ (v32 of + [dp(Zz, ((+1) dp (z, Ze+1).
Since dp 7(+1) 1 17 - 7 = VlU Upl + |1 Vill we can bound ar as follows.
S (V32(11 - Unl1 + [[V++1 VollA + U
1I -val2.) U.
Since (U,1)) E C (Ur, Vor arfia.))) Hence,
see eq.
(8), |11 Uell + || Vell S 44+1 can""
1320,01
4v20; of
0t v 2 Viace
2 1ak
caK
2 Vce
2 4-41 cak
E.2 Proofs of Lemmas D.2
D.3
D.4
and D.5
Proof of Lemma D.2 We first lower bound Lip (Uz+1, V(+1), the analogue the objective function
eq. 1 on the set Iit By definition Si,5 for every (i.j) E Aç. Since I S A
(73)
Note that
U.V. + U..VV U.V. - - -UVVVt + Un-VV U.V. -U411V
+ (U111 ViTs -I²))
=(L+1 L*) - -UU+1 -V)((V+1- V.)
Inserting this into ??, by the triangle inequality
Ip (U++1, V(+1) 2 |1++1 - L 1'Il - |AU AVTilllT
Rearranging the terms yields,
|+++1 - L ('(aa S (Up41 Vo-1 + ||U,+| AV
33

---

Proof of Lemma D.3 Our goal is to upper bound L/ (U2+1, Ve+1). Since P \ Ar = 1,th U f
[ch, (U++1, Vi+a]] (jet(U Veti)* [ (U142, Ve+1)
Since va² + 1 2 v2 (a+
1 - (U Vi+1) (U2+1 Ve+1)]-
(U,11 Ve+1) 2
12
Rearranging the terms yields,
cip (UL41, Vi+1) v2Ch, (Ut+1, V(+1) L/ (UL+1, V(+1). Note that (U++1, Vi+1) = arg min (U, | (U, V) E Bu ne (Uz, Vo, 2t1)). By definition A B Nc (U,, V,, A Therefore for any (U", V*) Ar.
(74)
(UL+1, V4+1) - Cb, V*). 74 yields eq. (57) of the lemma.
(75)
Inserting eq. (75 into eq.
Proof of Lemma D.4
By the definition of Ch see eq. I since X + S*
S/, (U", V*) = ||U, V - U.V, - L - S*11F(20))
Combining the triangle inequality with the fact that L = UVVUT gives
||U,** + UVV, - U.V,T - U (U*, (U", (*)= <
Il --V'V''TlPpp
|| ||5
= -IUG(V*T - v,J) U- -v-TTT--V -V)))la + ||*
= IAU7AV; + ||S*))(()))
Proof of Lemma D.5
The analogue of the objective function in eq. I on the set 1.tH can be written
cim (Ut+1, V++1) ||U,V, U UVV, L -5- ('((1(17)))
= I1 U,+IV, UVV, -U++1Vita) + (U141V - S*)) lrare
= [I](L+1 L- - SS*) - (V)) 1
Note that the second term AU,AV. Hence eq. (59) follows by the triangle inequality.
E.3 Proof of Lemma D.8
Proof. We denote by u, and uy the i-th row and the j-th column of Pa(L - L*), respectively, We denote by u: (k) the element of un with the k-th largest magnitude, and similar definition for uf As A support (Tra (L 2)), for any (i. Ω A
(k).
(),a) S max {|I-- X) X) || x) 1
(0,)
(76)
By ussumption 3 S* e S there are at most ar; corrupted entries in the éth row. Since y > 1, the set of [yar]] largest entries in the ith row of Pn X) contains at least [(y 1)aryl non
corrupted entries. Therefore, the [yrr;] largest entry in the ith row of PatLT X) is smaller than the [(> 1)or;] largest entry in the ith row of Pa T.*). Formally
[[L - x ([zar:1)
< [[>-1)]|[
(c.))
(77)
The same argument can be applied to each column j. Inserting eq. (77 and the analogous inequality for the jth column into eq. (76) yields,
(L - X)isl max {|u,) [(-- 1)=-1)
[[--- 10-
(78)
34

---

Next we upper bound
un
(y-
To this end note that,
[(7 1).r
((--))arii
||u, = Σ 24
22
(u, 12 2
u
(0- 1)mm
2 (7
1) rs 2
(1--1)an 1)rr:
Therefore.
[(7 - 1)nn
2
|4,1
u;
(79)
(7)
1)ar
The same argument can be applied to
Inserting eq. (79 into eq. 78 gives
|1:11
|
(): (7 - 1)am
+ (7 - 1)acy
Summing over the entries (2) \ A) n A. yields,
|L (I-IIP((OAAAAAA
1
E
||,11
(7 1)a
(1.))(
rb
Cj
Since (52 A A...
|u:|l
|00113
[ - XIPr(ai))).)) S
( 1)a (iS))A.
Cj
|uill
1|2
Σ
( - 1)a
Ta
Cj
[E(m)) JEA...))
jE(ma)
iEA
By the assumption S S it follows that |An(i-)) S ar, and A. S acj. Therefore,
| - X(PP((OAAAAA)) $ ( 1)a
a Σ ||ul1
Σ ||
(E(ng]
jE(mal
2
7- |PPa(L 1')
|| L 1'
Taking the square root both sides completes the proof.
F Proof of Lemma
In our proof would use the following lemma from Zilber and Nadler (2022) [Lemma SM2.4).
Lemma F.1. Let L" T x be matrix of rank r, and denote Z" b-SVD,(L*). Then for any
Z (V) taa
dFZZZZ)) < (V2 1)0; (IUVT-L"M) L - -
(80)
Proof of Lemma inequality
E.
We prove for U, and Ug. A similar proof follows for V2 and Vo. By the triangle
a So) + 110+1 Uellop
Hence by induction
t Σ
(V.))
|l Ukllop S (U)) + Σ |l++1
Unlle.
(81)
k=0
k=
35

---

Since (U++1, Vx+1) E C(Uk: Vss qo of noTio see eq. (8),
of
of
1
||U++1 UkllF S V @4tllco
|
CeVK
2k+1
2k+1
Therefore for 2 1,
|lx+1 - U&ll S
of
of
Vo
S
Vo
(82)
C
2
CoVR
k=
k=0
Next we bound 01 (Ug).
Denote Z"
V-
bL") By our assumption (Uo, Vo)
Berr
5 Bbin
Therefore by Lemma
20z
Zo. 2*)
o oj.
(83)
(v2-1)
16o7
Let P Pbe the minimizer of the Procrustes distance between Uo and U Note that 00
(Un) - a1 OU(UP)) By Weyl's inequality
(U)) - 01 (U*))) 5 110 U' Ploop S 11U6 - U P dp(Up, U*) S do Z²).
Hence (Ug) 01 (U*) dp dZ Z²) By the triangle inequality and eq. 83
σ1 (U)) (U*) + dp (Zo = 2//1.
(84)
Inserting eq.
82 and eq.
into eq.
(T completes the proof.
36

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction summarize the theoretical and empirical contri- butions that are proven and illustrated in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper clearly states the assumptions made for our theoretical results, and the parameter regimes which our empirical results were generated. In the end of Section we pointed out the limitations of our theoretical analysis.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
37

---

Answer: [Yes]
Justification: In section [ we provide the full set of assumptions. The proofs for all of our theoretical results appear in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: In section 4 we provide a detailed explanation of the experiments conducted in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
38

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide open access all code used to generate the experimental results that appear in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc.
cablic/guuddes/Codeuubbsss wtw.ooeeSsubiissiooooooooooogg for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wwtp:/cccppppgguuuiiaeoeae
Stteee///ooSSSSeissSioica www.ssssiicggcooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: section we provide a detailed explanation of the experiments conducted in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Error bars are illustrated as part of our figures. A detailed explanation of the the results is given.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
39

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We describe the hardware and memory requirements needed in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification: Our research adhered to the Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
40

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The original owners of code used in the paper are all properly credited and cited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
41

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: All code is well documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
42

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
43


Reviews:
[{"review_id": "u3q5KxmAs0", "reviewer": "Reviewer_zeEZ", "summary": "A new method for robust matrix completion, RGNMR, is introduced to overcome the limitations of existing methods. It is empirically shown that RGNMR has significant advantages when only a limited number of entries is observed, and, moreover, that it copes well with both overparameterization of the rank and with ill-conditioned matrices. Besides, it is shown that RGNMR recovers the underlying matrix exactly under suitable assumptions.", "questions": "- Is there a connection (formal or intuitive) between the estimation procedure of the corrupted entries in Alg. 1 and Alg. 2? \n- Does this scheme for updating $\\Lambda_t$ in Alg. 2 also work decently in practice? Or is there a (significant) gap between theory and practice?\n- Could you attribute the observed properties of RGNMR to either the estimation procedure of the corrupted entries, or to the Gauss-Newton based method GNMR? What is the contribution of each of these to the overall method?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper is well-written; ideas are clearly presented.\n- The numerical results look promising.\n- A theoretical analysis reveals that RGNMR recovers the underlying low-rank matrix exactly under suitable assumptions, and improves upon the best-known results for factorization-based methods.\n\nWeaknesses:\n- There is a discrepancy between the method that is theoretically analyzed, and the one that is used in the experiments. Although not uncommon in this field, I believe it would strengthen the paper if the authors could explain in more detail the connection between Alg. 2 and Alg. 1. \n- The main novelty of RGNMR is the procedure for estimating the number of corrupted entries $k^\\*$, which is then combined with the (existing) GNMR scheme. As mentioned in Remark 2.2, various existing RMC methods require an estimate of $k^*$, and therefore they could be equipped with a similar scheme. This raises the important question whether such an approach may yield a performance similar to that of RGNMR.\n\nTypos:\n1. Line 28: Remove / rephrase `both’, since it is followed by three adjectives\n2. Line 76: RGNMR performs well on real data\n3. Line 166: The vertical pipe for “such that” is doubled\n4. Line 188: Maybe good to explicitly define the support?\n5. Inconsistency: over-removal versus over removal\n6. Line 266: The remain open directions\n7. Line 472: The subscript init should be upright\n8. Line 583: Eq. eq. (14) -> Eq. (14)", "was_revised": true, "final_justification": "This paper presents interesting theoretical results for robust matrix completion, provides promising numerical experiments and is well-written. It seems that the main concern of some reviewers is the practicality of the work. While I understand and can even follow some of these concerns, it is my opinion that this is still a strong paper which deserves to be accepted. Finally, I would also like to mention that I appreciated the adequate rebuttal of the authors.", "rebuttal": "We thank the referee for their constructive feedback and suggestions. We first answer their three questions and then reply to other issues raised. \n\n**Q1 :** [Connections between Alg.1 and Alg. 2]: In both Alg. 1 and Alg. 2  the estimation procedure of the corrupted entries is based on the magnitude of the residual entries. \nThe method employed in Alg. 2 is based on the assumptions made on the corrupted entries, which facilitate deriving theoretical guarantees. Specifically, \nunder Assumption 3, the fraction of corrupted entries in each row and column is bounded. Hence, it makes sense to remove only a bounded number of entries from each row and column.\nAccordingly, Alg.2 removes the largest $\\gamma \\alpha$ residual entries in each row and column.\nHowever, without any assumptions on the corruption pattern, a more general approach is to remove the largest residual entries across the entire matrix, as employed in Alg.1.\nWe will clarify this in the revision. \n\n**Q2 :** [Alg.2 in practice] This is a great question. \nAs mentioned above it make sense to use the scheme of Algorith 2 to detect the outlier entries only under Assumption 3. \nFollowing the referee's question we tested the performance of RGNMR combined with the scheme of Alg. 2. \nThough this method is far less successful than our proposed one it still works decently.\nSpecifically, it successfully recovers a $500\\times 500$ matrix of rank $5$ and a condition number of $10$, with an oversampling ratio of $12$ and **1%** fraction of corrupted entries. \nThis makes it competitive with other RMC methods, which fail to recover such ill-conditioned matrices. \nWe will discuss this in the revision. \n\n**Q3:** [ Properties of $\\texttt{RGNMR}$]\nThe fact that  $\\texttt{RGNMR}$ performs well on ill-conditioned matrices, with a small number of observed entries and under overparameterization should be attributed to the optimization step, which updates $U$ and $V$ simultaneously and globally.\nOther optimization schemes, such as gradient based schemes, have been shown to perform poorly under these conditions even when no entries are corrupted.\nHowever, we would like to clarify that  $\\texttt{GNMR}$, as well as many other low-rank matrix completion methods, is not robust to the presence of outliers. \nIt may fail miserably even in the presence of very few corrupted entries. \nTherefore, the estimation procedure of the corrupted entries is crucial for the method success.\nWe will clarify this in the revision, and also add a figure showing the failure of GNMR in the presence of outliers. \n\nOther issues: \n\n- **Novelty/Estimating number of outliers:** \nWe agree that our scheme to estimate the number of outlier entries is an important and novel component of  $\\texttt{RGNMR}$. However, accurately estimating the number of outliers is not sufficient. \nSpecifically, as mentioned in P9 L297-301 of our manuscript, and illustrated in the simulations, even though we provided $\\texttt{AOP}$ and $\\texttt{RPCA-GD}$ with the exact number of corrupted entries, they still perform poorly in comparison to  $\\texttt{RGNMR}$ and  $\\texttt{RGNMR-BS}$.\nWe will clarify this in the revision."}, {"review_id": "fFONnNF0eZ", "reviewer": "Reviewer_J6k5", "summary": "This paper addresses the classic problem of low-rank matrix completion in presence of outliers. It is noted that previous robust matrix completion (RMC) algorithms fail when the number of observed entries in the measurement matrix is relatively small, the low-rank matrices ($U$ and $V$) are overparameterized or the condition number is small. To mitigate these shortcomings, the authors propose an alternation-based algorithm whereby the outlier-corrupted elements are estimated in each step and subsequently excluded from estimating the decomposed matrices.  Since this involves estimating the number of outlier-corrupted entries ($k$) in each iteration, the authors test two versions, i) the oracle case whereby $k$ is known (RGNMR) and ii) the binary search scheme implemented to find an upper bound of $k$.\nThe authors present a theorem (Theorem 3.1) to provide recovery guarantee under certain assumptions such as small enough fraction of outliers and large enough number of observed entries. The theorem is supplemented by numerical simulation results using largely synthetic data (except for the background extraction example) demonstrating improved performance compared to competitors under various scenarios changing oversampling ratio, fraction of outliers, overparameterized rank, etc.", "questions": "1. I wonder if Figures 1 to 3 are drawn assuming some degree of additive noise in each observed entries (like in Fig. 7) or only consider the effect of gross outliers. (In practical viewpoint, assuming no or very little additive noise can be very rare.)\n\n2. I wonder if the authors have tried out various challenging different visibility patterns besides uniform sampling and power-law sampling (Meka et al., 2009) techniques. For instance in structure-from-motion in computer vision (Tomasi and Kanade, IJCV 1992), the visibility pattern of the observation matrix can often be diagonal if the underlying motion of the camera is circular. I wonder if the algorithmic convergence would be severly affected by the ``diagonal-ness'' of the visibility matrix as for other algorithms such as Damped Wiberg/Variable Projection (Okatani et al., Damped Wiberg, ICCV 2011, Hong et al., Revisiting Variable Projection..., CVPR 2017)\n\n3. Since RGMNR is only tested on matrices with comparatively small fraction of outliers (0 to 25%), I wonder if this method would outperform approaches based on non-graduated convexity in which the width of the robust kernel is gradually narrowed in each iteration (e.g., see Le et al., A Graduated Filter Method for Large Scale Robust Estimation, CVPR 2020 --- this is not a paper handling LRMF but a similar technique could be applied).\n\n4. In l. 259, it is reported that RGMNR succeeds even from random initialization. Does this mean all elements of $\\Lambda$, $U$ and $V$ are sampled from a particular probability distribution? What is the assumed underlying distribution? I am asking this because from my experience, I feel the convergence would depend significantly on how $\\Lambda$ (the predicted outliers) is estimated but is not discussed in the paper.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "[ Strengths ]\n\n- Clarity: the paper is mostly comprehensible despite use of heavy math notations.\n- Results: experimental results largely support the claims made in this paper and is mostly superior compared to the competing algorithms.\n- Reproducibility: Supplementary code is provided for review.\n\n[ Major weaknesses ]\n\n- Limited motivation: While it is true that low-rank matrix factorization (LRMF) still serves as a baseline model for recommender systems, it is subsequently being more replaced by deep models that are able to capture nonlinear relationships between the user traits and item traits (e.g., Li et al., A Survey on Deep Neural Networks in Collaborative Filtering Recommendation Systems, arxiv). The paper would benefit from a more concrete motivation of why robust low-rank matrix completion is still an important problem (cited works in l.20 are already 4 to 9 years old).\n\n- Novelty of the proposed method: In terms of the algorithmic structure, RGNMR is largely based on the work of GNMR (Zilber and Nadler, 2022) for estimating decomposed matrices. The only major difference is in re-estimating the corrupted entries in each iteration of the algorithm.\n\n- Practicality of the experimental settings: One area where LRMF can still accel compared to deep networks is where the observation matrix ($L$) itself is very large but the number of observed entries is very small (e.g. Bennett et al., The Netflix Prize, Proceedings of the KDD Cup Workshop 2007). Nevertheless, evaluations in this paper is limited to largely synthetic observation matrices of relatively small sizes (3200 x 400). I am not entirely sure if such experimental setting would support the usefulness of this algorithm for real-world applications, e.g. in (large-scale) recommender systems.\nAnother major weakness in my opinion is that, as demonstrated in Fig. 7, the performance of the (non-oracle) RGNMR-BS is not stronger than others even when the standard deviation of the additive noise is sufficiently small (1e-6 or greater). In practice, additive noise and gross outliers usually occur simultaneously and thus should be the default testing ground in my opinion. \n\n- Runtime and/or algorithmic complexity is an essential component for practical consideration but is not compared against other algorithms.\n\n- Missing connections to other literature: The approach of subsequently improving the set of inliers is similar to the concept of  graduated non-convexity (e.g., Sidhartha et al., Adaptive Annealing for Robust Averaging, ECCV 2024) but is not discussed in the related work.\n\n[ Minor weakness ]\n\n- It seems the positions of figures are slightly unsynchronized compared to the location of paper contents. Perhaps Figures 1 to 3 could be moved to the latter half of the paper? Also, the paper in its current form is not self-contained within the 9 pages limit --- many essential experimental results (e.g. Fig. 7) are in the supplementary material.", "was_revised": true, "final_justification": "After considering the paper, reviews and discussions with other reviewers, I am upgrading my score to ``borderline accept'' primarily based on the strength of the theoretical contribution (new recovery guarantee and an estimator for the number of corrupted entries). That said, my practical concerns remain: the non‑oracle variant can lag under simultaneous noise+outliers, experiments are mostly small/synthetic, and runtime/complexity are not compared against fast baselines (e.g. against IRLS-based approaches). During author-reviewer discussion, the rebuttal offered only promises to add larger‑scale experiments, diagonal‑band sampling results, and runtime analyses, but no new evidence or figures were provided, so my confidence in the practical value has not increased.\n\n**For camera‑ready**, including the promises made in the rebuttal, please move the essential experiments into the main paper (simultaneous noise+outliers; non‑uniform/diagonal‑band sampling) and clarify the initialization procedure for the decomposed matrices.", "rebuttal": "We thank the referee for their constructive feedback and suggestions. We first address the weaknesses raised,  and then answer the referee's questions. \n\n## Weaknesses:\n\n### Motivation:\nWe agree with the referee that in recommender systems, matrix completion methods are not state of the art. We will mention this in the revision. \nDespite having been considered for more than 20 years, matrix completion and its robust variant are still important problems in data science. \nBeyond classical applications in computer vision, they are still applicable and used in several contemporary fields, including single-cell analysis in biology **[1]** and sensor networks **[2]**, for example.\nIn addition, as noted by numerous recent citations in the manuscript, robust matrix completion is an active field of research in statistics and machine learning.\nWe will include a clearer motivation for low rank matrix completion in the revision.\n\n**[1]** Lejun et al, SeqBMC: Single‐cell data processing using iterative block matrix\ncompletion algorithm based on matrix factorization, IET Systems Biology, 2025. \n\n**[2]** Wu, Di, et al. \"Robust low-rank latent feature analysis for spatiotemporal signal recovery.\" IEEE Transactions on Neural Networks and Learning Systems (2023).\n\n\n### Novelty: \nWe agree with the referee that the proposed method $\\texttt{R$\\texttt{GNMR}$}$, can be viewed as a relatively simple combination of outlier removal with the existing \nscheme $\\texttt{GNMR}$. Two major novelties are: (i) a non-trivial method to estimate the number of corrupted entries; and (ii) a theoretical recovery guarantee, which improves the state of the art for factorization based methods. \nWe will clarify these points in the revision. \n\n### Practicality of the experimental settings: \nIn the main text, indeed \nresults were presented for matrices of size $3200\\times 400$. \nHowever, please note that \nin Fig. 10 in supplementary of our original submission, we applied $\\texttt{RGNMR}$ to  matrices of size up to $16,000 \\times 16,000$. \nNamely, $\\texttt{RGNMR}$ can be successfully applied to much larger matrices.\nIn the revised version, we will add simulations comparing $\\texttt{RGNMR}$ to other methods for such large matrices.  \n\n### Additive Noise:\nFig. 7 compares the reconstruction error of various algorithms in the presence of both outliers and small additive noise. However, the setting here was chosen so that other methods will succeed, specifically \na small condition number $\\kappa=2$,  a high oversampling ratio $\\frac{|\\Omega|}{r\\cdot(n_1+n_2-r)} = 12$, a small fraction of outliers $\\alpha = 5\\%$ and all methods were given the correct rank.\nChanging one of these parameters, for example increasing the condition number to 10, causes most other methods to have an $O(1)$ error, at any noise level. In contrast,  $\\texttt{RGNMR}$ and $\\texttt{RGNMR-BS}$ maintain an error proportional to the standard deviation of the noise.\nTherefore, $\\texttt{RGNMR}$ is a competitive method even in the presence of additive noise. \nWe will add figures to illustrate this in the revised version.\n\n### Runtime and/or algorithmic complexity:\nThanks for raising this important issue. Some matrix completion methods, such as those based on gradient descent are very fast.\nIn comparison to such methods, \n$\\texttt{RGNMR}$ is indeed more computationally demanding. \nPlease note that in Figure 10, we did study the runtime of our method as a function of matrix size. As mentioned in the main text P9, L309, the compleixity of $\\texttt{RGNMR}$ emprically scales as $O(n^2)$. Moreover, \nas illustrated in Fig.10 its runtime on a standard PC remains reasonable even for large matrices (several minutes for a $16k\\times 16k$ sized matrix). \nImproving $\\texttt{RGNMR}$ runtime is an interesting problem for future research. \nWe will add a discussion of these issues in the revised version.\n\n### Missing connections to other literature: \nWe thank the referee for pointing this out and we will discuss it in revision. \n\n### Missing essential results from the main text:\n In revision, with an additional allowed page, we will make the manuscript more self contained, in particular moving some of the figures from supplementary to the main text.\n\n## Questions \n### Q1:[Additive noise] \nIndeed, Figures 1 to 3 correspond to simulations with outliers but otherwise no additive noise. In the revision, we will clarify this issue and add figures with a small amount of additive noise (beyond the outliers). \n\n### Q2: [non-uniform sampling pattern of observed entries]\nThanks for raising this interesting issue. Following the referee's question, \nwe ran $\\texttt{RGNMR}$ and several other methods mentioned in our paper, in a setting where the observed entries are concentrated in a diagonal-band pattern as in **[1]**. \nIn this setting, all tested methods require a higher number of observed entries to succeed. Yet, $\\texttt{RGNMR}$ still significantly outperformed the tested competing methods even in this case. \nIn the revision, We will add a comparison between the different methods under this non-uniform sampling pattern.   \n\n**[1]** Okatani, Takayuki, Takahiro Yoshida, and Koichiro Deguchi. \"Efficient algorithm for low-rank matrix factorization with missing components and performance comparison of latest algorithms.\" 2011 International Conference on Computer Vision. IEEE, 2011.\n\n### Q3: [graduated non-convexity approaches]\nOne of our initial attempts to solve robust low rank matrix completion was to develop a method that iteratively reweighted the effect of potential outliers. Specifically, we\nreplaced the least squares objective to update the factor matrices by an\nIRLS scheme.\nSince this requires employing an IRLS algorithm for every update of $U$ and $V$ it is very computationally demanding. \nIn addition, the performance of this approach was not promising. Hence, we developed the method presented in our manuscript, that detects outliers and removes them completely. \n\n### Q4: [Initialization]\nTo randomly initialize  $U_0$ and $V_0$ we generated two random matrices $Z_1\\in\\mathbb{R}^{n_1\\times r}, Z_2\\in \\mathbb{R}^{n_2\\times r}$ \nwith i.i.d. entries distributed as $N(0,1)$.\nWe then set $(U_0, V_0) = (\\tilde{U_1},\\tilde{U_2})$ where $\\tilde{U_i}\\tilde{\\Sigma_i}\\tilde{V_i}$ is the SVD of $Z_i$.\nWe set $\\Lambda_0$ as the $k$ largest residual entries in $U_0 V_0^\\top - X$. We will add these details in the revision."}, {"review_id": "kUA0MIjWGZ", "reviewer": "Reviewer_dKUj", "summary": "This paper introduces a new method for robust matrix completion with strong theoretical guarantees. The algorithm can be described in the following: For robustness, a set of $k$ indices $\\Lambda$ is maintained and used to track the estimated outliers based on the largest residual entries. For matrix completion, a factorization method based on a gauss-newton linearization on the factors is used (GNMR by Zilber and Nadler 2022), where only the set of indices $(i,j) \\not \\in \\Lambda$ (or the estimated \"inliers\") are used to update the factors. \n\nFor the outlier indices, $$\\Lambda_{t+1} = \\arg \\underset{\\Lambda \\subset \\Omega, |\\Lambda| = k}{\\min} \\|\\|U_t V_{t+1}^T + U_{t+1}V_t^T - U_tV_t^T - X\\|\\|_{F(\\Omega \\setminus \\Lambda)}^2$$\n\nFor the update of the factors, \n$$(U_{t+1}, V_{t+1}) = \\arg \\underset{U,V}{\\min} \\|\\|U_t V^T + U V^T - U_tV_t^T - X\\|\\|_{F(\\Omega \\setminus \\Lambda_t)}^2$$\n\nSince the number of outliers $k$ must be estimated, the authors also propose a simple yet interesting binary search scheme with justified intuition. \n\nThe authors provide recovery guarantees for a slightly modified version of the proposed method. The first theorem establishes the fact that given a sufficiently accurate balanced initialization with bounded row norms, which are relatively standard assumptions, the modified algorithm recovers the true matrix with high probability and linear convergence rate. The recovery guarantees has small sample complexity, and holds the weakest conditions for factorization based methods. \n\nThe second theorem establishes the possibility to construct an accurate enough initialization under suitable conditions, such that the recovery guarantee's assumptions can be satisfied. This initialization's success depends on the fraction of outliers to be slightly lower than other algorithms. \n\nThe authors also provide a set of simulations comparing against other robust matrix completion methods and demonstrates the effectiveness of the proposed method.", "questions": "1. Can the authors provide some insight as to how to choose the rank for the factorization in practice? If possible, can a set of small experiments be added to show the effects of overparametrization? I understand that the time is short, but even a small set of experiments may help. \n\n2. How different are the solutions of RGNMR-BS and the normal variant of RGNMR? Under what conditions may they vary much and how much does it affect the runtime? Are there cases where BS takes a long time to find the correct k and greatly affects the quality of the solution and runtime? \n\n3. Including a set of experiments comparing RGNMR directly with the original GNMR without the robust mechanism may be helpful to understand and validate the effectiveness of the simple robust mechanism. \n\n4. If I recall correctly, GNMR had different variants according to some change of variables. In the experiments for RGNMR, was there a specific variant of GNMR that worked better than the others?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n\nThe paper provides a simple yet effective algorithm for robust matrix completion, mainly making good use of the existing results from GNMR (Zilber and Nadler 2022). Performance is good compared with other RMC methods with strong theoretical guarantees (especially sample complexity and fraction of outliers for the recovery guarantee), and experiments on a real computer vision dataset is included. The paper is presented in a concise and clear manner. \n\nWeaknesses: \n\n1. I don't see significant novelty in the work, as it mostly relies on the existing work GNMR, which was simple and had strong theoretical properties. The paper's main contribution employs a simple robustness mechanism similar to existing methods to an already powerful matrix completion algorithm. \n\n2. Including a set of experiments comparing directly with the original GNMR without the robust mechanism may help me to understand the true effectiveness of RGNMR. It is unclear to me how effective the robustness mechanism actually is. \n \n3. In applying factorization methods in general, the rank used for the factorization is always difficult to choose. Even for applications where the true rank of a certain matrix under noiseless conditions are known, it may still be difficult, as the best rank to use for matrix completion may be higher than the true rank due to noise and corruption. The authors didn't fully discuss the affect of rank in the factorization and \"did not consider the case of overparametrization\", and this may limit the practicality of the proposed method. \n\n4. The initialization procedure in theorem 3.2 improves the sample complexity of existing works, but requires a lower fraction of outliers. It is possible that the initialization procedure doesn't provide a sufficiently accurate initialization when data is highly corrupted. \n\nIn equation (1) between lines 106 and 107, a square is missing for the norm of the residual.", "was_revised": true, "final_justification": "I believe that the paper is a good and interesting in the field of robust matrix completion. The main strengths of the paper is that there is strong theoretical properties of the algorithm proposed, despite the simple extension of the methodology. \n\nMy concerns about some details of the practicality, including the estimation of the rank through citing that the method is not sensitive to overparametrization and the option to test different ranks as the input, and initialization through citing that the proposed method works well under random initialization, have been mostly resolved. I am interested to see some of the additional experiments mentioned in the rebuttal in the main paper or the appendix of the paper. \n\nThe reviewers all agree that the practicality of the algorithm is still a bit unconvincing, but I believe that the paper has already showed potential through their strong theory and their numerical experiments, and this work should be introduced to the community. I would recommend an accept for the paper to the main conference.", "rebuttal": "We thank the referee for the constructive feedback and valuable suggestions. We first address the concerns raised, followed by responses to the specific questions.\n## Weaknesses\n### No Significant novelty in the work: \nWe respectfully disagree with the refeee's assessment that our manuscript has no significant novelty.\nOn the methodological side, \nwe agree that the proposed method $\\texttt{RGNMR}$, can be viewed as a relatively simple combination of outlier removal with the existing scheme $\\texttt{GNMR}$. \nHowever, our manuscript contains at least two significant results: (i) a non-trivial method to estimate\nthe number of corrupted entries; and (ii) a theoretical recovery guarantee, which\nimproves the state of the art for factorization based methods.\nDeriving these recovery guarantees for $\\texttt{RGNMR}$, does not directly follow from the existing guarantees for $\\texttt{GNMR}$, which hold only without outliers. \nFurthermore, the recovery guarantees we were able to derive for $\\texttt{RGNMR}$\nimprove upon those of other RMC factorization based methods in terms of the fraction of corrupted entries. We view this as a significant theoretical contribution. \n\n### Comparison to $\\texttt{GNMR}$:\n$\\texttt{GNMR}$ is a non robust method. Like many vanilla matrix completion methods it may fail completely in the presence of even a small fraction of corrupted entries.\nWe will illustrate this in the revision.\n\n### Overparameterization:\nThe referee is correct that overparameterization is an important issue when employing factorization based methods.  \nFor this reason we discuss overparameterization in several places in the manuscript, see for example Figurew 2 as well as Lines 50-67 \"Limitations of existing RMC methods\".\nSpecifically, Fig.2 illustrates\nthe performance of $\\texttt{RGNMR}$ under overparameterization and show that it  is in fact the only method, out of those tested, that succeeds in this case.\n\n### Initialization: \nIndeed, the proposed initialization procedure\nyields a highly inaccurate initial guess when the data is highly corrupted. \nHowever, this does not pose a major problem for $\\texttt{RGNMR}$, as empirically $\\texttt{RGNMR}$ succeeds even from a random initialization.\n\n### Additional notes: \nThe square is not crucial but we will add it for clarity, thank you for noting that.\n\n## Questions:\n### Q1: [Rank estimation]\nFirst, we note that in various applications in computer vision, the rank of the underlying matrix is known [1]. \nThat said, \nthe referee is correct that in many applications the rank of the underlying matrix is unknown.\nThis does not pose a significant challenge for our approach, since \nas illustrated in Figure 2, $\\texttt{RGNMR}$\ncontinues to work well even under overparametrization. For example, for an underlying matrix of rank $r=5$, $\\texttt{RGNMR}$ succeeds if its input rank is $r=10$. In short, our method only needs a reasonably tight upper bound on the rank. Another option is to simply run our algorithm with several input ranks. We will discuss this in the revision. \n\n\n[1] Okatani, Takayuki, Takahiro Yoshida, and Koichiro Deguchi. \"Efficient algorithm for low-rank matrix factorization with missing components and performance comparison of latest algorithms.\" 2011 International Conference on Computer Vision. IEEE, 2011. \n\n\n### Q2:[$\\texttt{RGNMR}$ VS $\\texttt{RGNMR-BS}$] \nThere are indeed settings where accurately \nestimating $k^*$ is difficult. In such cases, $\\texttt{RGNMR-BS}$ may fail to recover the matrix, whereas $\\texttt{RGNMR}$ (given the exact number of outliers) may still succeed. \nThis occurs, for example, when the fraction of corrupted entries is quite large, as illustrated in Fig.5 in the Appendix.\nThe difference in runtime between $\\texttt{RGNMR}$ and $\\texttt{RGNMR}$-BS is illustrated in Fig.10 in the Appendix.\n\n### Q3: [$\\texttt{GNMR}$ VS $\\texttt{RGNMR}$]\nWe will include such simulations in the revised version. \n\n### Q4: [$\\texttt{GNMR}$ variants] \nIn $\\texttt{RGNMR}$ we employ an optimization step similar to that of the setting variant of $\\texttt{GNMR}$. This variant worked best. We will mention this in the revision."}, {"review_id": "qfUuzl38NM", "reviewer": "Reviewer_hYb1", "summary": "This paper addresses the problem of matrix completion with corrupted (and unobserved) entries. It proposes to use a Guass-Newton linearization step and outlier removal to improve the assumptions needed for accurate reconstruction. They provide theoretical guarantees for their method and show through experiments that it does well even in challenging settings.", "questions": "1) Per the discussion above, could a remark after (2) be added to enhance some intuition?\n2) How sensitive is the approach to parameter selection (i.e. number of corruptions, \\mu, \\alpha...). Remark 3.2 only states this is a common assumption, but are these practical issues or not?\n3) Perhaps 2) could be addressed by some sensitivity experiments (dare I say ablation experiments) if they can't be addressed by other works?", "limitations": "They discussed limitations in the problem approaches.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The problem is well-motivated and the various challenging settings identified. The theoretical guarantees are clear, transparent, and well-explained. I found the entire paper to be very clear and forthcoming.\n\nFigure 1 -- in the caption, it would be helpful to describe what is meant by failure probablity (since the paper studies the robust version, what is failure?)\n\nRemark 2.1 -- what is meant here by runtime savings? It seems that doing additional updates would increase runtime -- is it that the small increase in runtime is far outweighed by the improved convergence (and if so, perhaps this could just be rephrased). \n\nPerhaps a remark after (2) could be added to enhance some intuition -- given that the hope is that this approach allows for a lower number of non-uniformly sampled entries yet also removes outliers, it seems on first glance that it is very possible for the samples to \"miss\" some directions, making those appear as outliers. In this case, the method actually does itself more damage, but further trying to ignore those directions. Can some intuition be discussed here about this case (rather than waiting for the theory below)?", "was_revised": true, "final_justification": "After thoroughly reviewing the responses, other reviews, and reviewer discussions, my rating is at an Accept. As discussed in several other places, there are some practical concerns but I believe this to be a nice contribution on the theoretical side.", "rebuttal": "We thank the referee for the positive feedback and constructive comments.   \nWe first address the concerns raised, and then respond to the specific questions. \n## Weaknesses\n\n### Definition of failure: \nTo avoid repetitions in the captions of all figures  we defined failure in Line 60 of the manuscript.\nAs this seems to have been missed, \nin the revision, \nwe will add this to the caption of the figure as well. \n\n### Remark 2.1: \nWe agree with the referee that Remark 2.1 should be made clearer and we will do so in the revision.\nYes, the small increase in runtime is far outweighted by the improved convergence. \n\n### Intuition to Equation (2):\nThanks for the suggestion. We will add an intuitive explanation \nfor why Eq. (2) is an effective approach to detect outliers, and does not miss signal directions. \n\n## Questions\n### Q1:[Remark after equation 2] \nWe will add such a remark in the revision. \n\n### Q2+Q3: [Parameter selection] \nOur practical algorithm is parameter free and so these are not practical issues.\nA way to select the number of corrupted entries is discussed in Section 2.1 of the manuscript. \nThe parameter $\\mu$ can also be estimated [1].\n\n[1] R. Sun and Z.-Q. Luo, Guaranteed matrix completion via non-convex factorization, IEEE Trans. Inform.\nTheory, 62 (2016)"}]

Author rebuttal:

Meta-review: The paper suggests a new method for robust matrix completion (which is a combination of the matrix completion and robust PCA problem), building on the recent GNMR algorithm from 2022.  This new method is better at handling outliers, and also takes care of over-estimating the rank.

Reviewers all liked it, especially for having good theory (assumptions are reasonable) as well as good practical performance.  The writing quality was also sufficiently high.

The topic itself is relevant to a good portion of NeurIPS readers

Overall, it seems to be a solid paper and on an interesting topic, hence I'm pleased to recommend acceptance.
Decision: Accept (poster)