Inference and Uncertainty Quantification for Noisy Matrix Completion

1.1 Motivation: inference and uncertainty quantification?

• Noisy matrix completion estimates are difficult to use for valid, efficient inference because their distributions are hard to characterize and prior error bounds can yield overly conservative confidence regions.The paper addresses this gap with de-biased estimators and distributional characterizations.Source: §1.1 · p. 3, §1.2 · p. 3

1.2 A glimpse of our contributions

• The procedures support confidence intervals for observed or missing matrix entries and confidence regions for low-rank factors, modulo global ambiguity.Source: §1.2 · p. 3
• The inferential procedures avoid sample splitting, preventing unnecessary widening of confidence intervals and regions from insufficient data use.Source: §1.2 · p. 3
• The proposed confidence intervals and regions are described as optimal in some sense, and the approach treats convex and nonconvex estimators in a unified framework.Source: §1.2 · p. 3
• The de-biased estimators' Euclidean error bounds match an oracle lower bound precisely, including the pre-constant; the paper presents this as the first such result for a computationally feasible algorithm.Source: §1.2 · p. 3

• The target is an unknown rank-r matrix M⋆ with compact SVD M⋆ = U⋆Σ⋆V⋆⊤, and X⋆, Y⋆ are its balanced low-rank factors.Source: §2 · p. 4
• Each matrix entry is observed independently with probability p, with independently generated noise at observed locations.The sampling set is uniformly random, and PΩ projects onto matrices supported on observed indices.Source: §2 · p. 4
• A standard incoherence condition on the singular subspaces requires their row energy to be reasonably spread, with µ denoting the incoherence parameter.Source: §2 · p. 4

3 Inferential procedures and main results

• The inferential framework starts from convex relaxation and nonconvex optimization and aims to establish near-Gaussianity and optimality for de-biased estimators.Source: §3 · p. 4

3.1 Background: convex and nonconvex estimators

• The convex baseline replaces the rank penalty with the nuclear norm, while the nonconvex alternative represents the matrix through two low-rank factors.The cited convex program has near-optimal order-wise estimation accuracy under mild conditions and a proper regularization parameter; the paper focuses on a two-stage gradient-descent algorithm for the nonconvex program.Source: §3.1 · p. 5
• With a properly chosen regularization parameter, the convex estimate, its best rank-r approximation, and the nonconvex estimate are exceedingly close, enabling guarantees to transfer between approaches.Source: §3.1 · p. 5

3.2 Constructing de-biased estimators

• Because regularized least-squares estimates can be biased, the paper corrects the estimate and projects the corrected matrix onto rank-r matrices to suppress variability outside the principal subspace.The unprojected correction is heuristically unbiased under independence, but typically full-rank and highly variable.Source: §3.2 · p. 6
• A de-shrunken low-rank-factor estimator is nearly equivalent to the matrix de-biased estimator, providing an alternative representation of the correction.The factor construction de-shrinks the spectrum of the current factors.Source: §3.2 · pp. 6–7

3.3 Main results: distributional guarantees

• The paper targets distributional characterizations for both observed or missing matrix entries and low-rank factors, with the latter considered up to global rotational ambiguity.Theorem 1 is introduced as a distributional guarantee for low-rank factors under sample-size and noise conditions.Source: §3.3 · p. 7

Then one has the following decomposition

• The entrywise Gaussian approximation yields nearly accurate confidence intervals, supported by near-independence of the relevant factor-error vectors.Theorem 2 gives the distributional guarantee for matrix entries, and Corollary 1 supplies nearly accurate two-sided (1 − α) intervals under its conditions.Source: Then one has the following decomposition · pp. 8–9
• The de-shrunken factor errors decompose into Gaussian components plus residuals that are smaller when sampling is sufficient and noise is small.The typical Gaussian row size is on the order of σ√r/(pσmax); under condition (3.13), the residual row is smaller with high probability.Source: Then one has the following decomposition · p. 8
• In the symmetric case, the relevant factor-error vectors are identical rather than independent, changing the diagonal variance formula while leaving off-diagonal variances unchanged.Source: Then one has the following decomposition · p. 9
• For r, μ, κ = O(1), the conditions match minimal sample complexity up to logarithmic factors; Gaussian approximation can fail at zero rows, and small unknown row norms hinder efficient inference.The relevant row norms cannot generally be determined from the observed data.Source: Then one has the following decomposition · p. 10

3.4 Lower bounds and optimality for inference

• With oracle knowledge of the opposite factor, the de-shrunken factor estimates attain the conditional Cramér–Rao covariance bound with high probability.The oracle least-squares estimator has minimum covariance among unbiased estimators for a factor row, and the de-shrunken factor covariance matches it arbitrarily closely.Source: §3.4 · p. 10
• The de-biased matrix estimator’s variance is arbitrarily close to an oracle-aided Cramér–Rao lower bound, making its uncertainty statistically minimal in this sense.The oracle has access to factor side information; the de-biased estimator does not.Source: §3.4 · p. 11

3.5 Back to estimation: the de-biased estimator is optimal

• The de-biased estimator has a sharp error characterization and achieves optimal estimation efficiency in both rate and pre-constant, matching an oracle lower bound.The paper identifies this as the first polynomial-time algorithmic theory matching the statistical limit in the pre-constant.Source: §3.5 · pp. 11–12

3.6 Numerical experiments

• Synthetic experiments show low-rank confidence-interval coverage close to nominal and Gaussian Q-Q behavior for both factor and matrix-entry statistics.The reported factor-coverage results use 200 Monte Carlo simulations; the entry-statistic plots likewise show reasonable agreement with a standard normal distribution.Source: Table 2 · p. 12, Figure 1 · p. 12, §3.6 · pp. 13–14
• Across noise levels, M d had uniformly smaller Frobenius- and ℓ∞-norm errors than Zcvx and was closer to the oracle lower bound.The comparison averaged 20 Monte Carlo simulations with r = 5 and p = 0.2; the authors recommend M d even for estimation.Source: §3.6 · p. 14
• On daily temperatures from 1,400 stations over 365 days, coverage was reasonably close to nominal 95%, intervals were short, and M d had lower error than Zcvx.Results were averaged over 20 independent experiments; the authors suggest approximate low rank and potentially dependent noise may explain coverage discrepancies.Source: §3.6 · p. 14, Table 4 · p. 14

3.7 A bit of intuition

• For rank-1 positive-semidefinite matrices with λ = 0, the intuition is that a quadratic error term vanishes and a weakly aligned estimation error makes another term negligible, leaving an approximately Gaussian component.This reasoning assumes a reliable estimate close to x⋆ and, for the Gaussian approximation, weak dependence between E and the estimate; the paper says the arguments are made rigorous in the proof.Source: §3.7 · p. 15
• With missing data, the intuition relies on approximating PΩ and the estimate as statistically independent; for λ > 0, it similarly applies after de-shrinking the estimate.The authors state that these hand-waving arguments can be made rigorous in the proof.Source: §3.7 · p. 15

3.8 Inference based on spectral estimates?

• Spectral estimates are affected by both Gaussian noise and random subsampling, whose error persists even without noise and may make spectral-based uncertainty quantification less desirable.The discussion uses the leading eigenvector in a symmetric rank-1 example and identifies spectral initialization with methods including [CW15] [CCF18] [MWCC17].Source: §3.8 · pp. 15–16

Matrix completion

• Convex relaxation and nonconvex optimization are the two widely used paradigms for low-rank matrix completion.The literature includes nuclear-norm methods and gradient-based factorization algorithms.Source: §4 · p. 16

Convex relaxation

• Convex estimation guarantees improved, but often retained suboptimal error bounds or hidden, potentially large pre-constants [CCF+19].The cited work reports near-optimal guarantees across several error norms, while noting that their pre-constants limit inferential usefulness.Source: §4 · pp. 16–17

Nonconvex optimization

• Nonconvex methods can attain near-optimal accuracy and linear-time convergence, yet many guarantees require sample complexity of at least nr^2 [CW15] [MWCC17] [CCF+19].The passage contrasts this rank dependence with convex relaxation.Source: §4 · p. 17

Statistical inference

• Prior inference methods faced constraints including over-covering confidence regions, sample splitting or restrictive designs, sample sizes above n^2, or special Bayesian priors [CEGN15] [Xia18] [MX17].The cited trace-regression result requires a restricted-isometry sampling mechanism that does not hold for matrix completion.Source: §4 · p. 17

De-biasing approaches

• The paper presents its matrix-completion de-biasing as requiring no sample splitting and achieving statistical efficiency including the pre-constant, unlike typical sparse-regression de-biasing.The estimator construction is described as analogous to Lasso de-biasing.Source: §4 · pp. 17–18

5 Architecture of the proof

• The proof focuses on Theorems 5 and 6, which subsume the earlier results for low-rank factors and matrix entries, respectively.The section inserts a 1/p scaling into the nonconvex loss and defines sampling indicators as Bernoulli variables with mean p.Source: §5 · p. 18

5.1 Near equivalence between convex and nonconvex estimators

• Convex and nonconvex estimates are close, and their de-biased versions inherit that proximity, allowing the proof to focus on either estimator [CCF+19].In Figure 4, the estimator differences and factor distance are reported as significantly smaller than the estimation errors.Source: §5.1 · p. 19, Figure 4 · p. 20

5.2 A precise characterization of the de-shrunken low-rank factors

• The de-shrunken factor decomposition identifies a Gaussian-noise term as the main uncertainty source and terms that are small with frequent observations near a stationary point.The second term is close to the true factor, up to rotation, when the other de-shrunken factor is accurate; a sampling correction vanishes at p = 1.Source: §5.2 · pp. 20–21

5.3 Taking global rotation into account

• After aligning factors by a best-fitting global rotation, the proof reduces to bounding a residual and approximating the principal noise term by a Gaussian matrix.The argument treats the other factor by symmetry.Source: §5.3 · p. 21

5.4 Key lemmas for establishing Theorem 5

• Five lemmas establish Theorem 5 by controlling remainder terms and showing that the principal noise-driven factor term is close to a zero-mean Gaussian matrix with desired covariance.A leave-one-out technique is used to decouple dependence when bounding a term involving sampled noise.Source: §5.4 · pp. 21–22

5.5 From low-rank factors to matrix entries (Proof of Theorem 6)

• For matrix entries, the proof characterizes a component as approximately Gaussian and the residual as small; the two lemmas together establish Theorem 6.The section derives the entrywise result from the factor decompositions.Source: §5.5 · p. 23

6 Discussion

• The sample complexity scales sub-optimally with rank r and condition number κ, unlike the noise-free O(nr log^2 n) requirement, which is independent of κ and matches the information limit up to a log factor.The discussion calls for more refined analysis to improve this dependence.Source: §6 · p. 24
• For moderately large entries, the paper gives valid confidence intervals; when a factor row norm vanishes, the estimation error is better approximated by an inner product of independent Gaussian vectors.How to determine whether the row norm is too small remains unresolved.Source: §6 · p. 24
• The theory requires moderate-to-high SNR, with σ_min^2/σ^2 exceeding order n/p; whether the convex–nonconvex connection holds at low SNR is unclear.Inference in the low-SNR regime is left as future work.Source: §6 · p. 24
• The theory assumes an exactly low-rank matrix and uniform random sampling, while the investigation covers only a natural random model.Extending inference to approximately low-rank matrices and more general sampling patterns remains open.Source: §6 · p. 24
• Robust PCA, sparse PCA, and 1-bit matrix completion require non-trivial extensions of the convex–nonconvex optimization link for valid uncertainty assessment.The paper identifies these as important matrix-completion extensions.Source: §6 · p. 24
• A unified inferential framework for losses beyond penalized squared loss remains an open direction.Examples include penalized Poisson log-likelihood for Poisson noise and non-smooth loss to improve convergence.Source: §6 · p. 24

A.1 Algorithmic details of nonconvex optimization

• The nonconvex algorithm uses the true factors or spectral initialization; the true-factor start is not implementable, but the same stated guarantees extend to spectral initialization.Gradient descent runs until the gradient is exceedingly small.Source: §A.1 · p. 25

A.2 Properties of approximate nonconvex solutions

• The nonconvex solution is an approximate stationary point, is nearly balanced, and is close to the convex solution.The accompanying claims hold on a high-probability event.Source: §A.2 · p. 26
• The nonconvex solution F obeys lower and upper singular-value and norm bounds that also hold for its de-shrunken and leave-one-out variants.The passage gives σ_r(F) ≥ 0.5√σ_min and upper bounds on operator, Frobenius, and row norms.Source: §A.2 · p. 28

B Summary of the proposed estimators

• The estimator summary defines the nonconvex matrix estimate as X_ncvxY_ncvx^T and the convex factor estimate as a balanced rank-r factorization of the convex solution’s best rank-r approximation.The de-biased matrix and de-shrunken factor estimators are then summarized.Source: B Summary of the proposed estimators · p. 28

C Proof of Lemma 3

• The analysis defines the tangent space at the nonconvex estimate and uses its orthogonal projection and complementary projection.The complementary projection is P_T⊥ = I − P_T.Source: C Proof of Lemma 3 · p. 28

C.1 Proof of the inequality (5.4a)

• The proof establishes the advertised inequality (5.4a) by bounding the de-biased convex and nonconvex estimates and the nonconvex factor product near U(Σ + (λ/p)I_r)V⊤.The argument uses perturbation bounds and gives the final step under n p ≫ κ^3, with λ ≲ σ√(n p).Source: §C.1 · pp. 28–30

C.2 Proof of the inequality (5.4b)

• The analysis treats the convex balanced factors as a perturbation of (UΣ^1/2, VΣ^1/2), then uses convex/nonconvex estimator proximity to transfer the bound to de-biased factors.Source: §C.2 · p. 33

C.3 Proof of the inequality (5.5)

• The proof of inequality (5.5) reduces the claim to a bound for the nonconvex estimator and factor product, using the C.1 result and the stated n ≫ κ assumption.The convex-estimator claim is treated similarly.Source: §C.3 · p. 33

D.1 Proof of Lemma 4

• The proof of Lemma 4 rearranges the gradient decomposition and uses the de-shrunken-factor identities to derive decomposition (5.8a).The argument focuses on X_d; the Y_d factor is handled similarly.Source: §D.1 · pp. 33–34

D.2 Proof of Lemma 5

• The proof of Lemma 5 controls rowwise error terms separately, using conditional independence and concentration bounds together with bounds on auxiliary singular values.The argument conditions on the perturbation and sampling indicators, then takes a maximum over rows to bound Φ_1.Source: §D.2 · pp. 35–36

D.3 Proof of Lemma 6

• The proof of Lemma 6 combines incoherence, the Y_d decomposition, and bounds on four terms to obtain the desired maximum-row bound.It also invokes an identity stated as Claim 4.Source: §D.3 · pp. 37–41
• The proof decomposes the expression using X⋆⊤X⋆ = Y⋆⊤Y⋆, invokes [MWCC17, Lemma 35] to establish symmetry under the best rotation Hd, and combines (D.23) and (D.24) to complete Claim 4.The passage identifies Hd as the best rotation aligning (Xd, Yd) and (X⋆, Y⋆).Source: §D.3 · p. 41

D.4 Proof of Lemma 7

• Conditional on (X(j), Y(j)), the right-hand side is a sum of independent random vectors; Bernstein’s inequality is invoked, with proviso np ≫ μ log n, and the conclusion holds with probability exceeding 1 − O(n^-10).Source: §D.4 · pp. 42–43

D.5 Proof of Lemma 8

• The Lemma 8 proof combines intermediate bounds with the triangle inequality, under the proviso n^2 ≫ κ^3μr.The passage identifies this as the condition for the advertised result.Source: §D.5 · p. 45

D.6 Proof of Lemma 9

• In the Lemma 9 proof, each row of Z_X follows a Gaussian distribution, and the event complement has probability O(n^-10) when np ≳ μr log n.The argument uses matrix Bernstein’s inequality.Source: §D.6 · pp. 46–47

E.1 Proof of Lemma 10

• The Lemma 10 proof bounds two terms separately, using the Cauchy–Schwarz inequality and an incoherence assumption before combining the bounds.The supplied passage does not state the resulting bound.Source: §E.1 · p. 48

E.2 Proof of Lemma 11

• The two terms share randomness only through δij and Eij, a weak dependency that the proof decouples.Their other underlying sampling and noise variables are separate.Source: §E.2 · p. 48
• Under np ≫ κ^2µr^2 log^2 n, Claim 5 gives a decomposition used to establish near independence.The proof states that the desired result follows from Claim 5.Source: §E.2 · pp. 48–49

F Proof of Corollary 1

• Under conditions (3.18), Corollary 2 states the resulting probability bound for any t.The proof says this establishes Corollary 2; the supplied passage does not include the bound's formula.Source: F Proof of Corollary 1 · pp. 50–51
• With probability exceeding 1 − O(n^-10), Claim 6 bounds ∆V.The proof identifies this as the remaining high-probability bound needed after controlling ∆ij.Source: F Proof of Corollary 1 · p. 51
• The proof combines bounds on the matrix estimate and its factor terms to control ∆V with high probability.It treats the X and Y factors similarly before combining their bounds.Source: F Proof of Corollary 1 · pp. 52–53

G Proof of Theorem 3

• F is the dominant term and concentrates sharply around its mean, while rem is much smaller with high probability.The proof identifies F/σ^2 as chi-squared with nr degrees of freedom and invokes concentration bounds.Source: G Proof of Theorem 3 · p. 53
• max{∥∆X∥F, ∥∆Y∥F} ≲ √n max{∥∆X∥2,∞, ∥∆Y∥2,∞} ≲ σ√pσmin.This factor-error bound follows from the decompositions in Theorem 5.Source: G Proof of Theorem 3 · pp. 53, 55
• The proof’s remainder control is stated under the proviso np ≳ κ^3µr log^3 n.The passage ties this sampling condition to a high-probability bound.Source: G Proof of Theorem 3 · p. 55

H.1 Proof of Lemma 1

• With probability at least 1 − O(n^-10), the Lemma 1 bound holds when np ≥ C0ε^-2κ^4µr log n.The proof derives the probability statement using a matrix Bernstein inequality.Source: §H.1 · p. 56

H.2 Proof of Lemma 2

• The Lemma 2 inequality follows when np ≥ 4C^2ε^-2κ^4µr log n.The proof compares the bounds in (H.2) and (H.3).Source: §H.2 · p. 57

I.1 Proof of the inequalities (A.13)

• The proof of (A.13) bounds estimator differences using triangle inequalities and perturbation results.For the de-shrunken estimator, it combines its definition with bounds referenced in (A.11) and (C.16).Source: §I.1 · p. 59

I.2 Proof of the inequalities (A.16)

• The proof of (A.16) controls θ by applying bounds for both (X, Y) and (X(j), Y(j)).It then uses a matrix-square-root perturbation bound.Source: §I.2 · p. 60

J Technical lemmas

• Lemma 14 bounds the perturbation of rank-r SVD components when ∥E∥ ≤ ∥M∥ and σr(M) > σr+1(M + E).The appendix also states perturbation results for pseudo-inverses and the Sylvester equation.Source: J Technical lemmas · pp. 61–62