{"id":"e0de28be-d95a-4bb0-90fa-02f66678bdb7","arxiv_id":"2501.19224","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A truncated-SVD-plus-rounding algorithm achieves exact recovery of noisy low-rank matrices under only low rank, incoherence, and sufficient sampling, with a new infinity-norm perturbation theorem.","lead":"This paper gives the first algorithm that exactly recovers a noisy low-rank matrix from a sparse set of observed entries using only the three standard matrix-completion assumptions. The method is a single truncated SVD followed by rounding, backed by a new infinity-norm perturbation theorem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The abstract's claim of 'only three basic assumptions' is undercut by the explicit large-signal hypothesis in Theorem 1.5, which the proof uses to guarantee a valid truncation index and to apply Theorem 2.1.","rationale":"The reader's weakest_assumption identified the large-signal premise as load-bearing, and my reading agrees. The theorem itself is internally coherent, and the core Davis-Kahan-Wedin bound appears to be the main technical contribution; but the paper's advertised novelty is exact recovery under only low-rank, incoherence, and sampling-density assumptions. Theorem 1.5 formally adds a signal-to-noise condition, and the proof uses it to certify the truncation index and to satisfy the gap condition of the perturbation theorem. This is not a mere presentational issue: without the condition, the proof's step selecting s ∈ [r] and its application of Theorem 2.1 fail. The self-aware Remark 1.7.3 confirms the condition is present, so the abstract's claim is overstated relative to the proved statement. However, since the theorem as stated includes the condition and the proof appears to support that statement, the appropriate verdict remains CONDITIONAL, not REJECT; my read does not change the reader's verdict.","tokens_in":47,"tokens_out":11499,"duration_ms":280824,"concrete_test":"Set m = n = N, r = rmax = 2, K = KA + KZ = 1, and take A = diag(σ, σ) (padded with zeros) with unit-norm, µ0 = O(1) singular vectors, entries multiples of ε0. Choose σ = 10 √(N/p), violating the large-signal condition σ1 ≥ 100 r K √(rmax N/p) = 200 √(N/p) by a factor of 20, while keeping p at the level (19). Run AR2 analytically or numerically with bounded noise of scale KZ = 1. Verify whether Step 1 of the proof can certify s ∈ [r]: the gap δ1 = 0 is below the cutoff 20√(rmax N/p), so the algorithm sets s = rmax = 2; then δ_2 = σ = 10√(N/p) is below the 40 r K √(N/p) = 80√(N/p) required by Theorem 2.1, so the proof's key perturbation bound cannot be applied. If exact recovery still holds in this example, the large-signal condition is removable for this case; if not, or if the proof simply cannot proceed without it, the 'only three assumptions' claim is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1.5 states, beyond the three basic assumptions and bounded precision, the large-signal condition σ1 ≥ 100 r K √(rmax N / p). The abstract and Section 1.7 claim exact recovery 'under only the three basic assumptions.' This is not a cosmetic omission. The proof of Theorem 1.5 uses the condition in two load-bearing places. First, to find l ∈ [r] with δ_l ≥ σ1/r; only with σ1/r ≥ 100K√(rmax N/p) does Weyl's inequality give a gap above the algorithm's cutoff 20K√(rmax N/p), ensuring the selected s lies in [r]. Second, the bound on σ_{s+1} in Eq. (31) relies on s being the largest index whose gap clears the cutoff, so σ_{s+1} is a sum of gaps each below the cutoff. If the large-signal condition fails, the proof cannot certify s ≤ r, and even when s = r the gap δ_s may be below the 40rK√(N/p) needed to invoke Theorem 2.1. Remark 1.7.3 itself concedes 'Well, almost!' and frames the condition as mild, but mildness does not make it one of the three listed assumptions. The central advertised contribution—exact recovery under only the three basic assumptions—therefore requires qualification.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies exact matrix completion from noisy, partially observed entries, assuming the ground-truth matrix has entries at finite precision (multiples of ε0). The authors propose the algorithm AR2, which rescales the observed matrix, computes a truncated SVD with a data-dependent cutoff, and rounds the result to the nearest multiple of ε0. The main theorem (Theorem 1.5) asserts that, under low rank, incoherence, the sampling-density condition (19), bounded noise moments, and a large-signal condition σ1 ≥ 100 r K sqrt(rmax N / p), the first three steps of AR2 approximate A entrywise to error ε0/3 with probability 1 - O(N^{-1}), so rounding then recovers A exactly. The proof builds on a new infinity-norm Davis-Kahan-Wedin-type perturbation bound (Theorem 3.2), a random version (Theorem 3.3), and a deduction chain from Theorem 2.1 to Theorem 1.5. The paper advertises removal of the extra spectral assumptions (small condition number or large singular-value gaps) required by previous infinity-norm approaches.","tokens_in":54238,"tokens_out":6843,"duration_ms":60006,"significance":"If the proof chain is completed, this is a significant contribution: it would give the first noisy exact-recovery result using essentially the classical low-rank, incoherence, and sampling-density assumptions, with an extremely simple algorithm (truncated SVD plus rounding). The contour-integration and combinatorial-expansion method for infinity-norm perturbation bounds is new and appears to be of independent interest; the sequence from the deterministic Theorem 3.2 through the random Theorem 3.3 to Theorem 2.1 and Theorem 1.5 is presented in detailed, largely self-contained fashion, including semi-isotropic moment bounds for powers of random matrices. However, the advertised claim of recovery 'under only the three basic assumptions' is not literally what is proved, and the proof of the key Lemma 4.2 is currently incomplete as written. Both issues are load-bearing and must be addressed before the central claims can be taken at face value.","major_comments":[{"comment":"The abstract and the introduction state that exact recovery is achieved 'under only the three basic assumptions' (low rank, incoherence, density), but Theorem 1.5 contains an additional hypothesis, the large-signal condition σ1 ≥ 100 r K sqrt(rmax N / p) with K = K_A + K_Z. This condition is not cosmetic: the proof of Theorem 1.5 uses it to find an index l ∈ [r] with δ_l ≥ σ1/r, so that Weyl's inequality yields a gap above the algorithm's cutoff and ensures the selected index s lies in [r]; it is also used to control σ_{s+1} in Eq. (31), which is needed to bound ∥A_s − A∥∞. Remark 1.7.3 concedes 'Well, almost!' and argues that the condition is mild and often automatic, but mildness does not make it one of the three basic assumptions. The abstract and Section 1.7 should be qualified to state 'the three basic assumptions plus a large-signal condition,' and the remark should be integrated into the statement of the main theorem rather than left as an aside.","section":"Abstract, §1.7.3, Theorem 1.5"},{"comment":"The proof of Lemma 4.2 is incomplete as written. After the sentence 'We follow two steps:', the text breaks off at '1. Assuming M' and then resumes with 'Consider the analogue of Eq. (52) for V (we wrote the proof for V before the final edit, and wanted to save the energy of changing to U)' without completing the normalization from general ς to the case ς = 1, without specifying the constants D used in the applications of Lemmas B.3 and B.4, and without treating the stated range t > 0 and the two probability regimes in Eqs. (52)–(53) versus Eqs. (54)–(55). Since Lemma 4.2 supplies the semi-isotropic bounds for τ1 and τ2 used in the proof of Theorem 3.3, and Theorem 3.3 is the bridge to Theorem 2.1 and Theorem 1.5, this gap is load-bearing. The full proof needs to be supplied.","section":"§B.2, proof of Lemma 4.2"},{"comment":"The proof-structure discussion at the end of Section 3.2 states that 'we need to dedicate the whole Section 5 for the proof of Theorem 3.3', but the proof of Theorem 3.3 actually appears in Section 4.1. The cross-reference should be corrected, and the structural roadmap should be updated to match the actual section numbering.","section":"§3.2, end of Section 3.2"}],"minor_comments":[{"comment":"The sentence about recent universality results contains the placeholder 'cite Y au et al book which you read'; this must be replaced with a proper citation or removed.","section":"§3.2"},{"comment":"The phrase 'if all entries are multiples integer of ε0' should read 'if all entries are integer multiples of ε0'.","section":"Theorem 1.5"},{"comment":"The text near Eq. (67) says 'bounding it with overwhelming probablity'; the typo 'probablity' should be corrected to 'probability'.","section":"§4.2"},{"comment":"In the proof of Theorem 1.5, the probability bound for the concentration of ρ is stated as 1 − O(N^{-2}), while the final theorem claims 1 − O(N^{-1}); the proof should clarify that the union bound over all stages still leaves the O(N^{-1}) rate.","section":"§2.2"}],"recommendation":"major_revision","confidential_remarks":"The paper contains a genuinely new technique and a substantial proof chain, but the advertised main claim is overstated relative to the theorem statement, and a key lemma (Lemma 4.2) has an incomplete proof. Both issues are fixable within the manuscript's scope, but they require real work rather than copy-editing. I recommend major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the abstract oversells it, but the actual theorem is a real step forward and the proof deserves a careful read. The paper proves exact recovery for noisy matrix completion under low rank, incoherence, density, bounded precision, and a large-signal condition sigma_1 >= 100 r K sqrt(r_max N / p). That last condition is not one of the three basic assumptions, and the abstract's claim of 'only three basic assumptions' is not literally true. The proof uses it in at least two load-bearing places: to find a singular-value gap above the cutoff, and to bound sigma_{s+1}. The paper's own Remark 1.7.3 admits as much ('Well, almost!'). It argues the condition is mild and often automatic, and there is independent reason to think some signal-to-noise condition is necessary (BBP threshold). So the gap between advertised and actual is mostly a presentation problem, not a mathematical fraud.\n\nWhat is genuinely new: this is the first exact-recovery guarantee in the noisy case that removes both the small-condition-number assumption (Abbe et al.) and the singular-gap assumption (Bhardwaj–Vu). The algorithm is just rescale, truncated SVD, and round off. The main technical contribution is a Davis–Kahan–Wedin theorem in the infinity norm (Theorem 3.2) plus semi-isotropic moment bounds for powers of random matrices (Lemma 4.2). I did not find a fatal algebraic error in the chain from Theorem 1.5 to Theorem 2.1 to Theorems 3.2/3.3. The proof is long but structured, and the lemmas are stated with enough precision that a referee can check them.\n\nSoft spots, in order of importance. (1) The large-signal condition should be in the abstract. The theorem statement is honest, the abstract is not. (2) There is unfinished text in the proof of Lemma 4.2 ('1. Assuming M...') and a placeholder citation in Section 3.2 ('cite Yau et al book which you read'). These are cosmetic but embarrassing. (3) The paper leans heavily on the authors' earlier contour-expansion framework [38], which is still an arXiv preprint. That raises the barrier for independent verification, but the present paper gives enough detail that a referee can at least check the new steps. Self-citation here is not a red flag; the earlier work is directly relevant.\n\nMy take: this deserves a serious referee. The advertised 'only three basic assumptions' needs fixing, and the proof text needs cleaning, but the core result is substantial and the large-signal condition is a reasonable, probably necessary, addition. I would send it out. For a reading group, the infinity-norm Davis–Kahan–Wedin theorem alone is worth a session.","headline":"Real result, oversold abstract: the large-signal condition is load-bearing but mild, and the proof is worth engaging.","tokens_in":54742,"tokens_out":2514,"would_cite":true,"duration_ms":24359,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A18","15A42","60B20","62H12"],"pacs":[],"model":"deepseek-v4-flash","headline":"A simple truncated-SVD-plus-rounding algorithm recovers every entry of a noisy low-rank matrix exactly, under the three standard assumptions plus a large-signal condition.","keywords":["matrix completion","exact recovery","infinity norm","Davis-Kahan-Wedin theorem","low-rank perturbation","noisy observations","random sampling","singular value thresholding"],"falsifier":"Numerically evaluate the ratio $\\|\\tilde{A}_s - A_s\\|_\\infty / \\big[\\sigma_s r (\\|E\\|/\\sigma_s + 2r\\|U^T E V\\|_\\infty/\\delta_s + 2r y/(\\delta_s \\sigma_s))\\big]$ over a large set of random low-rank $A$ and Gaussian $E$ with $r=2$, $m=n=10^3$. If the supremum of this ratio exceeds the universal constant in Theorem 3.2 by more than a small factor, the new Davis-Kahan-Wedin bound is violated, and a single such violation with fixed dimensions, verified by exact arithmetic, would settle the claim.","tokens_in":53746,"feed_emoji":"🔢","tokens_out":7181,"duration_ms":59757,"temperature":0.7,"pith_summary":"This paper claims that exact recovery of a low-rank matrix from a small random sample of noisy entries can be achieved by a single truncated singular value decomposition followed by rounding, under only the three standard assumptions of the field: low rank, incoherent (delocalized) singular vectors, and sufficiently dense sampling. Previous algorithms that achieved exact recovery in the noisy setting needed an extra spectral condition, either a bounded condition number or large gaps between consecutive singular values; this work removes both. The price is a large-signal condition on the top singular value, which the paper argues is mild and often automatic. If the claim is right, the practical consequence is that the simplest possible pipeline, estimate density, rescale, truncate, round, provably recovers every entry of a bounded-precision matrix with high probability.","feed_headline":"Exact noisy matrix recovery without spectral-gap assumptions","feed_subtitle":"A single truncated SVD plus rounding recovers every entry, removing prior condition-number and gap conditions.","key_machinery":"The central object is the new infinity-norm Davis-Kahan-Wedin theorem (Theorem 3.2). It bounds $\\|\\tilde{A}_s - A_s\\|_\\infty$ by $C \\tau_1 \\tau_2 \\sigma_s r (\\|E\\|/\\sigma_s + 2r\\|U^T E V\\|_\\infty/\\delta_s + 2r y/(\\delta_s \\sigma_s))$, where the $\\tau$'s are coherence parameters of the interaction between the noise and the singular vectors, $\\delta_s$ is the singular-value gap, and $y$ measures the size of diagonal blocks of $E E^T$ in the singular basis. The proof machinery is a resolvent contour-integral expansion: after symmetrizing the SVD, the difference of spectral projectors is written as a power series in the noise, each term of which is a product of monomials whose integral coefficients are bounded by contour-integral estimates; a combinatorial walk-counting argument controls the sum, and the series is summed geometrically. The random version (Theorem 3.3) uses new semi-isotropic bounds for powers of random matrices to convert the deterministic $\\tau$'s into explicit polylogarithmic factors.","core_discovery":"The paper proves (Theorem 1.5) that, under low rank $r \\le \\log^2 N$, incoherence $\\mu_0$, sampling density (19), bounded finite-precision entries and bounded noise, and the large-signal bound $\\sigma_1 \\ge 100 r K \\sqrt{r_{\\max} N / p}$, the first three steps of the algorithm AR2 return a matrix $\\tilde{A}_s$ with $\\|\\tilde{A}_s - A\\|_\\infty \\le \\varepsilon_0/3$ with probability $1 - O(N^{-1})$; rounding to the nearest multiple of $\\varepsilon_0$ then recovers $A$ exactly. The algorithm needs only an upper bound on the rank, not the rank itself: the truncation index $s$ is chosen as the largest gap of the rescaled observed matrix above a threshold. The mathematical core is a new infinity-norm perturbation theorem (Theorem 3.2), an analogue and extension of the Davis-Kahan-Wedin theorem, which bounds how much the best rank-$s$ approximation of $A+E$ moves in the infinity norm as a function of the noise $E$, the interlacing term $U^T E V$, and coherence-type parameters $\\tau_1, \\tau_2$, under a condition on the noise-to-gap ratio.","pith_inferences":["The paper's phrase 'only three basic assumptions' is slightly generous: the large-signal premise is an additional formal assumption, although it is a signal-to-noise floor rather than a spectral-shape condition, and may be information-theoretically unavoidable.","A natural stress test is to run AR2 with several equal large singular values (zero gap) and $\\sigma_1$ at the stated threshold; the cutoff rule should still select a valid $s$, but the numerical margin is likely thin near the boundary of the sampling condition.","The semi-isotropic power bounds for random matrices (Lemma 4.2) appear reusable for entrywise eigenvector or singular-vector analyses in other settings, such as community detection or spectral clustering.","The deterministic Theorem 3.2 replaces incoherence with a general condition on the noise and the singular vectors; identifying natural non-random perturbations that satisfy this condition could widen the theorem's range."],"forward_implications":["Exact noisy completion becomes a one-pass truncated-SVD plus rounding procedure; no iterative cleaning and no exact knowledge of the rank are required, only an upper bound $r_{\\max}$.","The sampling density bound in the base case is $O(N \\log^{10} N)$ with no factor of the condition number, matching earlier noiseless spectral bounds up to polylogarithmic factors.","The large-signal condition is the only new formal requirement; the paper argues it is usually implied by normalization and the classical phase-transition threshold for random perturbations.","The deterministic infinity-norm perturbation bound is a standalone matrix-analysis result, applicable beyond matrix completion whenever a low-rank matrix is perturbed by bounded-moment noise."],"supporting_citations":[{"why":"Supplies the Approximate-and-Round algorithm and the prior infinity-norm Davis-Kahan bound that this paper extends by removing the gap assumption.","marker":"[6]"},{"why":"Establishes the first infinity-norm recovery result in the noisy setting, at the cost of a small-condition-number assumption; the paper removes that assumption.","marker":"[1]"},{"why":"Source of the contour-integral and combinatorial-expansion method used to prove the new infinity-norm perturbation theorem.","marker":"[38]"},{"why":"Defines the noisy matrix-completion model and the RMSE benchmarks that the exact-recovery result is compared against.","marker":"[9]"},{"why":"Introduces the three basic assumptions (low rank, incoherence, density) and the convex-optimization baseline.","marker":"[10]"},{"why":"Provides the spectral-norm bound $\\|E\\| = O(K\\sqrt{N/p})$ used in the proof of Theorem 1.5.","marker":"[39]"},{"why":"The classical singular-subspace perturbation theorem that Theorem 3.2 generalizes to the infinity norm.","marker":"[41]"}],"fun_headline_variants":["Exact noisy matrix recovery with only SVD and rounding","No spectral gaps needed for exact matrix completion","Infinity norm approach achieves exact noisy recovery","Truncated SVD plus rounding gives exact recovery"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the large-signal condition $\\sigma_1 \\ge 100 r K \\sqrt{r_{\\max} N / p}$: if the top singular value falls below this level, the argument that a valid truncation index $s \\le r$ exists and that the tail $\\sigma_{s+1}$ is small collapses, so the infinity-norm guarantee no longer follows.","fun_headline_variants_meta":{"raw":{"variants":["Exact noisy matrix recovery with only SVD and rounding","No spectral gaps needed for exact matrix completion","Infinity norm approach achieves exact noisy recovery","Truncated SVD plus rounding gives exact recovery"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000554,"raw_usage":{"total_tokens":2761,"prompt_tokens":1192,"completion_tokens":1569,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":808,"completion_tokens_details":{"reasoning_tokens":1509}},"tokens_in":808,"tokens_out":1569,"duration_ms":10671,"temperature":1.0,"reasoning_tokens":1509,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T20:53:01.597143+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Numerically evaluate the ratio $\\|\\tilde{A}_s - A_s\\|_\\infty / \\big[\\sigma_s r (\\|E\\|/\\sigma_s + 2r\\|U^T E V\\|_\\infty/\\delta_s + 2r y/(\\delta_s \\sigma_s))\\big]$ over a large set of random low-rank $A$ and Gaussian $E$ with $r=2$, $m=n=10^3$. If the supremum of this ratio exceeds the universal constant in Theorem 3.2 by more than a small factor, the new Davis-Kahan-Wedin bound is violated, and a single such violation with fixed dimensions, verified by exact arithmetic, would settle the claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Approximate-and-Round algorithm and the prior infinity-norm Davis-Kahan bound that this paper extends by removing the gap assumption."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the first infinity-norm recovery result in the noisy setting, at the cost of a small-condition-number assumption; the paper removes that assumption."},{"cited_title":"Cand` es and Yaniv Plan,Matrix completion with noise , Proceedings of the IEEE 98 (2010), no","cited_arxiv_id":null,"evidence_quote":"Defines the noisy matrix-completion model and the RMSE benchmarks that the exact-recovery result is compared against."},{"cited_title":"Cand` es and Benjamin Recht,Exact matrix completion via convex optimization , Found","cited_arxiv_id":null,"evidence_quote":"Introduces the three basic assumptions (low rank, incoherence, density) and the convex-optimization baseline."},{"cited_title":"6, 721–736","cited_arxiv_id":null,"evidence_quote":"Provides the spectral-norm bound $\\|E\\| = O(K\\sqrt{N/p})$ used in the proof of Theorem 1.5."},{"cited_title":"Informationsbehandling (BIT) 12 (1972), 99–111","cited_arxiv_id":null,"evidence_quote":"The classical singular-subspace perturbation theorem that Theorem 3.2 generalizes to the infinity norm."}],"review_version":1}