REVIEW 1 major objections 5 minor 17 references
Statistical Inferences of Linear Forms for Noisy Matrix Completion
T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Noisy matrix completion can support confidence intervals and tests for any linear summary of the matrix.
desk verdict A valuable conditional normality result for linear forms in noisy matrix completion, but the paper's own initial estimator does not satisfy the key assumption in the fixed-rank asymptotic regime. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the double-sample-debiased estimate: split the data in half, form an initial estimate from one half, and add the one-step correction $(d_1d_2/n_0)\sum_i(Y_i-\langle \hat M_{\mathrm{init}},X_i\rangle)X_i$ using the other half; repeat with the halves swapped. Projecting the two debiased matrices onto their top-$r$ singular subspaces and averaging gives $\hat M$. The proof is carried by a sharp perturbation expansion of the empirical singular subspaces, written as a series in powers of the noise matrix, which lets the paper control the $(2,\max)$-norm errors of the estimated singular vectors under sub-Gaussian noise. To provide the required initial estimator, the paper gives a rotation-calibrated gradient descent on the product of two Grassmann manifolds (rank-$r$ orthonormal frames modulo rotation) that converges geometrically with constant step sizes.
What would settle it
Simulate the procedure with $d_1=d_2=2000$, rank 3, noise $\sigma_\xi=0.6$, sample size $n=4r^2 d\log d$, and a linear form $T$ aligned with a singular vector; the studentized statistic should be approximately standard normal over repeated runs. If the histogram shows detectable bias or the coverage of the Wald intervals misses the nominal level at these sample sizes, the normality claim would be contradicted. A sharper test targets the boundary: for $T$ nearly orthogonal to the singular spaces (small alignment), Assumption 4 fails and the asymptotic normality should break down, which a simulation could confirm.
Extended reading notes
Core claim
Under the noisy matrix completion model $Y = \langle M, X\rangle + \xi$ with entries sampled uniformly and sub-Gaussian noise, the paper proves that the debiased and spectrally projected estimator $\hat M$ satisfies $\bigl(\operatorname{tr}(\hat M^{\top}T)-\operatorname{tr}(M^{\top}T)\bigr)\big/\bigl(\sigma_\xi(\|U^{\top}T\|_F^2+\|TV\|_F^2)^{1/2}\bigr)\cdot\sqrt{d_1d_2/n}\xrightarrow{d}N(0,1)$ whenever the initial estimator satisfies Assumption 1 and the incoherence, SNR, and alignment conditions hold. The same convergence remains true with estimated noise level and estimated singular vectors, so the statistic is directly usable for confidence intervals and tests. A notable corollary is that the asymptotic variance of the estimator is governed by how $T$ aligns with the singular spaces of $M$, not by the sparsity of $T$ alone, so dense linear forms are allowed when their alignment is sufficient.
Load-bearing premise
The argument collapses without an initial estimator whose maximum entry-wise error is $o_P(\sigma_\xi)$ under the paper's independent uniform sampling; the paper itself notes that such guarantees were previously proved mainly for sampling without replacement and positive semidefinite matrices, and supplies its own initial estimator only under stronger sample-size and SNR conditions.
Editorial extensions
If this is right
- Entrywise confidence intervals for the entries of $M$ become available at near-optimal sample sizes, $n$ on the order of $r d_1 \log d_1$ up to constants and log factors.
- Comparisons such as $H_0: M(i,j_1)=M(i,j_2)$, including group versions that aggregate over users, can be tested with asymptotic level control.
- The initial estimator only needs max-norm consistency $o_P(\sigma_\xi)$; its convergence rate does not enter the limiting distribution, so a suboptimal estimator can lead to optimal inference.
- The asymptotic variance of the linear-form estimator is determined by the alignment of $T$ with $M$'s singular spaces, so dense linear forms are allowed when their singular-space alignment is not small.
- The integrated mean squared error of the debiased projected estimator is $\sigma_\xi^2 r d_1 d_2 (d_1 + d_2)/n$ up to a $(1+o(1))$ factor, matching the minimax lower bound.
Reading between the lines
- A natural next step is to reweight the debiasing sum by inverse sampling probabilities for non-uniform entry sampling; the paper notes the calibration would change but does not develop it.
- The alignment condition suggests that tests are intrinsically more powerful for linear forms that lie partially in the row or column singular spaces, while forms wholly in the null space require a different limiting theory.
- The paper's numerical evidence suggests the procedure is insensitive to the estimated rank, but no proof is given; one testable extension is a rigorous rank-estimation scheme inside the debiasing loop.
- One could apply the same double-sample debiasing to other trace-regression designs with known second moment of the design, since the debiasing formula only needs $E[\operatorname{vec}(X)\operatorname{vec}(X)^\top] = (d_1d_2)^{-1} I$.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper develops a framework for statistical inference on general linear forms tr(M^T T) of a low-rank matrix M from n noisy, uniformly sampled entries of the matrix completion model (1.1). The procedure has four steps: splitting the sample in two, debiasing each half by an additive correction based on the other half, projecting the debiased matrices onto their top-r singular subspaces, and plugging the averaged projection into the linear form (Section 2). Theorem 1 establishes an asymptotic normality result with an explicit Berry-Esseen bound under an initial-estimator condition (Assumption 1: max-norm error o_P(sigma_xi)), an incoherence condition (Assumption 2), a sub-Gaussian noise and SNR condition (Assumption 3), and an alignment condition (Assumption 4). Theorem 2 extends the result to data-driven noise-variance and singular-subspace estimates, yielding confidence intervals and tests. Section 5 introduces a rotation-calibrated Grassmannian gradient descent algorithm (Algorithm 1) intended to supply the initial estimator, with geometric convergence proved in Theorem 3; Section 7 and the appendices contain the proofs, built on a de-localized perturbation expansion of empirical singular vectors (Theorem 4). Simulations with Gaussian and uniform noise and experiments on the Jester and MovieLens datasets illustrate the method.
Significance. If the conditional result holds, this is a substantial contribution to noisy matrix completion inference. The framework covers entries, differences of entries, and other sparse or moderate linear forms at near-optimal sample sizes, and it shows that the rate of the initial estimator is irrelevant provided it is max-norm consistent, which is a useful and somewhat surprising design principle. The proof machinery is a strength: Theorem 1 carries an explicit Berry-Esseen rate, the perturbation analysis in Section 7.1 and Lemmas 1-9 of the appendix provide sharp (2,max)-norm bounds for empirical singular vectors under sub-Gaussian noise, and the double-sample debiasing avoids the efficiency loss of single splitting. The verification of the theoretical input is, however, incomplete: the supplied initializer does not provably satisfy Assumption 1 in the fixed-rank regime, so the end-to-end guarantee of the procedure is not established; this is a load-bearing gap that a major revision should close.
major comments (1)
- [§5 (Theorem 3 and following paragraph); §3 (Assumption 1)] Assumption 1 (Section 2, eq. (2.1)) requires a sequence gamma_{n,d1,d2} -> 0 such that the initial estimators have max-norm error O(gamma sigma_xi), and the Berry-Esseen bound in Theorem 1 together with condition (3.5) requires gamma_n sqrt(log d1) -> 0. The paper's constructive verification, Theorem 3 (Section 5), proves ||Mhat^{(m)} - M||_max <= C6 mu_max kappa_0 sigma_xi sqrt(r^2 d1 log^2 d1 / n) under n >= C1 alpha_d kappa^6 mu^6 r^3 d1 log^2 d1. Substituting the minimal sample size gives ||Mhat^{(m)} - M||_max / sigma_xi = O(1/sqrt(r)) up to constants in mu, kappa, alpha_d; for fixed rank r, the regime used throughout the paper (r = 3 in Section 6.1, r = 2 in Section 6.2), this is a positive constant rather than a vanishing sequence. Consequently the claim on page 18 that 'Assumption 1 is satisfied with gamma_{n,d1,d2} = mu_max kappa_0 sqrt(r^2 d1 log^2 d1 / n)' is incorrect as stated, and the only initializer supplied by the paper does not instantiate Assumption 1 in fixed-rank asymptotics. Figure 1 corroborates this: the curve log(||Mhat - M||_max / sigma_xi) saturates at about -0.4, i.e., a max error near 0.67 sigma_xi, while the text of Section 6.1 states that the debiasing procedure requires o_P(sigma_xi); the histograms in Figures 2 and 3 are therefore not covered by Theorem 1. This gap is load-bearing for the paper's universality claim, because the abstract and Section 2 present Algorithm 1 as the concrete route to Assumption 1. The issue is fixable within scope: either require the sample size in Theorem 3 to satisfy n / (d1 log^2 d1) -> infinity, which makes gamma_n vanish for fixed r, or sharpen Algorithm 1's max-norm rate to sqrt(r d1 log d1 / n) via a leave-one-out analysis; the revision should also reconcile Figure 1 with Assumption 1.
minor comments (5)
- [§1 and §6.2] Several citations contain '[?]' placeholders (e.g., the Chernozhukov et al. reference on page 8 and the data-source descriptions for Jester and MovieLens on pages 19-20); these should be completed before the manuscript goes into production.
- [Assumption 3 and throughout §3] The phrase 'the noise xi is independent with X' should read 'independent of X'; this wording error appears in Assumption 3 and several times in Sections 3 and 7.
- [§1, page 6] The introduction states that 'All proofs are presented in the online supplement,' but the proofs of Theorems 1-4 and Lemmas 1-9 appear in the main text (§7 and Appendices A-I); the sentence should be corrected to match the actual organization.
- [§3.1, page 10] The statement that the procedure is 'generally robust to reasonable estimate of r' is acknowledged to lack rigorous justification; since all theorems assume r known, this claim should be explicitly labeled as an empirical observation so that the theoretical scope of the paper is unambiguous.
- [Theorem 1 and §7.2] The term '6 log d1 / d2^1' in Theorem 1's Berry-Esseen bound and the analogous '3/d2^1' terms in Lemma 4 appear to be typesetting artifacts of what should be expressions like 6 log d1 / d1^2; these should be reset in LaTeX so that the bounds are readable and verifiable.
Circularity Check
No circularity found: Theorem 1 is a conditional probabilistic statement derived from explicit concentration and Berry-Esseen bounds, not from its own conclusions.
full rationale
The derivation chain is not circular. Theorem 1 takes Assumption 1 (the existence of an entry-wise consistent initializer with max-norm error o_P(σξ)) as a hypothesis and proves asymptotic normality of the debiased, spectrally projected estimator by bounding the perturbation expansion in Lemmas 1-6 and applying Berry-Esseen to the leading linear term in Lemma 4. No parameter appearing in the theorem is fitted to the data used to evaluate the statistic; the normalization by σξ and by the true singular subspaces is replaced only in Theorem 2 by estimators whose consistency is proved from the same assumptions, not assumed. The self-citation to Xia (2019b) for the spectral expansion (7.11) is load-bearing but is a prior mathematical lemma used as a tool; the paper does not assume the target normality result, and it supplies the NMC-specific bounds itself. The paper also explicitly flags two limitations: that a max-norm guarantee under independent sampling is lacking (Section 2, after Assumption 1) and that a rigorous justification of rank-choice robustness has eluded it (Section 3.1). These are acknowledged gaps, not circular steps. The skeptical observation that Algorithm 1's Theorem 3 bound gives γ_n = O(r^{-1/2}) at the stated sample threshold when r is fixed is a possible gap in instantiating Assumption 1 for fixed-rank asymptotics, but it is a correctness concern about whether an input condition is met, not evidence that the theorem's output was assumed as an input.
Assumptions & free parameters
free parameters (1)
- rank r =
r=3 in simulations; r=2 in real data, chosen as the rank minimizing σ̂ξ
assumptions (8)
- domain assumption Assumption 1: initial estimator satisfies max-norm error o_P(σξ)
- domain assumption Assumption 2: incoherence of singular vectors U and V with parameter μmax
- domain assumption Assumption 3: independent centered sub-Gaussian noise
- domain assumption SNR condition λ_r ≥ C μmax κ0^2 σξ sqrt(α_d r d1^2 d2 log^2 d1 / n)
- domain assumption Assumption 4: alignment condition α_T on T with respect to singular spaces
- domain assumption Rank r known and κ(M) ≤ κ0
- standard math Spectral representation (7.11) for perturbed singular subspaces from Xia (2019b)
- standard math Standard probability tools: matrix Bernstein, Davis-Kahan/Wedin, Berry-Esseen
Cite this review
Pith. "Pith review of Statistical Inferences of Linear Forms for Noisy Matrix Completion." pith.science (2026). https://pith.science/paper/HBRFDSBA
@misc{pith2026190900116,
author = {Pith},
title = {Pith review of: Statistical Inferences of Linear Forms for Noisy Matrix Completion},
year = {2026},
howpublished = {\url{https://pith.science/paper/HBRFDSBA}},
note = {Machine review of arXiv:1909.00116}
}
read the original abstract
We introduce a flexible framework for making inferences about general linear forms of a large matrix based on noisy observations of a subset of its entries. In particular, under mild regularity conditions, we develop a universal procedure to construct asymptotically normal estimators of its linear forms through double-sample debiasing and low-rank projection whenever an entry-wise consistent estimator of the matrix is available. These estimators allow us to subsequently construct confidence intervals for and test hypotheses about the linear forms. Our proposal was motivated by a careful perturbation analysis of the empirical singular spaces under the noisy matrix completion model which might be of independent interest. The practical merits of our proposed inference procedure are demonstrated on both simulated and real-world data examples.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[2]
Then, ⏐⏐⟨ (ˆΘiˆΘT i − ΘΘT)A(ˆΘiˆΘT i − ΘΘT),~T ⟩⏐⏐ ≤ ‖‖(ˆUiˆU T i −UU T)M(ˆViˆV T i −VV T) ‖‖ max·‖T‖𝓁1 ≤‖T‖𝓁1·‖ Λ‖‖ˆUiˆU T i −UU T‖2,max‖ˆViˆV T i −VV T‖2,max. Therefore, under the event of Theorem 4, ⏐⏐⟨ (ˆΘiˆΘT i − ΘΘT)A(ˆΘiˆΘT i − ΘΘT),~T ⟩⏐⏐ ≤C2κ0µ2 max‖T‖𝓁1σξ √ r2d1 logd1 n · σξ λr √ d2 1d2 logd1 n . H Proof of Lemma 7 By eq. (7.5), we write d1d2 N0...
work page 2012
-
[4]
Ji Chen, Dekai Liu, and Xiaodong Li. Nonconvex rectangular matrix completion via gradient descent without 𝓁2,∞ regularization. arXiv preprint arXiv:1901.06116 , 2019a. Yudong Chen and Martin J Wainwright. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.03025,
work page Pith review arXiv 1901
-
[9]
A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
48 Lingxiao Wang, Xiao Zhang, and Quanquan Gu. A unified computational and statistical framework for nonconvex low-rank matrix estimation. arXiv preprint arXiv:1610.05275 ,
-
[10]
71 Then, we obtain ‖‖(ˆU (t)ˆL(t) G −UˆO(t) U ˆL(t) G ) ( I−η·ˆL(t)T G ˆO(t)T U ΛˆO(t) V ˆR(t) G (ˆΛ(t))−1)‖‖ 2,max≤ ( 1− 9η 10 ) ·‖ˆU (t)−UˆO(t) U‖2,max. Since‖ˆU (t)‖max≤ 2µmax √ r/d1, by (I.2), we get η ‖‖ˆU (t)(ˆG(t)− ˆO(t)T U ΛˆO(t) V )ˆR(t) G (ˆΛ(t))−1‖‖ 2,max≤ 2η‖ˆU (t)‖2,max·‖ ˆG(t)− ˆO(t)T U ΛˆO(t) V‖· λ−1 r ≤C3 µmaxησξ λr · √ r2d2 logd1 N0 +C4ηκ...
work page 2012
-
[11]
Qinqing Zheng and John Lafferty. Convergence analysis for rectangular matrix completion using burer-monteiro factorization and gradient descent. arXiv preprint arXiv:1605.07051,
-
[13]
Next, we bound the third moment of ξ (⟨ U⊥U T ⊥XVV T,T ⟩ + ⟨ UUXV⊥V T ⊥,T ⟩)
As a result, the second moment is Eξ2(⟨ U⊥U T ⊥XVV T,T ⟩ + ⟨ UUXV⊥V T ⊥,T ⟩)2 = σ2 ξ d1d2 ( ‖V TT TU⊥‖2 F +‖U TTV⊥‖2 F ) . Next, we bound the third moment of ξ (⟨ U⊥U T ⊥XVV T,T ⟩ + ⟨ UUXV⊥V T ⊥,T ⟩) . By the sub- Gaussian Assumption 3, we have E|ξ|3⏐⏐⟨ U⊥U T ⊥XVV T,T ⟩ + ⟨ UU TXV⊥V T ⊥,T ⟩⏐⏐3 ≤C2σ3 ξ· E ⏐⏐⟨ U⊥U T ⊥XVV T,T ⟩ + ⟨ UU TXV⊥V T ⊥,T ⟩⏐⏐3 =C2σ3 ...
work page 1941
-
[15]
We then prove the upper bound for ‖‖‖ (ˆG(t)− ˆO(t)T U ΛˆO(t) V ) − d1d2 N0 ∑ j∈D2t ⟨ˆG(t)− ˆO(t)T U ΛˆO(t) V ,ˆU (t)TXjˆV (t)⟩ˆU (t)TXjˆV (t) ‖‖‖ where ˆG(t) is dependent with{(Xj,Yj)}j∈D2t. To this end, we write ‖‖‖ (ˆG(t)−ˆO(t)T U ΛˆO(t) V ) − d1d2 N0 ∑ j∈D2t ⟨ˆG(t)− ˆO(t)T U ΛˆO(t) V ,ˆU (t)TXjˆV (t)⟩ˆU (t)TXjˆV (t) ‖‖‖ ≤‖ˆG(t)− ˆO(t)T U ΛˆO(t) V‖· su...
work page 1998
-
[16]
By the definition ofN1/3(Or), ‖‖‖ (ˆG(t)−ˆO(t)T U ΛˆO(t) V ) − d1d2 N0 ∑ j∈D2t ⟨ˆG(t)− ˆO(t)T U ΛˆO(t) V ,ˆU (t)TXjˆV (t)⟩ˆU (t)TXjˆV (t) ‖‖‖ ≤3‖ˆG(t)− ˆO(t)T U ΛˆO(t) V‖· max A∈N1/3(Or) ‖‖‖A− d1d2 N0 ∑ j∈D2t ⟨A,ˆU (t)TXjˆV (t)⟩ˆU (t)TXjˆV (t) ‖‖‖. For eachA∈N 1/3(Or), ‖‖⟨A,ˆU (t)TXiˆV (t)⟩ˆU (t)TXiˆV (t)‖‖≤‖ ˆU (t)TXiˆV (t)‖⋆·‖ˆU (t)TXiˆV (t)‖≤‖ ˆU (t)‖2 ...
work page 2017
Show all 17 references
-
[1941]
A singular value thresholding algo- rithm for matrix completion
Jian-Feng Cai, Emmanuel J Cand` es, and Zuowei Shen. A singular value thresholding algo- rithm for matrix completion. SIAM Journal on optimization , 20(4):1956–1982,
1956
-
[1972]
Confidence region of singular subspaces for high-dimensional and low-rank matrix regression
Dong Xia. Confidence region of singular subspaces for high-dimensional and low-rank matrix regression. IEEE Transactions on Information Theory , 2019a. Dong Xia. Normal approximation and confidence region of singular subspaces.arXiv preprint arXiv:1901.00304, 2019b. Dong Xia and...
1901 arXiv
-
[1998]
A moment inequality with an application to the central limit theorem
Carl-Gustav Esseen. A moment inequality with an application to the central limit theorem. Scandinavian Actuarial Journal, 1956(2):160–170,
1956
-
[2009]
The power of convex relaxation: Near-optimal matrix completion
Emmanuel J Cand` es and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. arXiv preprint arXiv:0903.1476 ,
-
[2011]
Implicit regularization in noncon- vex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution
47 Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in noncon- vex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution. arXiv preprint arXiv:1711.10467 ,
-
[2014]
Matrix completion from a few entries
Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from a few entries. IEEE transactions on information theory , 56(6):2980–2998, 2010a. Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from noisy entries. Journal of Machine ...
-
[2015]
Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. arXiv preprint arXiv:1902.07698 , 2019b. Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan. Inference ...
1902 arXiv
-
[2016]
Recall that ˆZ (1) 1 is defined by ˆZ (1) 1 = d1d2 n0 n∑ i=n0+1 ξiXi where{(ξi,Xi)}n i=n0+1 are i.i.d
49 A Proof of Lemma 1 W.L.O.G., we only prove the bounds for ‖ˆZ (1) 1 ‖ and‖ˆZ (1) 2 ‖. Recall that ˆZ (1) 1 is defined by ˆZ (1) 1 = d1d2 n0 n∑ i=n0+1 ξiXi where{(ξi,Xi)}n i=n0+1 are i.i.d. The ψα-norm of a random variable Y is defined by‖Y‖ψα = inf{t >0 : E exp|Y/t|α ≤ 2} for...
2011
-
[2018]
Uncertainty quantifi- cation for matrix compressed sensing and quantum tomography problems
45 Alexandra Carpentier, Jens Eisert, David Gross, and Richard Nickl. Uncertainty quantifi- cation for matrix compressed sensing and quantum tomography problems. arXiv preprint arXiv:1504.03234,
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.