{"id":"dc604569-c271-4acd-9937-d6753a175e7d","arxiv_id":"2412.10005","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"A residual spectral matching estimator for noisy matrix completion matches the singular values of residuals to those of sparse random matrices and claims minimax optimal error rates.","lead":"Matrix completion usually fills in missing entries by minimizing the squared difference between observed and predicted values. This paper instead checks whether the leftover errors have the same singular-value signature as pure random noise, and uses that check to guide estimation, claiming better results when noise is strong.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems are unverifiable: all proofs are deferred to a missing appendix, so the minimax-optimality claim cannot be checked.","rationale":"The reader correctly identifies that no proofs are present and that the central claims are unverifiable, which alone justifies not accepting the paper. The reader also correctly flags the inconsistency between equation (4) and Algorithm 1. However, the reader's weakest_assumption goes further by focusing on the signal-leakage risk into the bulk of the residual spectrum; this is a substantive scientific concern, but since the proofs are absent, the primary blocking issue is verifiability, not the specific technical assumption. The reader's verdict of REJECT is too strong for a preprint with no proofs: the correct disposition is UNVERDICTED, pending the appendix and supplementary material. The load-bearing concern is that the paper's central claim cannot be checked, not that it is necessarily wrong. Agreement is partial because the reader's identified weakest assumption is plausible but secondary to the missing derivations.","tokens_in":22184,"tokens_out":1451,"duration_ms":13902,"concrete_test":"Post the missing appendix and supplementary material, and verify the key steps: (i) re-derive Lemma 4.1's universality bound with the stated n^{-3} probability for sparse Gaussian/bounded-noise matrices; (ii) re-derive Lemma 4.2's separation threshold using the singularity of the loss; (iii) confirm that Theorem 4.1's constant (3+5κ)(2+2√ρ+o(1)) follows from Lemmas 4.1-4.2 without hidden log factors. Also check whether Algorithm 1's line 7 matches equation (4) after the sqrt(m) normalization.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"The paper's central claim, Theorem 4.1 (Frobenius error bound matching the minimax lower bound for the rank-constrained estimator) and its nuclear-norm analogue Corollary 4.3, are stated with no proof in the main text. Section 4 repeatedly cites 'the Appendix' and 'online Supplementary Material', but neither is present in the arXiv posting. Lemma 4.1 (universality of sparse random matrices), Lemma 4.2 (separation of the loss), and Theorem 4.2/Corollary 4.3 all depend on these absent derivations. Additionally, the criterion (4) defines the working standard deviation with a factor of sqrt(m) in the denominator, while Algorithm 1 (line 7) computes it without that factor; this changes the objective actually optimized. The core statistical argument that bulk singular values of the residual P_Omega(M0 - M) + P_Omega(H) are insensitive to the low-rank perturbation is plausible, but the no-log result depends on delicate eigenvalue rigidity estimates for sparse matrices that are not shown. Absent proofs, the claim of optimality with no logarithmic factors cannot be accepted.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a residual spectral matching criterion for noisy matrix completion. Instead of minimizing the Frobenius norm of the residual Y - P_Omega(M), the authors compare the ordered singular values of the scaled residual to the expected singular values of a sparse Gaussian random matrix with the same observation probability, using a Monte Carlo estimate of the reference spectrum and a data-dependent working standard deviation psigma(M). Estimators under both a strict rank constraint and a nuclear-norm constraint are analyzed, with Theorem 4.1 and Corollary 4.3 claiming Frobenius error bounds that match the known minimax lower bound of order sigma sqrt(mr/p) without logarithmic factors. An alternating gradient algorithm with a pseudo-gradient is proposed, and its convergence is claimed in Theorem 4.3. Numerical experiments on simulated data and on Netflix and Amazon datasets show consistent gains over least-squares baselines, particularly at high noise levels.","tokens_in":22453,"tokens_out":9566,"duration_ms":110665,"significance":"If the theoretical claims were fully established, the paper would make a substantive contribution: it introduces a genuinely different loss function for noisy matrix completion based on random-matrix spectral information, and it claims rate-optimal estimation without logarithmic factors for both rank-constrained and nuclear-norm estimators. The matrix-denoising motivation in Section 2.2 is compelling, and the numerical results, especially the rank-misspecification robustness in Table 3 and the high-noise gains in Figure 4, are suggestive. The paper also spells out explicit dependence on the condition number kappa and aspect ratio rho in the bounds. However, the central theoretical results are currently unverifiable because all proofs are deferred to an appendix and supplementary material that do not appear in the posted version, and Algorithm 1 is inconsistent with the loss definition in Eqs. (4) and (8). The significance can only be assessed after these issues are resolved.","major_comments":[{"comment":"The central theoretical claims are unverifiable as posted. Lemmas 4.1-4.3, Theorems 4.1-4.3, and Corollaries 4.1-4.4 are all stated with proofs relegated to \"the Appendix\" and \"online Supplementary Material\" (see the end of Section 1.3 and the preamble to Section 4), but neither the appendix nor the supplementary file appears in the arXiv posting. Theorem 4.1 and Corollary 4.3 are exactly the load-bearing minimax-optimality claims of the paper, and their proofs would require delicate eigenvalue rigidity and low-rank perturbation arguments for sparse random matrices that cannot be reconstructed from the main text. As it stands, the optimality claim cannot be checked.","section":"Section 4 (all results)"},{"comment":"Algorithm 1 is inconsistent with the paper's own definitions. Line 7 computes psigma^{(k+1)} = sum_{i=n/3}^{2n/3} D^{(k+1)}_{i,i} / part_sum, whereas Eq. (4) defines psigma(M) with an additional factor 1/sqrt(m) in the denominator, so the two quantities differ by a factor sqrt(m). Line 8 then forms sum_i w_i (D_{i,i} - psigma^{(k+1)} lambda_i) u_i v_i^T, which omits the 1/(sqrt(m) psigma) prefactor appearing in Eq. (8) and applies P_Omega only later in lines 9-10. Although constant factors could in principle be absorbed into the step size eta_k, the algorithm as written does not minimize the loss L defined by Eqs. (3)-(5), and Theorem 4.3's notation psigma(M^{(k)}) is ambiguous about which convention is used. This needs correction or explicit clarification.","section":"Section 3.2, Algorithm 1, Eqs. (4) and (8)"},{"comment":"The statement of Lemma 4.2 appears garbled: the condition is written as \"if ||M0-M||_F - (3+5kappa)(2+2sqrt(rho)+C^{1/2}) sigma sqrt(mr/p) greater than or similar to p log^{-1} m sigma sqrt(mr/p)\", which mixes a difference with a lower bound in a way that is not a well-formed hypothesis. A precise statement is essential because the lemma supplies the separation of the spectral matching loss that underlies Theorem 4.1. Please rewrite the condition and correct the typographical corruption.","section":"Section 4.1, Lemma 4.2"},{"comment":"Assumption 1(c) is difficult to parse as printed: the expression \"sigma greater than or similar to ((mn)^{-1/2} ||M0||_F)^{r?} [1/2 m^{-1/2} log^{1/2} n]\" contains unclear exponents and brackets. Since this assumption plays a role in the proof strategy and in Corollary 4.1, it must be restated cleanly so that the reader can verify which noise levels are covered.","section":"Section 4, Assumption 1(c)"}],"minor_comments":[{"comment":"The title contains a spacing artifact, \"MA TRIX COMPLETION\", and similar spacing artifacts appear elsewhere; the manuscript should be carefully proofread.","section":"Title and throughout"},{"comment":"The summation notation in Eq. (4) is rendered as \"ri=2n{3 i=n{3\" and should be sum_{i=n/3}^{2n/3}; the same notation should be used consistently in Algorithm 1.","section":"Equation (4)"},{"comment":"The caption says \"based on 100 repeated experiments\"; this should read \"based on 100 replications\" or \"based on 100 independent experiments\" for clarity.","section":"Section 2.2, Table 1 caption"},{"comment":"The word \"minmax\" should be \"minimax\".","section":"Section 4.1, Remark 4.1"},{"comment":"The text states that psigma(M) \"approximates the standard deviation sigma of the noise\"; this is accurate only after the sqrt(m) factor in Eq. (4) is accounted for, and the sentence should be clarified to avoid confusion with the algorithm's psigma in line 7.","section":"Section 3.1, text after Eq. (4)"},{"comment":"The external URLs for the Netflix and Amazon data are useful, but the paper should also state the exact preprocessing steps for the Amazon data rather than deferring them entirely to the supplementary material, since the supplementary material is not currently available.","section":"Section 5.2 and 5.3"}],"recommendation":"reject","confidential_remarks":"The numerical experiments are well executed and the core idea is interesting, but the manuscript in its current form cannot be evaluated because all proofs are missing and Algorithm 1 does not match the stated loss function. If the authors supply the full appendix and supplementary material and correct the algorithmic inconsistency, the paper may be worth reconsidering; however, as posted, the central claims are unsupported. I would also note that the claim of being the first to use low-rank perturbation of random matrices in noisy matrix completion should be checked carefully against the literature before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the residual spectral matching criterion is genuinely new in the matrix completion literature—comparing ordered residual singular values to Monte Carlo expectations for the sparse Gaussian ensemble is not in any of the cited work, and the matrix-denoising motivation in Section 2.2 is well done. The citation pattern is right (Benaych-Georges-Nadakuditi, the sparse local law papers, Koltchinskii-Lounici-Tsybakov and Negahban-Wainwright for lower bounds). To their credit, the paper is explicit that the advantage is for high-noise regimes (Assumption 1(c), Remark 4.2) and that heterogeneous noise is hard (Section 6).\n\nThe problem is that you cannot verify the central claims in this posting. Every lemma and theorem in Section 4 is deferred to an Appendix or online supplement, and neither is present in the arXiv PDF. Theorems 4.1 and Corollary 4.3 claim the minimax rate with no log factors, and that rests on a separation argument (Lemma 4.2) showing the bulk of the residual spectrum is insensitive to P_Ω(M0-M). That is not obvious: that perturbation is sparse and may be full-rank, and the working standard deviation (4) is estimated from the middle third of the residual singular values. The needed universality and rigidity results for sparse matrices are delicate. Without proofs, 'optimal, no log' is a claim, not an established result.\n\nThere is also a real mechanical inconsistency: (4) divides by √m when estimating the working standard deviation, but Algorithm 1 line 7 omits that factor. As written, the algorithm drives singular values toward targets that are √m too large, so the implemented objective differs from the analyzed one. It looks like a typo, and the experiments are suggestive enough that I would bet the corrected version works, but the current text does not let a reader reproduce that.\n\nSmaller point: in the Amazon table, Estimator 2 loses to Baseline 2 in scenario 2 (0.924 vs 0.866), which contradicts the blanket claim of larger gaps everywhere.\n\nVerdict: reject as posted, but do not desk-reject the idea. Ask the authors for the appendix and a corrected Algorithm 1, then send it out. The criterion deserves referee time.","headline":"New spectral criterion, real idea, but the posted paper states every theorem without proofs and its algorithm doesn't match the analyzed objective; reject as posted, re-review with the appendix.","tokens_in":22912,"tokens_out":9405,"would_cite":false,"duration_ms":99903,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H12","60B20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Matching the residual spectrum of a matrix completion estimate to the spectrum of a sparse random noise matrix yields an estimator that attains the minimax optimal Frobenius error rate $\\sigma\\sqrt{mr/p}$.","keywords":["noisy matrix completion","residual spectral matching","low-rank perturbation","sparse random matrix","spectral property","random matrix theory","nuclear norm"],"falsifier":"Take an incoherent rank-$r$ target whose smallest nonzero singular value is close to the noise bulk edge (violating the bounded-condition-number assumption), draw noise with $\\sigma$ at or below the Assumption 1(c) threshold, and compute the rank-$r$ minimizer of (3) over many seeds. If the empirical Frobenius error consistently exceeds the Theorem 4.1 bound, or if the middle-third residual singular values deviate from the sparse-random-matrix expectation $\\hat{\\lambda}$, then the bulk-separation argument in Lemma 4.2 is wrong.","tokens_in":21971,"feed_emoji":"🎯","tokens_out":10487,"duration_ms":106067,"temperature":0.7,"pith_summary":"Noisy matrix completion is usually solved by least squares, which compares only the sizes of residuals. This paper proposes judging an estimator by the entire spectrum of its residual matrix: the ordered singular values of $Y-P_\\Omega(M)$ are matched, in a weighted $L^2$ sense, to the expected singular values of a sparse Gaussian random matrix with the same missingness pattern. The paper claims that this residual spectral matching criterion is statistically optimal: for a rank-$r$ incoherent target and a suitable weight, the estimator's Frobenius error reaches the known lower bound $\\sigma\\sqrt{mr/p}$, and the convex nuclear-norm variant attains the same rate without a logarithmic factor. A pseudo-gradient algorithm is shown to reach that optimal statistical error in finitely many iterations, and simulations plus two real recommendation datasets show gains over least squares, mainly at high noise levels. The motivation is that low-rank signals perturb only the edge of the noise spectrum, so matching the bulk spectrum recovers information that squared residuals throw away.","feed_headline":"Spectral matching hits minimax-optimal matrix completion","feed_subtitle":"Residual singular values compared with sparse random matrices remove log factors and beat least squares at high noise.","key_machinery":"The load-bearing object is the residual spectral matching loss $l(N;\\omega)=\\sum_i \\omega_i(\\sigma_i(N)-\\hat{\\lambda}_i)^2$, the weighted $L^2$ distance between the ordered singular values of the scaled residual $(Y-P_\\Omega(M))/(\\sqrt{m}\\,\\hat{\\sigma}(M))$ and $\\hat{\\lambda}$, a Monte Carlo estimate of the expected singular values of a sparse Gaussian random matrix with observation probability $p$. The spectral separation idea carries the argument: the low-rank perturbation $P_\\Omega(M_0-M)$ moves mainly the top edge singular values, while the bulk of the residual spectrum follows the noise $P_\\Omega(H)$ and its limiting sparse-random-matrix law. The working standard deviation $\\hat{\\sigma}(M)$ in (4) is computed from the middle third of the residual singular values to isolate the noise bulk, and the pseudo-gradient in (8) projects the singular-value gradient back through $P_\\Omega$, making iterative minimization feasible without an explicit gradient.","core_discovery":"The central claim is Theorem 4.1: when the estimation rank equals the true rank $r$ and the noise is not too small, the estimator minimizing the residual spectral matching loss (3) over an incoherent rank-$r$ class satisfies $\\|\\widehat{M}-M_0\\|_F \\le (3+5\\kappa)(2+2\\sqrt{\\rho}+o(1))\\sigma\\sqrt{mr/p}$ with high probability. This matches the problem's minimax lower bound, so the criterion is statistically optimal, and Corollary 4.3 shows that the nuclear-norm-constrained version (6) also attains a no-logarithm upper bound once the penalty $\\lambda$ is tuned. The proof treats the observation as a sparse random matrix $P_\\Omega(H)$ plus the low-rank perturbation $P_\\Omega(M_0-M)$, then combines two facts: at the true $M_0$ the loss is small (Lemma 4.1), while any rank-$r$ matrix far from $M_0$ pushes the loss above the noise floor (Lemma 4.2).","pith_inferences":["Editorial inference: because the loss already isolates edge singular values from the bulk, the same machinery could be turned into a data-driven rank selection rule — stop adding dimensions when the residual spectrum starts matching the null sparse-random-matrix law.","Editorial inference: the separation assumption implies the method should be paired with a preprocessing step that estimates the noise variance structure; for grouped or heteroscedastic noise, the middle-third scale estimator in (4) would need a per-block or per-column version.","Editorial inference: a direct stress test of the boundary is to push $\\sigma$ below the Assumption 1(c) cutoff while keeping the rank small; Corollary 4.1 predicts a correction proportional to $\\|M_0\\|_F\\sqrt{r^3\\log n/(mnp)}$, and the empirical advantage of spectral matching should visibly transfer to least squares.","Editorial inference: the low-rank-plus-noise spectral viewpoint is not specific to entrywise missingness, so the criterion may transfer to tensor completion, robust PCA, or dynamic matrix recovery whenever the residual array inherits a similar spiked structure."],"forward_implications":["For a correctly chosen rank $s=r$, Theorem 4.1 gives $\\|\\widehat{M}-M_0\\|_F \\le (3+5\\kappa)(2+2\\sqrt{\\rho}+o(1))\\sigma\\sqrt{mr/p}$, which is the minimax rate and makes the dependence on the condition number $\\kappa$ and aspect ratio $\\rho$ explicit.","With a tuned penalty $\\lambda$, the nuclear-norm estimator in Corollary 4.3 reaches the same order without the logarithmic factor that appears in classical convex relaxation bounds for noisy matrix completion.","If the rank is overestimated ($s>r$), Corollary 4.2 controls the error by a mix of $r^{1/2}$ and $s^{1/2}$ terms, and the simulations show the error grows more slowly than the least-squares baseline as $s$ increases.","The pseudo-gradient algorithm (Algorithm 1) converges linearly to the estimator and, by Corollary 4.4, reaches the statistical error $\\sigma\\sqrt{mr/p}$ in finitely many steps while keeping the incoherence parameter bounded.","Residual diagnostics improve as well: the residual singular values of fitted estimators align with the predicted sparse-random-matrix spectrum, whereas the least-squares residuals show outliers at both edges."],"supporting_citations":[{"why":"Supplies the low-rank perturbation limits of leading singular values and vectors that motivate the spectral-matching loss and the closed-form denoiser comparison in Section 2.","marker":"Benaych-Georges and Nadakuditi (2012)"},{"why":"Provides the nuclear-norm-penalized completion estimator and its near-optimal rate, which Corollary 4.3 improves by removing the logarithmic factor.","marker":"Koltchinskii, Lounici and Tsybakov (2011)"},{"why":"Theorem 3 gives the minimax lower bound $\\sigma\\sqrt{mr/p}$ that Theorem 4.1 and Corollary 4.3 are matched against.","marker":"Negahban and Wainwright (2012)"},{"why":"Establishes the sampling lower bound and near-optimal exact-completion benchmark used to frame the low-noise regime in Remark 4.2 and Assumption 3.","marker":"Candès and Tao (2010)"},{"why":"Provides the alternating gradient descent with implicit regularization and the Algorithm 2 baseline used in numerical comparisons; Theorem 4.3 builds on its techniques.","marker":"Ma et al. (2018)"},{"why":"Introduces nuclear-norm convex relaxation for exact completion, motivating the convex variant (6).","marker":"Candès and Recht (2009)"}],"fun_headline_variants":["Residual spectral matching nails minimax matrix completion","Sparse random matrices guide optimal matrix completion","Spectral trick beats least squares for noisy completion","No-log matrix completion from residual spectra","High-noise matrix completion via spectral residuals"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the middle third of the residual spectrum is governed almost entirely by the random noise, with the low-rank signal confined to the top edge, so the working standard deviation in (4) is trustworthy; when signal leaks into the bulk, the loss stops separating good from bad estimates.","fun_headline_variants_meta":{"raw":{"variants":["Residual spectral matching nails minimax matrix completion","Sparse random matrices guide optimal matrix completion","Spectral trick beats least squares for noisy completion","No-log matrix completion from residual spectra","High-noise matrix completion via spectral residuals"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000349,"raw_usage":{"total_tokens":1903,"prompt_tokens":937,"completion_tokens":966,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":900}},"tokens_in":553,"tokens_out":966,"duration_ms":9494,"temperature":1.0,"reasoning_tokens":900,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:28:23.274304+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take an incoherent rank-$r$ target whose smallest nonzero singular value is close to the noise bulk edge (violating the bounded-condition-number assumption), draw noise with $\\sigma$ at or below the Assumption 1(c) threshold, and compute the rank-$r$ minimizer of (3) over many seeds. If the empirical Frobenius error consistently exceeds the Theorem 4.1 bound, or if the middle-third residual singular values deviate from the sparse-random-matrix expectation $\\hat{\\lambda}$, then the bulk-separation argument in Lemma 4.2 is wrong.","supporting_citations":[],"review_version":1}