Fast exact recovery of noisy matrix from few entries: the infinity norm approach
Authors: BaoLinh Tran
Van Vu
Venue: NeurIPS 2025 poster ()
Keywords: Matrix Completion
Matrix Perturbation
Recommendation System
Random Matrices
Primary area: theory
TL;DR: We show that exact recovery in the noisy Matrix Completion problem can be achieved under the basic assumptions without the need for a small condition number or large singular value gaps, using novel techniques that can be of independent interest.

Abstract: The matrix recovery (completion) problem, a central problem in data science, involves recovering a matrix $A$ from a relatively small random set of entries. While such a task is generally impossible, it has been shown that one can recover $A$ exactly in polynomial time, with high probability, under three basic and necessary assumptions: (1) the rank of $A$ is very small compared to its dimensions (low rank), (2) $A$ has delocalized singular vectors (incoherence), and (3) the sample size is sufficiently large. Various algorithms address this task, including convex optimization by Candes, Recht, and Tao (2009, 2010), alternating projection by Hardt and Wooters (2014), and low-rank approximation with gradient descent by Keshavan, Montanari, and Oh (2009, 2010). In applications, Candes and Plan (2009) noted that it is more realistic to assume noisy observations. In such cases, the above approaches provide approximate recovery with small root mean square error, which is difficult to convert into exact recovery. Recently, results by Abbe et al. (2017) and Bhardwaj et al. (2023) on approximation in the infinity norm showed that one can recover $A$ even in the noisy case, provided $A$ has bounded precision. However, beyond the three basic assumptions, they either required that the condition number of $A$ be small (2017) or that the gaps between consecutive singular values be large (2023). These additional assumptions conflict, with one requiring singular values to be close together and the other suggesting they should be far apart. It is thus natural to conjecture that neither is necessary. In this paper, we demonstrate that this is indeed the case. We propose a simple algorithm for exact recovery of noisy data, relying solely on the three basic assumptions. The core step of the algorithm is a straightforward truncated singular value decomposition, which is highly efficient. To analyze the algorithm, we prove a new infinity norm version of the classical Davis-Kahan perturbation theorem, improving an earlier result in (2023). Our proof employs a combinatorial contour integration argument and is entirely distinct from all previous approaches.

Fast exact recovery of noisy matrix from few entries: the infinity norm approach
BaoLinh Tran and Van Vu Department of Mathematics Yale University
New Haven, CT 06511
1. tran@yale, edu and van vu@yale. edu
Abstract
The matrix recovery (completion) problem, a central problem in data science, involves recovering a matrix from relatively small random set of entries. While such a task is generally impossible, it has been shown that one can recover A exactly in polynomial time, with high probability, under three basic and necessary assumptions: (1) the rank of A is very small compared to its dimensions (low rank), (2) A has delocalized singular vectors (incoherence), and (3) the sample size is sufficiently large. Various algorithms address this task, including convex optimization by Candes, Recht, and Tao (2009), alternating projection by Hardt and Wooters (2014), and low-rank approximation with gradient descent by Keshavan, Montanari, and Oh (2009, 2010). In applications, Candes and Plan (2009) noted that it is more realistic assume noisy observations. In such cases, the above approaches provide approximate recovery with small root mean square error, which is difficult convert into exact recovery. Recently, results by Abbe et al. (2017) and Bhardwaj et al. (2023) on approximation in the infinity norm showed that one can recover A even the noisy case, provided A has bounded precision. However, beyond the three basic assumptions, they either required that the condition number of A be small (Abbe and Fan, 2017) that the gaps between consecutive singular values be large (Bhardwaj et al., 2023). These additional assumptions close together and the other
conflict, with one requiring singular values suggesting they should be far apart. It is thus natural to conjecture that neither is necessary. In this paper, we demonstrate that this is indeed the case. We propose a simple algorithm for exact recovery of noisy data, relying solely on the three basic assumptions. The core step of the algorithm a straightforward truncated singular value decomposition, which is highly efficient. To analyze the algorithm, we prove new infinity norm version the classical Davis-Kahi perturbation theorem, improving earlier result in (Bhardwaj et al., 2023). Our proof employs a combinatorial contour integration argument and entirely distinct from all previous approaches.
1 Introduction
1.1 Problem description
A large matrix A E mR= is hidden, except for a few revealed entries in a set 12 C [m]] [n]]. We call Ω the of observations or samples. The matrix Ag, defined by
(Aa);j A. for (i,j) E Ω and otherwise. called the observed or sample matrix. The task is to recover A, given Ag- This is the matrix recovery (or matrix completion) problem, central problem in data science that has received significant
(1)
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

attention in recent years, motivated by number of real-world upplications. Examples include building recommendation systems, notably the Netflix challenge [i reconstructing a low-dimensional surface based on partial distance measurements from a sparse network of sensors 2 3 repairing missing pixels in images 4 ; and system identification in control [5]] See the surveys by Li et al. [6 and
Davenport and Romberg for additional applications.
Researchers have proposed two models: (a) Q is sampled uniformly among subsets with the same size, or (b) St has independently chosen entries, each with the same probability p. called the sampling density, which can be known hidden. The models are interchangeable in mathematical analysis through simple conditioning trick 4 Most papers use (b), and we will do so in our paper. Very recently, researchers have also explored models where the sample entries are correlated [8 these are beyond the scope of this paper.
In this paper, we focus exact recovery (to find all entries exactly). For this problem make sense, is important to assume that A has a fixed precision, namely all entries of are integer multiples of a positive constant e. (Otherwise, is impossible even write down an entry exactly, let alone compute it.) In most practical contexts, does not depend on the size of the matrix. For instance, in the Netflix problem, all entries are half-integers, so E 1/2. If all entries have two decimal places, then e = 0.01.
It has been pointed out by Candes and Plan [12 that in practice, data is often perturbed by noise, so we can only observe a partially hidden and noisy version of A. The main goal of this paper is to find an exact recovery for A from such a noisy sample.
1.2 Basic notation and assumptions
Throughout this paper, A is an m x n matrix, with N == max(m, n}. Consider the SVD of A = UEVT= = = ", " where r := rank A, and the singular values are ordered: σ1 2 02 2 2 o,. We write A, Ei= ",u,y, for the best rank-s approximation of A. An important parameter that appears in many papers in this area is the condition number of A: == = k(A) == 01 0
The coherence parameter is given by M4 (o(A) (xx)) where
11 ml 11103,3.00 Te(m]
m m(U) = max
(2)
and analogously for vV)). The 2-to-0o norm of matrix M is given by || sup [Mu]] ||u]|2 = 1]. It should be noted that || is simply the largest 1.2 norm among the rows of M.
We use C' to denote a positive constant, whose value depends on the context. When C' depends on set of parameters a1, ....... Ok, we write C(a1, .2,...,,ay ax).
In most existing works on matrix recovery, researchers make the following three assumptions
Low-rank:
One assumes that r := rank A is much smaller than min(m, nJ. Many papers assume r is bounded (r O(1)), while m, n 00.
Incoherence:
One requires that the rows and columns of A are sufficiently "spread out", so the information does not concentrate in a small set of entries, which could be easily overlooked by random sampling. In technical terms, one needs μu to be small.
Sufficient sampling size/density: The sampling density (or the size of Ω) is sufficiently large. To ensure all rows and columns are sampled, one needs |S2| 2 CN log N. We will typically work in the regime [ = N log 0(1) N, which is optimal up to a logarithmic term.
These assumptions have been shown to be necessary; see 13 7. and have been used in most papers on exact recovery. We will refer to them the basic assumptions.
In the noisy setting, we observe entries from A + Z, a noisy version of A, where Z represents the noise matrix. Most studies assume that Z has independent entries with mean 0, but not necessarily from the same distributions. In many papers directly related to our work, it was assumed that Z has bounded entries with probability 1. We will do the same here but note that we can replace this with weaker conditions, such as the entries of Z having light tails (via a standard truncation trick). We let An,z := (A + Z)Q denote the noisy observed matrix.

---

1.3 A brief summary of existing results and our contributions
There is a vast literature on matrix completion. The problem of exact recovery in the pure (noiscless) case, under the three basic assumptions,
first solved by Candès and Recht [13), Candès and Tao [4]. Recht [14], using nuclear norm minimization (NNM), which seeks to find the matrix with the smallest nuclear norm that satisfies the observed samples via semidefiite programmingg (SDP). Their idea is based on convexifying the intuitive but NP-hard approach of minimizing the rank given the observations. However, the best-known solvers for the SDP run in time ((12 which is O(N log* N) in the best case ( and the calculation may be sensitive noise 4. Therefore, it is reasonable to seek faster and more noise-robust algorithms, potentially sacrificing some generality.
In Hardt and Wootters (15). Hardt [16], the authors offered another intuitive but Narhard approach: minimize [ & subject to rank A r. and proposed an approximate solution with alternating projections, which switches between optimizing the column and row spaces, given the other. In Keshavan et al. 17 18), the authors proposed taking a low-rank approximation of Ag via SVD, then using initial value for GD-based algorithm to approximate A. In both approaches, it is important that the condition number A be small. See 19 Section A] in the supplementary appendix for more detailed discussion of the role of in these results. See also 23.
Recovery with noisy data, while more practical, as pointed out by Candes and Plan 12 in their influential survey, is clearly harder problem. The authors of the methods discussed above all extended their studies to this case, achieving approximate solutions with guarantees in the Frobenius norm. However, it seems very difficult to turn these approximations into exact recovery.
Recently, there has been progress in achieving exact recovery in the noisy case by Abbe and Fan 24 and Bhardwaj et al. 25 with simple and fast algorithms. The basic idea is to show that a properly chosen low-rank approximation of the observed (noisy) matrix, under an appropriate assumption, approximates the ground truth matrix A in the infinity norm, with error less than e/2. where is the discretization unit of the entries of A. Once this is achieved, a simple rounding off recovers A exactly (see the last few paragraphs of Subsection [.I.. The heart of the matter is the analysis of the algorithms, which requires new mathematical ideas, as proving approximation in the infinity norm is significantly more challenging than similar task under the Frobenius spectral norm.
In what follows, we denote by Ag,z z the matrix obtained from the observed entries of A Z. This is the input of the recovery algorithm. Beyond the three basic assumptions (see Subsection 1.2), these new works require an extra spectral assumption that either the condition number is small 24 or the gaps between consecutive singular values are large 225]
These assumptions are strong, and it is unclear how often they hold in practice. Figure 1.3 below is based on the Yale face database, a well-known and frequently used dataset; see Wainwright's book (26). The data matrix in TR. 17766 is created by flattening 165 greyscale 243 320 facial images into row vectors in 77760
decay quickly, resulting and centering them by subtracting the average row. The singular values rather large condition number; K 10.45 for the first 30 singular values. Consequently, the gaps between singular values are generally large, but there are still exceptions (for example, at index 15).
First 30 singu lr values
Singular value gaps from 10 to 30
5000
120000
4000
100000
3000
00000
2000
40000
1000
20000
10
15
20
25
30
0
5
10
15
20
Figure The Yale face database spectrum and spectral gaps
3

---

From a mathematical viewpoint, we observe a curious phenomenon: these two extra assumptions are seemingly contradictory. The first (small condition number) indicates that the singular values should be close to each other, while the second requires them to be apart. It is thus natural to conjecture that neither of these conditions necessary.
In this paper, we prove this conjecture. We show that a properly chosen low-rank approximation of An,z approximates A (with the required precision) in the infinity norm, using only the three basic assumptions. This not only provides a mathematically satisfying answer but also significantly expands the range of applications (regarding real datasets).
Our analysis of the algorithm is based on novel mathematical developments and is entirely distinct from previous approaches. It combines the contour integral method introduced in Tran and Vu [27] with a novel bound on random matrix powers, in a fairly nontrivial manner. This approach is robust, and we believe in its potential for future applications.
New results: a unifying exact recovery method
2.1 Formal setting and algorithm
To state the algorithm and our main result, let us restate the setting for clarity.
Setting 2.1 (Matrix completion with noise). Consider the gound truth matrix A, the observed set Q2 and noise matrix Z. We assume: (1) || KA for known parameter KA; (2) we know an upper bound maxx 2 r, without needing to know r; and (3) the noise Z has independent entries satisfying E [Zag] = and E [Z
K2 for all 1 N for known parameter Kz, without necessarily having the same distribution or variance. The parameters т, , maxx, KA. K can depend on m and n.
Algorithm 2.2 (Approximate-and- -aund 2). Input: the m x n sample matrix Aq,z and the dis- cretization unit of A's entries.
1. Empirical rescaling: Let p = (mn) |/2|| and p= 'n,
2. Low-rank approximation: Compute the truncated SVD Å Arma Eisrmes Ōyüstif
Take the largest index s S Tmax such that ô, - 0z41 2 20(KA + K2) Cmax (m+
If no such exists, take s = Tmax Let A, := Eis. O,
3. Rounding off: Round each entry of Å, to the nearest multiple of e. Return A.-
Compared to the algorithm Approximate-and Round used in 25 a minor difference is that we use an estimate ý of p. which is highly accurate with high probability. Another innovation is a different threshold for the truncated SVD step that does not require knowledge of the parameter Po. From complexity viewpoint, our algorithm is efficient, consisting of a truncated SVD on a matrix with [22] non-zero entries, and a rounding step, requiring only 0( + mn) O((r + 1)mm) FLOPs.
Our main theorem below provides sufficient conditions for exact recovery with this algorithm.
Theorem 2.3. There is universal constant C> > O such that the following holds. Suppose Tmax
log² N. Under the model 2.1 assume that the signal is sufficiently large,
Tmax N p
||||| = a 2 100r
for K == Kn + Kzi and the sampling is sufficiently dense,
1 ++1] max m
13 K22 1+
H log" N
} logo N.
p z
log N,
(3)
E²
Then with probability 1 O(N- the low-rank approximation step of Approximute undd--uuull----uuullll 2 recovers every entry of A within an absolute error e/3. Consequently, if all entries are multiples integer of the rounding-off off step recovers A exactly.

---

As promised, our result unifies [24] and 225 assumptions. Furthermore, our result also implies a RMSE recovery with the same error margin with no constraint on the condition number, an improvement over 17 18 15
removing both the condition number and the gap
2.2 Analysis of the result
We begin with small experiment showcase the performance of the algorith. Each of the 13 datapoints corresponds to a pair (m, n) that is either (2', 2'-1) or (2',2) for - 10, 11,...,
.....,,, 16.
The matrix A E R is randomly generated by Ao XY", where X E RRxx and Y R with iid NN,, 1) entries, then == Aloollloolll oe The noise matrix Z is generated with Zo E R=** having iid (0, 1/4) entries, then set Zi sgu((Zo)<) max[1/4, (Zo) This normalization makes KA* + Kg = 3/4 + 1/4 = For the sampling, we fix 0.1 in all datapoints.
In Figure 2 the plots show N- + on the horizontal axis, on log scale, and the RMSE and infinity norm errors on the vertical axes. Both decline rapidly with N. In the last datapoint, where m = 2 = 6000, one can recover every entry of A to within an absolute error of 0.1.
Root mean squared error
Infinity norm error
0.125
0.8
0.100
0.6
0.075
0.050
0.4
0.025
0.2
104
105
104
105
Figure 2: The RMSE and Infinity norm error of our method
Next, 1et us discuss the optimality of our result from a theoretical view.
Remark 2.4 (A high-level explanation for the thresholding rule). Note that the observed matrix, rescaled by 11, is perturbed version of the original matrix, since
E [pp
Aq.z] p (E [n] + [[])== A.
Therefore, one can write p -n, = - independent entries. One can view E a type of "noise" that includes both Z and the noise caused by the random sampling. Since is a well-known fact random matrix theory that || = O(Kz ((Kv/N/p) (see (28 29 for proofs), we simply want to cut off the singular values of Á at a level above || as the well-documented BBP phenomenon 30 35 shows that the part of A below that is fully absorbed by E and becomes indistinguishable from noise. Under the assumptions we make, the signal extracted from the spectrum of À above this threshold is a good approximation of A. We use the argument in Remark 2.5 to show the necessity of the lower bound d1
+ E. where is a random matrix of mean and
plus that ||A|] = di is large In our theorem, we use only the three basic assumptions of Section 1.2 enough. This last assumption seems new, but it is not. It is often hidden in previous papers, and is guaranteed by the fact that has low rank. Indeed
of = ||ll 1 2 IA
Consider the representative case when |AI1 Amm)). Then 01 2 2-2/1AA 2 oV density condition and the condition Tmax < log² N, we have
By the
> Fimax K2 N log" N
2 mn (log² N)rK
T Tmax N
p
5

---

so the assumption on di in our theorem is automatically satisfied.
Remark 2.5 (Necessity of the signal assumption). From the engineering perspective, it is intuitive that o1 should be large enough in order for any kind of recovery to be possible. In the opposite case when the intensity of the noise Z dominates the signal A, then the data is "too corrupted" and all interersting information are lost. Rigorously, the well-documented BBP phenomenon in random matrices (3) states that, if [| 2 c|| c||A||| = co), for a specific constant C, then A + Z is indistinguishable from fully random matrix, leaving no chance to recover A even if A + Z is fully observed. Since it is also well-known fact in random matrix theory that || O(Kz ((zzv// N/p) (see 228 29] for proofs), the condition in Theorem is simply 0j 2 Cr Cr|| 211. which optimal when
(1).
Remark 2.6 (Optimality of the density bound), The condition (3) looks complicated, but in the base case where O(1), KA Ky 01), and uniformly random singular vectors, so that we have H40 = Olog N), it reduces to
p 2 C' max flog* N, 5-2} (m + +n " N.
(4)
which is equivalent to [2]] > CN log N max{ = in the uniform sampling model. The power of N is optimal the theoretical limit (see Section I.2). The power of log N can be further reduced but the details are tedious, and the improvement is not really important from the pratical view point. For recovery with precision E, this bound grows with E-2, which is comparable or better than all previous works (see [19] Section A)).
Remark 2.7 (Relaxing the bound on Tmax). The condition Tmax S log N in Theorem 2.3 can be avoided, the cost having a more complicated sampling density bound, which connects p and
p P
+ 12
max log 10 N, e Fmaxg 2 x2
y k2
1
2 log N
)1
y log N N
log N}. (5)
m
The proofs of Theorem 2.3 and Eq. will be in the supplementary appendix, 19 Section B] This shows that our result does not require any extra condition besides the mandatory large signal assumption.
In Section 3] we give a proof sketch for Theorem 2.3 asserting the correctness of our algorithm, Approximate-and-Roumme 2] The proof will boil down to obtaining sharp bound in the infinity norm for the perturbation of the low-rank approximations, for which we introduce Theorem 7 By reframing the problem from matrix perturbation perspective,
view Theorem as an infinity
norm version of the classical Davis-Kahan- Wedin theorem.
We next explain the main ideas behind its proof, which combine the contour integral technique of Tran and Vu (27 (with necessary adjustments) and a novel semi-isotropic bound on powers of a random matrix. The (rather complex) detailed proofs will appear in the supplementary appendix, [19 Section CJ.
3
Main ideas of the proof
3.1
The matrix perturbation perspective and the rise of the extra assumptions
Consider A, - A.. Let p= : P/p and A= p1 An. -'' Å, we can write
A A
Å, A -
1)A+ + (A, A) + (A, A.).
We show that the three error terms on the right-hand side are small in the infinity norm. The first is easy, since p is close to 1 (by Chernoff bound, see e.g. Hoeffding (36)). For the second, we have
A|A A, $2++1
Σ
dun ||__
S |0.
S
r0
Vmm
which will be small by the way we choose s and the incoherence property. Most of the heavy lifting goes to bounding the third term, Í| Aslloo.
Observe that E[Ag] p4 and E [Zal 0, so that E[Å] = p- EE + Zal A. Therefore, : À A is random matrix with mean 0. This opens a way to use tools and ideas from random matrix theory in the analysis.

---

The approaches in [24 25] both arrive at bound on I|A, A, oo. but at the cost of their respective extra assumptions. We give brief overview of their methods.
Suppose & = r = for simplicity, one can write
Å1 A 61 010100 01 of ouu1of (ō1 )uuufff + to ( unef)
= (Aoi)uuzt + (i(())) + ti + oi (Aw))
where we set Ao == 01 01 and analogously for other A A-notations.
By Weyl's inequality. Ao1l - ||]], so the first term is bounded by || || El] in the infinity norm. The main challenge to bound the middle two terms, which dominate the last one. By symmetry, let us focus on (wm )uf. We have
||o (1(( )oi o 20 or loll
If oi large enough compared to |ا [25] showed that the error Auj sufficiently "spread out", namely, Auill I All uill To bound || ll. the classic Davis- KaarisKahha--a Wedin theorem gives Awull S Cl the final bound this term looks like
37
||o (Aui)uflle S Clolalloo//oe llo |E|-
Putting everything together, one obtains the desired (optimal) bound
Cyo
| - A1llx S /1
|B||
(6)
Vmn
When extending this argument to rank 8 > 1. and 25 used two different approaches. In 224 the authors wrote
A, - A, U, + (AU.)E,V +AV) (AU.)),(AV))
The problem here is that ||E,|| is still or (instead of J.), which eventually leads to the appearnce of the condition number x = 01/a, in the final bound. Furthermore, the algorithm in (24) requires knowledge of the rank of A. This is often not the case in practice. However, Keshavan et al. 17 showed that one can estimate r precisely with high probability, given that O(1). Thus, the assumption that the condition number is small needed here for two different reasons: to compute the rank and to improve the quality of the bound; see also
Again, needs to bound [| ((UU))
19
Section A].
25
circumvented this issue by considering
Å A₂ = [oraū,o7 - - ((00))=((aa A(a,uu))))
i
then bounding each term A(auuu?)) separately. Again, this boils down to bounding [|ar(An; )o? |l For this, they (stronger) variant of Davis-Kahan theorem proved in O'Rourke et al. [39 (see 19 Section BJ). As trade-off, this approach requries the assumption that the singular values a; are well-separated for the (stronger) Davis-Kahan bound hold.
Our new method, which is entirely different, allows us to avoid both assumptions. Let us first establish the quantitative statement:
Theorem 3.1. Consider a deterministic matrix E Raxn and a random matrix E mm with independent entries satisfying E [Eey] 0 and E [ < p' K for some K > 0 and
1.
Let A+ E. Let E [r] be an index satisfying
8, = o. 5+41 2 40r /N/P.
There are constant C, C1 such that. i 2 C(m-1 + + - log N (where N max(m, n)), then
[| Axlloo < Cilpo + log N) log rds
KVN /zyp
Kog N
r" log
Vmn
S./D
pd.
From Eq. 7 one can verify, with a routine computation, that the sampling density condition 33). with sufficiently large constant implies Í Ag S e/3, which proves Theorem 2.3. For detailed proof of Theorem 2.3 see [19 Section B].

---

3.2 Our new approach: contour integrals and bounds on random matrix powers
Let us now elaborate on our new approach used to prove Theorem
We begin with the contour integral argument, adopted from the technique by P. Tran and Vu [27]. Instead of analyzing A,- - A, directly, we turn to their symmetrized versions. Denote
B 0
B
B
any matrix B, we have A.g = Agm + E Note that the symmetrization preserves the spectral norm and transforms the singular value decomposition into the eigendecoompoition
Agg WAWT
Σ |E
oww;o
where for each i E [r].
14 U/4
U1
w-
0-1 =- -06-
2
V2
The first key idea here is to compare A.m and A. via their Stieltjes transforms. Let be a complex variable, we have the expansion (we pretend that convergence is not an issue for now)
=(=1 Amgm)) =(=1 A Agm)
Σ = [=I Agm) Engn (zI Agn)
we integrate both sides over a contour H, which encloses only the eigenvalues fa, |i| E [s]}, obtain, by Cauchy's 's integration theorem (and some light calculation).
of zdz [(II 11ma
(A. Az).m Σ
1'(( (2I Enym
Apm
2Tí Sr.
Using the formula (zm = Merr (2(2- -o:)) -w;w +2 II we can expand the right-hand side (via some calculations) to obtain
(Ag - Aa) = Σ Σ C(s,,,,.... +) uw w. E w. w.w." 1 Wy W.W: E
7=1 ,.....
where the asterisks stand for integer variables, i.e. w. can be any wi, E can be any positive power of Exgms and C is scalar coefficient of the form
zd=
C(*,*,..** * C(+,,,...,,) Jr. 2τi 2- (.)- 0.)
There are conditions on these variables, but we will overlook them for now. At this point, one can bound IÅ, A, by bounding the terms above and applying the triangle incquality. These bounds are Fairly technical and require some delicate combinatorial and analytical consideration. This is essentially the approach introduced in (40
Since we aim for the infinity norm, which much harder to deal with than the spectral norm, we need significantly modify the above argument.
us consider, example, the [1ppppe left corner) entry of the matrix in question. We have
(Å, A.)
Σ Σ * ((.,**....,++))) (eT+11 W.) (w E w.w, w w E W.) (wz Ex e1),
7
where G1, c2, standard basis vectors in N The upper left entry of matrix M is of Me,, but notice that we use em+1 on the left due to the symmetrization.
To bound || A - Asl we need strong bound on ex F w. for all indices j. To this end, we prove new semi-is -initiiotoopic bound for powers of E,u. which is a key technical contribution of this paper.

---

These bounds take advantage of the fact that E' has independent entries. The exact bounds are bit technical, but for the simple case when po = O(1, they take the form
C Colo N
po++log N
L for 1 1 S m,
lej E wil 2
Cllog N
Ao log
E
for m + 1ssjs N.
By setting a O, one can also see that these bounds optimal, up to log N factors. Plugging these bounds into the expansion, one can eventually obtain the bound of Theorem 3.1 1. by modifying the steps from [27] in a proper manner. This is, in itself, challenging task, and we provide the full detailed proof in the supplementary appendix
19
Section CJ.
Note that there have been similar isotropic-style bounds for powers of random matrices, notably by Mao et al. [4 and Fan et al. 42]. They both cover a wide range cases, but were designed optimally for the use cases in their respective papers. In the supplementary document [99] Section B),
we will briefly explain that they are not strong enough in our use case.
Besides the bound on the perturbation of low-rank approximations, we obtain similar bounds for the perturbation of singular vectors, both the infinity and 2-t0-00 norms, For instance, we can show
C'log² N(Po + log N)
||
r r|UTEVII 8,
|ū.0 -U5--UUU0 -U, 10 I
m
(Po + log N)
||li||
U||UT EVI
10.0, -UU 112,00 S Colog
m
8
under the assumptions of Theorem 3.1 We will use these bounds in future paper.
3.3 Summary and roadmap for the rest of the paper
We started with the famous and influential matrix completion problem (Section I.I its three basic assumptions. Next, we discussed the the noisy setting, which is more realistic (Section 1.2] and focused on recent results concerning exact recovery [24] 25] (Section I.3p. These results require extra assumptions the spectrum of the ground matrix. On one hand, these assumptions and thus significantly limit the application of these results on real data sets. On the other hand, they, quite intriguingly, seem to contradict each other from the mathematical view point. This leads to the conjecture that neither is needed.
rather strong
We next introduced our own result, which provides an efficient algorithm without requiring the above mentioned assumptions (Section[]. showing that the conjecture is correct. This algorithm obtains exact recovery under only three basic assumptions, and is the first such algorithm for noisy data. In the (easier) noiseless case, the only algorithm using only three basic assumptions is that of Candes et al. [13 14], which is based on convex optimization. Compared to this algorithm, our is simpler and faster, as it uses only on round of low rank approximation. (Low rank approximation is known to be an efficient operator, used very often in practice.) Thus, our result makes a contribution in the noiseless case as well.
which guarantees the correctness of our algorithm. This, in essence, is a matrix perturbation bound, and can be seen as an infinity norm variant of the classical Davis-Kahan theorem.
Our main theorem is Theorem 2.3
In Section we sketch the proof of Theorem 2.3 We started with the sketch of the arguments of 24 25 and showed why their extra assumptions are required. Next, we describe our new approach (Section 3.2). which combines the contour integration method intorduced in [27] with novel semi- isotropic bounds for random matrix powers. This approach avoids the use of the extra assumptions in earlier papers. Over all, this has led a highly non-trivial, but robust and powerful, machinery to obtain matrix perburtation bounds in the infinity norm. We believe that this method will have many other applications.
The supplementary appendix 19, separate from the main body, will contain four sections.
In 19 Section A] we dive deeper into the technical bounds of other matrix completion papers, including 24 25 and the RMSE recovery papers, pointing out the strong assumptions they use (which mostly requiring the condition number of the ground matrix to be small), and demonstrate

---

that we do not need those assumptions. Another point of interest is the sample size needed to recover A with precision E (or within RMSE E), which should grow with 1/e. We demonstrate that our growth factor, which is 1/s", _,,, is on par with the best of these results.
Consider the simple setting where Kz = O(1), po (log N) and = O N). Table summarizes the advantages have over the main methods discussed in this paper.
Method
Entry-wise recovery?
Time Complexity
Extra assumption to achieve optimal sampling bound
Convex Optimization
Candes and Plan
No
0(122 n)²)
Not optimal
Low-rank aрprox. with grad. descent cleaning up
Keshavan et al.
No
0[12[r= mn + Lr(m + n)), if one chooses L iterations for the clearning step
Condition number is small
Single-step low-rank approx. with singular value thresholding
Abbe
Yes
0( + mn)
Condition number is small
and Fan
Bhardwaj et al.
Yes
0( + mn)
Every singular value gap is large
Our method
Yes
0(12[r+ mm)
None
Table I: Comparison of methods for noisy matrix completion
we introduce our main technical machinery behind the proof of Theorem 3.1 We will fully shift the context to matrix perturbation, and introduce new notation be used throughout the ensuing discussion and proofs. We will have one main theorem for the contour integral method
In 19, Section B].
19
Theorem B.2). another for the semi-isotropic bounds 19 Theorem B.4] and corollary of
their combination 19 Theorem B.6] We then use this theorem to prove Theorem 3. then prove
Theorem 2.3 with Theorem
In 19 Section CJ, we provide the full proof's of the main technical theorems. To assist the readers, these proofs come with their sketches. In particular, the proof sketch of [19 Theorem B.2] will be a more detailed version of the sketch in Section 3.2 All details will be presented, barring some cumbersome technical lemmas.
Finally, in [19, Section D], we prove the technical lemmas. The details are heavy, but we hope that the revealed intution earlier will significantly help the readers follow the proofs.
Acknowledgments and Disclosure of Funding
The research is partially supported by Simon Foundation award SFI-MPS-SFM-O00066 SFM-00006506 and NSF grant AWD 0010308.
References
[1] Robert M. Bell and Yehuda Koren. Lessons from the netflix prize challenge. SIGKDD Explor Newsl., 9(2)755-7, 12 2007. ISSN 1931-0145. doi: 10.1145/1345448.133. 1345465. URL https:///aat http://///oooo///../// 1111111411110 1345448. 1345465
[2] Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995. ISSN 0209-9683. doi: T0.1007/BF01207555
[3] Anthony Man-Cho So and Yinyu Ye. Theory of semidefinite programming for sensor network localization. Math. Program., 109(2-3):367-384, 2007. ISSN (20-556610,1436-4666 doi:
1..1007/110107-006-000... URL httphttps:.. http:////...o.....////.001111110
10

---

[4] Emmanuel J. Candès and Terence Tao. The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inform. Theory, 5665) 2080, 2010. ISSN 0018-9448,15577 1557-9654, 2010 2044061
doi: 10.1 1099/TT:20110204440000
URL
[5] M. Mesbahi and G. P. Papavassilopoulls. On the rank minimization problem semidefinite linear matrix inequality. IEEE Trans. Automat. Control, 42()):239 1997. ISSN 2018-9286,118 1558,1155-2555 2523. doi:
probemm over positive
URL http/tpp///bbo...g//00...1
554402
[6] Xiao Peng Li, Lei Huang, Hing Cheung So, and Bo Zhao. A survey on matrix completion: Per- spective of signal processing, 2019. arXiv preprint
10885
[7] Mark A. Davenport and Justin Romberg. An overview low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics in Signal Processing, (0(4):608-622, 2016. doi: N0.110///TSPP220225599000
[8] Anish Agarwal, Munther Dahleh, Devavrat Shah, and Dennis Shen. Causal matrix com- pletion. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Con- ference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 3821-3826. PMLR, 12-15 Jul 2023. (RLLptts://proooedaio agarwal23c.85 html
mlr press/v19//
[9] Anish Agarwal, Devavrat Shah, Dennis Shen, and Dogyoon Song. On robustness of principal component regression. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL /ttp::///rrooceedingg .wwrgip........... hcc/paperffiles//eeeeeeeeeeeeeee 2019:/11000222222111176777766663
Paper pdf
[10] Anish Agarwal, Devavrat Shah, and Dennis Shen. On model identification and out-of-sample prediction of principal component regression: Applications to synthetic controls, 2023. URL Sctps://arxil: org/ abs/2010. 14449 14449
arXiv preprint https://arx:st /ttpsv///axvvv.e/ hrgg://ww.i.o/gg//e///// wwtp:/r//////////////// ab1/2010
[11] Anish Agarwal, Devavrat Shah, and Dennis Shen. Synthetic interventions, 2024. URL https //arxiv.. wwwooogggbaooe aba/abbs//000 07600060766111 arXiv preprint
[12] Emmanuel J. Candès and Yaniv Plan. Matrix completion with noise. Proceedings of the IEEE,
98(6):925-936, 2010. doi: 10.1 101///0C..209900355550 203357222..
[13] Emmanuel Candès and Benjamin Recht. Exact matrix completion via convex optimization. Found. Comput. Math., 96):717-772, 2009. ISSN 1615-3375, 1615-3338. doi: 10. 10.1007/
(002080009-00555 URL htttp::ts://d http:///ioo...111..1111 1tt..//0//0000000/00000000 0000000--09999-400 9045-5
[14] Benjamin Recht. simpler approach to matrix completion. Mach. Learn. Res., 12:3413-3430, 2011. ISSN 1532-4435,1533-7922
[15] Moritz Hardt and Mary Wootters. Fast matrix completion without the condition number. In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 638-678, Barcelona, Spain, 13-15 Jun 2014. PMLR. URL htlLh:tts///pee p/tppe/e////cooeeeggg/ mlr. www.prresssvvve wttps///////aarr11....... hwtphharddtaaaaaa. html
[16] Moritz Hardt. Understanding alternating minimization for matrix completion. 55th Annual IEEE Symposium Foundations of Computer Science-FOCS 2014, pages 651-660, IEEE Computer Soc., Los Alamitos, CA, 2014. ISBN 978- 144799-6517-5. doi: 10. 1091FFFFOCC 75. URL https://d/// ote/ /0. 1w11//009C0... 2014. 75
[17] Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from few entries. IEEE Trans. Inform. Theory, 5616);2980-2998 2010. ISSN 0018-9448, 1188-9448111577111 1557-9654, doi: 10.1109/TTT.20022244622
URL httt:tttt//oo..ooo http::::///oioor/110// 1w../////......1.....TT..T.
1ww.//11.TTTTT 2046205
[18] Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from noisy entries. J. Mach. Learn. Res., 11:2057-2078, 2010. ISSN 1532-4435,1533--922.

---

[19] Anonymous authors. ery of noisy matrix from few entries: the infinity norm approach", 2025. URL
Supplementary appendix to the paper "fast exact recov-
Matrix_ Sromppetiio__NeuRPPSSOOO00 / / .pf
https://88 /at::://itttut i- Stw.mppeeee.oooeeerrrP0000 http:////2222bbbob//moma supplementary..
[20] Sourav Chatterjee. Matrix estimation by universal singular value thresholding. Ann. Statist.,
43(D):17-214, 2015. ISSN 1100000334,2118---5 doi: 10.121414-A0S11222 URL https
/ /ddoi.org/10 1214/14-A0S1272
[21] Sohom Bhattacharya and Sourav Chatterjee. Matrix completion with data-dependdnt miss- ingness probabilities. IEEE Trans. Inform. Theory, 68(10))672-6673, 2022. ISSN 0018- 9448, 1557-964..
doi: 10. 00.11099i1.2022.1170444 URL https://doi...... org/::////oooo////////// ot.p:o/..rg1......1.... 11.g///0.110 10.1//....19/
[22] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization (extended abstract). In STOC' Proccediiss of the 2013 ACM Symposium on Theory of Computing, pages 665-674. ACM, New York, 2013. ISBN 978-1- 4503-2029-0. doi: 10. 211114//288868824488865 2488899 (tRLsttss:://et org/10. 10. 10..11145428808 2488693
[23] Srinadh Bhojanapalli and Prateck Jain. Universal matrix completion. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference Machine Learning. volume 32 of Proceedings of Machine Learning Research, pages 1881-1889, Bejing, China, 22-24 Jun 2014. PMLR. html
mlr. www.prress/eee prresss/v32/booaaaggge wtwp://iwn......eessesssse/.
[24] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Ann. Statist., 48(3):1452-1474, 2020. ISSN 0090-5364.2168
doi: 10.1214/1-AASS885 URL https:s::///oo ort.:/....rg/11.. 1214/
19- 19-A0S1854
[25] Abhinav Bhardwaj and Van Vu. Matrix perturbation: Davis-Kahan the infinity norm. In Proceedings of the 2024 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 880-934. SIAM, Philadelphia, PA, 2024. ISBN 978-1-61197-791-- doi: 10.1137/1. 9781611977912.34 URL httpss//:///o
1 111..111//111178111977999122...
[26] Martin Wainwright. Principal component analysis high dimensions, page 236-258. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[27] Phuc Tran and Van Vu. New matrix perturbation bounds via combinatorial expansion i: Perturbation of eigenspaces, 2024. URL http://aaxxivvoooab///////a 20207 arXiv preprint
/40///2249..om 20207
[28] Van Vu. Spectral norm of random matrices. Combinatorica, (11)):721-736,0000 ISSN 0209- 9683, 6919-
doi: 10.10077/004493-0722299900 URL https:///ol.orr//0..
500493-007-2190-
[29] Afonso S. Bandeira and Ramon van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. Ann. Probab., 44(4):249-2256,, 2016. ISSN
0091-1798,21 7777999118889999 11-899XX. doi: 10.1214/15-AP1122. URL https://doi: www.oo.gg...... 15-A0P1025
[30] Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Ann. Probab., 33(5):1643-1699) 2005. ISSN 0091-1798, 894X. doi: 10.2114/000111900000000099 1224/0091190550000222
URL https://doi.oorr /rg///0000000//
[31] Delphine Féral and Sandrine Péché. The largest eigenvalue of rank one deformation of large
Wigner matrices. Comm. Math. Phys., 278(1):185-228, 2007. ISSN 0010-3616, 1432-0916. doi: 10. 10.10077:0020-007000009 URL http:///ww.///...//.///////////.
12

---

[32] Sandrine Péché. The largest eigenvalue of small rank perturbations of Hermitian random matri- ces. Probab. Theory Related Fields. 134(1):127-173, 2006. ISSN 000e-80011,,11222 doi: 00.10077/004400-05-44666 URL.
[33] Mireille Capitaine, Catherine Donati-Martin, and Delphine Féral. The largest eigenvalues of finite rank deformation large Wigner matrices: convergence and nonuniversality of the fluctuations. Ann. Probab., 37(1): 47, 2009. ISSN 1991-1798,2168-880
doi: 10.1214,
08- A0P34. URL https: / /doi. org/10 1214/01-1118011 AOP394
[34] Florent Benaych-Georges and Raj Rao Nadakuditi. The eigenvalues and eigenvectors of finite, low rank perturbations large random matrices. Adv. Math., 227(1):494-521, 2011. ISSN 0001-8708, 1090-2082. doi: amm.
URL 0ttb::://ooi.orr/100000006
j.aim. 20a...011.02... 02.007
[35] Farzan Haddadi and Arash Amini Eigenvectors of deformed Wigner random matrices. IEEE Trans. Inform. Theory, 67(2)):069-1079, 2021. ISSN 1001-8994,1,. 1458-955799654 doi: 10.1 2020.3039173.
wttp://.....11//1/1111 1109/titt..... 2020 3039173
[36] Wassily Hoeffding, Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58: 58:1::::00001 1963. ISSN 1155-111999999913722744 URL http://links.... jsttor jstor
org/sici7sici - 1459 (196300))11)))) :8: (1t.aa/0666464000000000000011111
30::0301111:
[37] Chandler Davis and W. M. Kahan. The rotation of eigenvectors by perturbation. III. SIAM
J. Numer: Anal., 7:1-46, 1970. ISSN 0036-1429.
doi: 10.1137/0707001. URL https
/ //doi. 1117000071170070000
[38] Per-Åke Wedin. Perturbation bounds in connection with singular value decomposition. Nordisk
Tidskr. Infornattinnbeehandiing (BIT), 12:99-111, 1972. ISSN 0901-246X. doi: 10.1007/ bf01932678. htLpstts:://00 org/ 10. 1000000009926600
[39] Sean O'Rourke, Van Vu, and Ke Wang. Random perturbation of low rank matrices: improving classical bounds. Linear Algebra Appl., 540:26-59, 2018. ISSN 1823-3795,1883-11888 doi:
URL https: /octps://doi.oo org/ j016/jojoo.. laa 2017. 11.014
[40] BaoLinh Tran and Van Vu. The "power of few" phenomenon: the sparse case. Random Structures Algorithms, 66(1):Paper No. c21260, 16, 2025. ISSN (042-983211098-244 doi: 10.1002/rsa.2122 22200 https:tts::///oi. www.://0...........000........
[41] Xueyu Mao, Purnamrita Sarkar, and Deepayan Chakrabarti. Estimating mixed memberships with sharp eigenvector deviations. 2019. abs/ 1709 00407
httttp:://axxivorr//bbbba 00400 00407 arXiv
[42] Jianqing Fan, Yingying Fan, Xiao Han, and Jinchi Lv. Asymptotic theory eigenvectors for random matrices with diverging spikes, 2020. URL http::t/t/:/aaatt org/abs /////////// 19112.0022266666 arXiv preprint http::://tt//:ttt/ /ttp/////vvvv//////////ee///avvv www.ai.or.abaaaaaaaaaoaaaa...aae wttg///s///0/.00ee5e
13

---

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: In Section we claim that (1) exact recovery in the finite precision sense is achieved via truncated SVD with appropriate truncation point, combined with rounding step, and that (2) this method works with only the three basic assumptions present in all previous works on exact matrix completion, plus mild "strong signal" assumption, and that (3) the strong sinal assumption is necessary for noisy data. To justify the first two claims are resolved in the subsequent sections, provide Algorithm 2.2 in Section 2 and assert its correctness with Theorem [.3] which uses only the aforementioned assumptions. We prove Theorem 2.3 by shifting to the matrix perturbation perspective, using Theorem to complete the proof (with details in Section B of the supplementary appendix). The third
claim is justified in Remark 2.5 in Section 2.2
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 it is clear that these goals are attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Remark 2.6 we briefly mention that the power of the log N factor in our sample size assumption (to guarantee that the algorithm works) in Theorem [.]] can be improved if one can refine the semi-isotropic bounds in Theorem B.4 4 in the supplementary appendix Section L.3 we also make clear that exact recovery for noiseless data, the true sense, has been achieved by Candes, Recht and Tao with the nuclear norm minimization (NNM) method, with only the three basic assumptions. We emphasize that our method both simpler and faster than NNM, that it is robust for noisy data, and that requires fewer assumptions than previous fast methods for exact recovery.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors 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 (c.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 on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is 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 handle technical jargon.
14

---

The authors should discuss the computational efficiency of 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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 proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The full proof's are in the supplementary appendix, with every theorem and lemma fully proven, or cited from another paper.
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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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 of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Regarding Figure we have described the necessary steps to reproduce the graphs of the singular values and their gaps.
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, or 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
15

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should descrihe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular 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., registered users), but it should be possible for other researchers to have some path to reproducing verifying the results. 5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We feel that the description of the steps to reproduce Figure 1.3 has been clear enough, and the experiment itself is fairly short and non-essential to the results of the paper, so we do not feel the need to publish the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.cc)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ wttppccccpcccccccccccccccccccclt http://gweeeeeeeeeeee http:///eeeeebosssssoooeeeeeeeee
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 new 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 to the paper) recommended, but including URLs to data and code permirted.
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: [NA]
Justification: The paper does not include experiments that require training and testing of Machine Learning models.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
16

---

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: [NA]
Justification: The paper does not include experiments that require training and testing of statistical hypotheses.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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% CI, 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 range (e.g. negative eтror 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 of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments that require comparing performances of different algorithms, and thus does not need to specify the hardwares used. In fact, the experiments to produce Figure 1.3 can be run on any modern computer than can run Anaconda and Python 3.9.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of 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 or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpp::/neuurpps: http://www.....ppooooo//ccccsaaa
Answer: [Yes]
Justification: We have read and made sure that our paper follows the guidelines in the NeuRIPS Code of Ethics.
Guidelines:
17

---

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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper concerns a purely technical problem and its solution, with real-life applications in technologies that socially and politically neutral.
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.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet 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 tied to particular applications, let alone deployments. However, if there is a 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 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.
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 deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We have no data models that are of high risks for misuse.
Guidelines:
The answer NA means that the paper poses 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 to usage guidelines or 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
18

---

Question: 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?
Answer: [Yes]
The Yale face dataset used producing Figure 1.3 has been properly used and cited, as has the textbook in which it was mentioned.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, 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.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithheeooo thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We have released assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing 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 crowdsoureing 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 much detail as possible should be included in the main paper.
According to the NeurlPS 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.
19

---

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/teview based the requirements of your country institution) were obtained?
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.
Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to 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.
Declaration LLM usage
Does the paper describe the usage of LLMs if it is 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 this research does not 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.
20


Reviews:
[{"review_id": "bpAIy0PTXt", "reviewer": "Reviewer_KmFY", "summary": "This paper studies exact matrix completion in a setting in which the underlying matrix has rank r and  entries that are multiple of a known fixed number epsilon. The authors show that exact reconstruction is possible (in the case of fixed rank) as soon as the number of observed entries is larger than $(m+n)*log(m+n)^4$ which is nearly optimal.\nThe important point is that no assumption on the condition number or separation between singular values is made.", "questions": "I do not have questions.", "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": "Strenghts:\n1. Removing the dependence on the condition number and separation between singular values is significant.\n2. The proof technique is interesting.\n\nWeaknesses:\n1. Several key ideas are actually based on Tran Vu (2024)\n2. The algorithm is a small variation over method studied before.\n3. The assumption of discrete entries together with small rank is unrealistic. For instance the netflix ratings matrix is discrete but does not have small rank.", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your comments and the positive evaluation of our paper. We agree with your assessment of the shortcomings of the paper, and we would like to point out that we will try to tackle the case where the underlying matrix is only approximately low-rank in a future paper. As a matter of fact, the contour method used in the paper of Tran and Vu (that we follow)  applies for the approximately low rank case, when the matrix has few large leading eigenvalues and the rest are small.  However, to prove perturbation bound in the infinity norm as in this paper, this method needs to be modified significantly. We are working on the details at this moment, but are pretty positve on the outcomes."}, {"review_id": "6mf2VVRpA3", "reviewer": "Reviewer_q3L5", "summary": "This article looks into the matrix recovery/completion problem, focusing on the assumptions typically utilized to ensure exact recovery is possible. The article identifies three basic assumptions including low rank, incoherence, and sampling density as the necessary assumptions for exact recovery. It then looks into two extra spectral assumptions used in recent works on the small condition number and the large gaps between consecutive singular values, which seem to contradict with each other. It turns out that neither is in fact necessary.\nFrom this the paper establishes the main contribution (Theorem 2.3) that given a sufficiently large spectral norm of the matrix and sufficient sampling rate, the matrix can be exactly recovered with a high probability with a small error. The approximation algorithm is correspondingly based on a truncated SVD. Additionally, in Theorem 3.1, the paper introduces an upper bound on the $l_\\infty$-norm of errors in recovery, with a new approach to proof using contour integrals.", "questions": "A couple questions:\n\n(1) The two spectral assumptions addressed by the paper in Section 1.3 are that the condition number is small, and the gaps between consecutive singular values are large. My impression is that these statements are rather hard to quantitatively verify. The example provided in the article claims that $\\kappa=10.45$ is a large condition number, with which I am not sure I can agree since typically we would call it large when it is in the range of $10^3$. Similarly, in Algorithm 2.2, the largest index $s$ is found by looking for the last 'big' drop in singular values, which is in some way similar to the second spectral statement. I wonder whether the authors can clarify on the refutation of these two assumptions.\n\n(2) The recovery algorithm uses a truncated SVD with an additional scheme to ascertain the cutoff $s$. Since truncated SVD for matrix completion has been widely applied, I am curious if the authors can provide more insight on how the thresholding rule is established.", "limitations": "Not limitations but a few minor points:\n\n(1) I wonder whether the authors have considered applying the proposed completion algorithm to a real-world application to demonstrate its performance. \n\n(2) The article denotes the fixed precision of the matrix by $\\epsilon$, however, later in the paper it is referred to as the distortion level. Although both are probably supposed to refer to the same entity, I fear this causes some confusion.\n\n(3) In Section 2,1, it is claimed the algorithm is efficient consisting a truncated SVD on a sparse matrix. I am not seeing the sparsity being properly defined so I wonder whether this point can be clarified.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The target problem of the article has long been of interest, including the algorithm to recovery/complete a noisy and partially observed matrix, and theoretical results on the sampling rate to achieve accurate recovery. The literature review on the seminar works and more recent works is quite extensive, including the discussion on the necessity of the basic assumptions and the extra spectral ones. The key contributions include the low-rank approximation algorithm with a proposed method to find the cutoff, and a lower bound on the sampling rate, which are quite significant.\n\nIn terms of weakness, my opinion is that I am hoping to see more direct comparison of the sampling rate between the theoretical results proposed with that of the earlier works on matrix completion for their similarity and difference. For example, the results in ''Matrix Completion With Noise'' and ''Exact Low-rank Matrix Completion via Convex Optimization''. I believe that will better highlight the significance of the results by this article.", "was_revised": true, "final_justification": "The concerns from the reviewer have been properly addressed so I have adjusted my rating accordingly.", "rebuttal": "We thank you for your comments and the positive evaluation of our paper. We would like to address the following concerns and questions of your review:\n\n**1. Weaknesses of the paper:**\n\n1.  We acknowledge that we did not set aside a separate section to summarize and clarify the advantages and possible disadvantages of our results versus the other works. In an early version of the paper, we had a comparison table, which was cut from the final draft after we restructured the paper and removed the discussions and comparisons with several other papers that we felt not as relevant as the ones we kept. We did this to comply with the page limit. If you prefer, we will try to bring it back, with appropriate adjustments, probably in Section 3.3.\n\n2. Let us respond specifically to clarify your concern about the lack of direct comparisons with \"Matrix Completion with Noise\" by Candes and Plan (reference [8] in our paper) and \"Exact Low-rank Matrix Completion via Convex Optimization\" by Candes and Recht (reference [1]).\n  \n  - The result of [1] is one of most influential works in Matrix Completion that deal with the pure (noiseless) problem. It was followed shortly by the papers of Candes and Tao (reference [2]) and Recht (reference [3]) that direct improved on it. Therefore, it suffices to compare our result with [3]. Ignoring the factors dependent on $\\mu_0$ (the coherence) and $r$ (the rank of the original matrix), [3] has achieved near-optimal sampling rate, being off by a $\\log(m + n)$ factor from the theoretical limit $(m + n)\\log(m + n)$. Our result has a sampling rate off by $\\log^9(m + n)$, but otherwise is optimal. Its main advatage is the ability to deal with random, independent noise, which is not addressed in [1, 2, 3]. Our algorithm is also simpler and faster in practice (it basically computes a low rank approximation of the input). \n\n  - The result (Theorem 7) in [8] is more general than ours in the sense thay it holds for any type of noise, whereas ours only apply to noises that are independent among entries and universally bounded by a known upper bound. We also need the extra assumption that $||A||$ is large enough (which we have argued is reasonable and perhaps necessary for exact recovery in Remark 2.4). However, their method only achieves recovery in the Frobenius norm, or RMSE, sense, while ours gives recovery in the infinity norm sense, which becomes exact after rounding off. Their method, being convex optimization, runs in time $O(|\\Omega|^2(m + n)^2)$, which is at least $O((m + n)^4\\log^2(m + n))$ for recovery to be theoretically possible (see the survey [15] in our paper). On the other hand, our method runs in time $O(r|\\Omega| + mn)$, being simply a truncated SVD algorithm, making it much faster than [8]. Another point is the effectiveness of the methods. To achieve a RMSE error (which is $||\\hat{A} - A||_F / \\sqrt{mn}$) within some $\\varepsilon$, the method in [8] needs $p \\ge \\epsilon^{-2} ||Z||_F^2 / (m + n)$, which is not possible even in the simple cases like $Z$ having independent entries in $\\{-1, 0, 1\\}$ with uniform distribution (setting $p = 1$, which means full observation, is still not enough if $\\varepsilon = 0.1$). Our method achieves $||\\hat{A} - A||\\_\\infty \\le \\varepsilon$, which is stronger, while only needing $m$ and $n$ to be large enough and $p \\ge C(r, \\mu_0)\\max\\{\\log^4 (m + n), \\varepsilon^{-2}\\} \\log^6(m + n)$, which is much lower and achievable for the aforementioned simple noise model.\n\n3. We also want to offer a brief comparison with the works of Keshavan, Oh and Montanari (references [6] and [7]) that deal with both the noiseless and noisy cases. Our sampling rate is slightly higher than theirs, being off by a few $\\log (m + n)$ factors, and we need the extra assumption that $||A||$ is large enough (see the previous item and Remark 2.4 in our paper). On the other hand, we remove the dependence on the condition number that they have, and our method achieves an infinity norm recovery while theirs stop at RMSE recovery.\n\n**2. Questions.**\n\n1. Although  a condition number $\\kappa \\approx 10.45$ may be small, it can get very large if raised to high powers, making bounds inefficient. For example, the papers [6] and [9] that we discuss throughout Section 1 involve $\\kappa^6$ and $\\kappa^4$ in their sampling rate bounds. Our result avoids this growth factor by removing $\\kappa$ completely.\n\n2. A high-level explanation for our thresholding rule is as follow. We view the observed matrix, rescaled by $p^{-1}$, as a perturbed version of the original matrix, namely $p^{-1}A_{\\Omega, Z} = \\tilde{A} = A + E$, where $E$ is a random matrix of mean $0$ and independent entries. One can view $E$ as a type of \"noise\" that includes both the noise $Z$ and the noise caused by the random sampling. We simply want to cut off the singular values of $\\tilde{A}$ at a level above $||E||$, as the BBP phenomenon shows that the part of $A$ below that is fully absorbed by $E$ and becomes indistinguishable from noise. Under the assumptions we make, the signal extracted from the spectrum of $\\tilde{A}$ above this threshold is close enough to $A$ to allow us to recover it. We use the same argument in Remark 2.4 to show the necessity of the lower bound on $\\sigma_1 = ||A||$.\n\n**3. Limitations:**\n\n1. Thank you for the suggestion of including experiments on real datasets. As pointed out by other reviews, our assumption of low rank still does not fully reflect real-life datasets, which are often only approximate low-rank, so initially we wanted to focus on the fact our result breaks the two theoretical barriers involving the condition number and large singular value gaps as the main highlight. We will certainly include experiments, paralleling those in other works in the final version if you deem it necessary. We are also working on an extension of this paper which would cover the case when the truth matrix is only approximately low rank. \n\n2. We apologize for the potential confusion caused by the word \"distortion level\". We can revert it back to \"discretization unit\", for example.\n\n3. We use the word \"sparse\" simply to point out that, in the worst case that our method can still guarantee recovery with high probability, we allow the sampling rate $p$ (the density of non-zero entries in the observed matrix $A_{\\Omega, Z}$) to be very small, being at most $C(\\mu_0, r) (m^{-1} + n^{-1}) \\log^C(m + n)$. We acknowledge that $A_{\\Omega, Z}$ can become dense if $p$ increases. This will increase the time our SVD step takes, but also makes it easier to recovery $A$. As mentioned above, the time complexity $O(r|\\Omega| + mn) = O((pr + 1)mn)$ is still substantially better than nuclear norminimzation for any value of $p$."}, {"review_id": "CUKxv9Ivec", "reviewer": "Reviewer_AT2W", "summary": "The paper analyzes the performance of the proposed approximate-and-round 2 algorithm for matrix completion. By leveraging contour integrals and refined bounds on bilinear forms of matrix powers, it eliminates the dependence on the condition number and singular value gaps in the recovery guarantees and establishes an infinity-norm bound between the estimated matrix and the ground truth.", "questions": "1. Lines 261-272 suggest that a fine-grained bound on $\\left|e_j^{\\top} E_{\\text {sym}}^a w_i\\right|$ is needed. Such bounds are common in the literature, for example, in Section C.4 of Estimating Mixed Memberships with Sharp Eigenvector Deviations by Mao et al. (JASA 2021) and Lemmas 4 and 5 of Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes by Fan et al. (JASA 2022). (I am referring to the arXiv versions of these papers.)\n    If I understand correctly, the bounds in Lemmas D.3 and D.4 in the Appendix could be derived using bounds on $\\left|e_j^{\\top} E_{\\text {sym}}^a w_i\\right|$. Could you briefly discuss whether the results in these papers can be applied directly to obtain Lemmas D.3 and D.4, or clarify if additional arguments are needed?\n2. In the proof of Theorem 2.3, the signal-to-noise assumption changes from $\\sigma_1 \\geq 100 r K \\sqrt{r_{\\max } N / p}$ to $\\sigma_1 \\geq 100 r \\kappa \\sqrt{r_{\\max } N}$. It appears that you are implicitly using $\\kappa=K / \\sqrt{p}$, which conflicts with the notation where $\\kappa$ denotes the condition number of the matrix $A$. Perhaps this is a typo, and you intended to use a different symbol, such as $\\varsigma$ as introduced in Theorem B.4?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength:**\n\nAs mentioned in the summary, the paper presents a novel result on the performance of the approximate-and-round 2 algorithm for matrix completion, removing the dependence on the condition number and singular value gaps in the recovery guarantees. This is a meaningful contribution that offers new theoretical insights to the community. While I was not able to check all the details of the proofs due to time constraints, the overall approach appears solid and well-motivated.\n\n**Weaknesses:**\n1. I recommend adding numerical experiments to demonstrate that the algorithm's performance does not depend on the condition number $\\kappa$ if time permits.\n2. The assumption that $A$ has a distortion level of $\\varepsilon$ feels somewhat unnatural. It effectively implies that $A=$ $\\varepsilon B$ for some integer matrix $B$, where $B$ is bounded by $K_A / \\varepsilon$ and has rank $r$. Requiring an integer matrix to be exactly low-rank can be restrictive and unnatural in practice. Moreover, exact recovery may not be necessary, as a refined entrywise error bound would be sufficient for many applications, particularly under noisy observation settings.", "was_revised": true, "final_justification": "At the outset, I would like to highlight that the dependence on the condition number in low-rank matrix estimation has long been regarded as an artifact of the proof technique; eliminating this dependence constitutes an important theoretical contribution of the paper. The authors have addressed most of my questions. As a minor point, while the newly introduced matrix concentration inequalities are interesting, I encourage the authors to make clearer connections between these results and the existing literature. Overall, I maintain my positive score of the paper.", "rebuttal": "We thank you for your comments and the positive evaluation of our paper. We agree with your assessment of the shortcomings of the paper, and we would like to point out that we will try to tackle the case where the underlying matrix is only approximately low-rank in a future paper.\nWe also agree with your suggestion of including experiments on real datasets. We will certainly include experiments, paralleling those in other works in the final version if you deem it necessary.\n\nRegarding your questions, we would like to offer our responses below.\n\n1. Thank you for bringing to our attention these results, as we were not initially aware of them. We have examined the results by Mao et al. and Fan et al. carefully, and we found that their scopes do not cover our use case. We would like to bound $|e_i^TE^kw|$ (this $E$ is $\\mathbf{H}$ in Mao et al. and $\\mathbf{W}$ in Fan et al.), for all $i\\in [n]$ and all $k\\le C\\log n$ for some large enough constant $C$ like $100$. The probability for the bound to hold must be strong enough to beat the union bounds over all $i\\in [n]$ and $k\\le C\\log n$. This means the probability should be at least $1 - o(n^{-1}\\log^{-1}n)$. If we use Lemma 5.4 in Mao et al. for this purpose, we need to choose some $\\xi > 1$, and let $t = C\\log n$. The factor next to $||v||\\_\\infty$ in the bound then becomes $(\\log n)^{c \\log n}$, which grows too fast for our use (our Lemmas D.3 and D.4 has this factor capped at $\\log^3 n$). Likewise, Lemmas 4 and 5 in Fan et al. seem to not be directly applicable, since they assume $k$ is a bounded integer. Moreover, in our use case, which is where $E$ has $0$ on its diagonal, we need to involve $||v||_\\infty$ in the bound to make it efficient. If we can apply Lemma 4, then Lemma 5 here to arrive at a bound, it will just be $O(\\alpha_n^k)$, or $O(n^{k/2})$. This is not much better than the trivial argument $|e_i^TE^kv| \\le ||E||^k = O((2n)^{k/2})$ (for our use case only, as theirs also cover the case of non-zero diagonals). We admit that we had not have time to read and analyze their proofs, and it is possible that their techniques can be extended to cover our use case, or help us improve our result even more. We will continue to read their proofs and include a discussion about these results in the final version of the paper.\n\n2. Thank you for pointing out the typo. Indeed we intended to use $\\varsigma$ instead $\\kappa$ there. Choosing the names of variables has been challenging for us since this paper uses so many, and we want to keep variable names close to their traditional names in literature if possible. The naming clash for the name $\\sigma$ between the singular values and the variance of a random variables has been a particular issue. We will certainly fix it in the final version."}, {"review_id": "2iy47laAYg", "reviewer": "Reviewer_nrNZ", "summary": "This manuscript considers the problem of exact recovery of a low rank matrix from noisy observations, under an additional assumption that\nthe underlying matrix entries have fixed precision (i.e. they are all integer multiples of some epsilon). \n\nThe authors study a simple SVD-based algorithm followed by rounding. They prove that, under certain conditions, their method can exactly recover the target matrix even in the presence of additive noise. The analysis combines tools from random matrix theory and from matrix perturbation.", "questions": "- P4 L127 the authors write \"this not only provides a mathematically ... .but also significantly expands the range of applications (regarding real datasets). Can the authors provide convincing examples for this claim ?\n\n- Can the authors discuss how to estimate the parameters K_A and K_Z in the proposed algorithm ? \n\n- P5 L160 RMSE recovery with the same error margin. Can you please explain this sentence ?", "limitations": "This work is theoretical and has no societal impact.", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "Strengths: \nThe use of sophisticated tools from random matrix theory enables the authors to establish recovery guarantees that surpass existing \nresults in similar settings.\nThe paper is relatively clearly written and accessible.\n\nWeaknesses: \nThe problem considered in this manuscript is uncommon and non-standard in the matrix completion literature. \nIn terms of originality, the method considered is (up to the rounding step and how to choose the number of components) standard as an initialization in the matrix completion literature, and so there is limited novelty here. \nThese issues raise major concerns regarding the importance of the problems studied, the significance of their findings for the community and their practical relevance. \n\nWhile the authors motivate their work by practical applications, the manuscript lacks an empirical evaluation to support the theoretical claims or illustrate the method's performance in practice.\n\nFit to NeurIPS: as the authors write, one of their theorems can be seen as an infinity norm variant of the classical Davis-Kahan Theorem. Perhaps a more suitable venue for this work would be a journal focused on matrix analysis. \n\nAdditional comments: \n- Problem formulation: the authors assume the underlying matrix has finite precision while observations contain noise. It would strengthen the manuscript if the authors were to provide concrete examples where this setting holds. To the best of my knowledge, the more common setting is one in which the observations are quantized (e.g, have finite precision) with the underlying matrix assumed low rank but not with bounded precision. Examples include movie ratings (e.g. observed values are 1-5) with various stochastic models relating how observed ratings are related to the underlying matrix entries, and the 1-bit matrix completion problem, where observed entries are +1/-1, again where they underlying matrix is assumed low rank. \n\n- Abstract is very long. In addition, the abstract cites various papers, which is rather uncommon.\n\n- The authors write that the paper by Abbe et al [9] showed that one can recover A even in the noisy case, provided A has bounded precision [p1 L15], and a similar statement on p3 L101. This seems to imply that [9] also considered the precise problem studied in this manuscript of exact recovery in a matrix completion problem. Unless I missed something, I find this rather misleading. Ref. [9] discussed exact recovery for stochastic block models, which is a different problem. To the best of my understanding, Section 3.3 of [9], titled matrix completion with noisy entries does not assume bounded precision. \n\n- p1 L32 to be precise, the task is to recover A given A_\\Omega *as well as* the set Omega itself. \n\n- p1 L66 the authors claim that many papers assume r is bounded while m,n\\to\\infty. I find this inaccurate for the matrix completion literature. It often holds in mathematical statistics / RMT papers. \n\n- p3 L113-end: the authors show the eigenvalue decay for the Yale face dataset. The relation between this example and the manuscript is unclear. At best, this result shows that many practical datasets do not have an exact low rank, but at best are only approximately low rank. \n\n- A small remark is that matrix completion becomes challenging when the number of observed entries is very small and yet above the information limit. In this case, the SVD of the observed entries is not sufficiently accurate, and yet there are various methods that empirically are still able to recover the matrix.", "was_revised": true, "final_justification": "In my opinion this manuscript has potential to make a significant impact. However, in its current form, it considers a very niche and not particularly interesting problem (exact recovery of low rank matrices with finite precision). It does not cite nor discuss the possible relation and implications of this work to the more recent literature on exact recovery guarantees for various methods. Overall, my assessment remains the same. In my opinion this manuscript requires significant and major revisions and a careful re-evaluation before being suitable for publication at a top venue such as NeurIPS.", "rebuttal": "Thank you for the through and detailed comments and the evaluation of our paper. We would like to offer our responses to some of your concerns and questions.\n\n**1. Comments**\n\n1.  Regarding the lack of experiments on real datasets: we thank you for pointing it out, and we agree that we should have included a couple. Other reviews also pointed out that our assumption of low rank still does not fully reflect real-life datasets, which are often only approximate low-rank. On the other hand, most breakthrough mathematical works like Candes-Tao's make use of the low rank assumption.\nInitially, we wanted to focus on the fact our result breaks the two theoretical barriers involving the condition number and large singular value gaps as the main highlight. We will certainly include experiments, paralleling those in other works in the final version. We are also working on an extension of this paper to cover the case when the ground matrix is approximately low rank. \n\n2. Regarding the comparison with Abbe et al. (reference [9] in our paper): We felt that, at least in Section 3.3 of [9], the problems both of us were trying to solve are essentially the same, as we both aimed to provide an infinity norm estimate for the error of our respective recovery methods in terms of $n$, $p$ and other parameters from the underlying matrix $A$, which can then be turned to an estimate on the minimum sampling rate ($p$) needed to make this error within a chosen $\\varepsilon$. We only need to look at the precision level of the entries of $A$ if we want to round off the output to achieve exact recovery (one can imagine that the output before rounding off has higher precision level, for example, 64-bit floating point numbers while $A$'s entries are half-integers). \nAs the focus of [9] is a different problem, \nwe appologize for making the comparison with respect to matrix completion. We can omit this comparison and will only have  a   comparison with Section 3.3, and with respect to the infinity norm bounds. \n\n3. Regarding the inaccuracies on page 1: We thank you for pointing them out, and we will certainly fix them in the final version. We would also like to note that our result holds for a general $r$ that can go to infinity with $m$ and $n$.\n\n4. Regarding the comment about page 3: We refer to our first paragraph, which admits the limit of our current scope to low-rank matrices.\n\n**2. Questions**\n\n1. Regarding page 4 line 127: We meant to explain that our result guarantees (with high probability) that the method of truncated SVD can now be applied to recover, down to every entry, matrices with large condition numbers, and matrices with some small singular value gaps, which were not guaranteed by previous methods. As mentioned above, we will include experiments with some datasets in the final version.\n\n2. Regarding how to estimate $K_A$ and $K_Z$: We simply assume they will be given along with the dataset. For example, $K_A + K_Z \\le 5$ in the Netflix problem. Datasets often come with descriptions about the range of values each cell can take.\n\n3. Regarding page 5 line 160: We meant to explain that if we obtain a recovery within $\\varepsilon$ in the infinity norm, meaning $||\\hat{A} - A||\\_\\infty \\le \\varepsilon$, then this recovery is also within $\\varepsilon$ in the root-mean-squared-error sense, namely $\\frac{1}{\\sqrt{mn}} ||\\hat{A} - A||_F \\le \\varepsilon$, which is a fairly straightforward observation. We apologize for the confusion caused by our word choices, and will add a couple sentences to clarify this in the final version."}]

Author rebuttal:

Meta-review: One reviewer was still not satisfied with the paper, arguing that a ground truth which is low rank and has integer entries is not so realistic. The other reviewers also acknowledged this but for them this concern was outweighed by the nice technical contributions of the paper, and removing assumptions in prior work on condition number and singular value gaps that were needed even in this case. I tend to agree with the majority here, and think the ideas here are significant and this will be impactful for future work. Thus, I recommend acceptance.
Decision: Accept (poster)