Near-Optimal Nonconvex Matrix Completion

Jian-Feng Cai; Xiliang Lu; Juntao You

Source-linked AI summary

Near-Optimal Nonconvex Matrix Completion

Jian-Feng Cai, Xiliang Lu, Juntao You

arXiv:2609.17048v1Sep 15, 2026math.NAcs.LG

TL;DR

Efficient nonconvex matrix completion methods have generally lacked the near-optimal rank dependence achieved by convex methods. The paper analyzes RGD and RGN with multiscale residual initialization, obtaining exact recovery from near-optimal sample complexities with linear and eventual Q-quadratic convergence, respectively.

Problem
Earlier efficient nonconvex matrix-completion guarantees generally required higher polynomial dependence on rank r, despite convex methods achieving near-optimal dependence on μ, n, and r up to logarithmic factors.
Method
The paper analyzes RGD and RGN equipped with multiscale residual initialization while simultaneously controlling spectral, row, column, and entrywise errors.
Results
O(μnr log n log(nκ)) and O(μnr log n log(2μrκ)) observations suffice for high-probability exact recovery by RGD and RGN, respectively, with RGD linear and RGN eventually Q-quadratic.
Takeaways & Limitations
RGD and RGN achieve global recovery guarantees with sample requirements linear in n and r up to logarithmic factors under standard incoherence.
Takeaways & Limitations
The paper leaves reuse of the entire observation set at every initialization step and RGN with an inexact tangent solve and computable stopping criterion for future study.

Abstract

from arXiv · show

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an $n\times n$ matrix of rank $r$ with incoherence parameter $μ$ and condition number $κ$, the two methods achieve exact recovery with high probability from $O(μnr\log n\log(nκ))$ and $O(μnr\log n\log(2μrκ))$ observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

1 Introduction

Matrix completion has near-optimal convex sample complexity, but efficient nonconvex methods have typically required higher-rank dependence. This paper addresses that gap for RGD and RGN using multiscale initialization and simultaneous error control.

Motivation: Prior convex guarantees attain optimal dependence on μ, n, and r up to logarithmic factors, whereas earlier nonconvex guarantees generally had higher polynomial dependence on r.This motivates whether efficient nonconvex methods can achieve sample complexity linear in n and r up to logarithmic factors.
Main contributions: O(μnr log n log(nκ)) and O(μnr log n log(2μrκ)) observations suffice for exact recovery by RGD and RGN, respectively, with high probability.Both bounds are linear in n and r up to logarithmic factors; RGD converges linearly, while RGN eventually converges Q-quadratically.
Proof strategy: The analysis tracks spectral, row, column, and entrywise errors simultaneously to control the loss incurred when converting spectral error into Frobenius error.For RGD, multiscale initialization affects only the number of initialization steps before Frobenius control; RGN continues sharp-norm control through initial iterations.
Main contributions: Multiscale residual initialization avoids the additional κ^2 sampling factor of ordinary spectral initialization and avoids an additional polynomial dependence on r.Successive residual reconstructions reduce sharp-norm error at sampling level p ≳ μr log n/n while controlling spectral, row, column, and entrywise errors.
Convergence analysis: RGD reaches a Frobenius neighborhood where a uniform tangent-space sampling estimate yields linear convergence.After initialization, relative Frobenius accuracy ε is reached within O(log(1/ε)) RGD iterations.
Convergence analysis: RGN uses finite leave-one-out analysis to propagate sharp-norm control before a local deterministic argument yields quadratic convergence.Relative Frobenius accuracy ε is attained within O(log log(1/ε)) subsequent RGN iterations, with cost depending additionally on CG iteration counts.

2 Problem Formulation and Riemannian Algorithms

The paper formulates matrix completion under Bernoulli observations and optimizes over the fixed-rank matrix manifold. It then combines RGD, RGN, and multiscale spectral residual initialization, with observation-set decompositions used in the analysis and reuse in implementation.

2.1 Problem setup: Matrix completion recovers an unknown rank-r matrix X⋆ from the sampled entries PΩ(X⋆), assuming Bernoulli observations and standard incoherence.The incoherence condition prevents the singular spaces from concentrating on only a few canonical-basis entries.
2.2 Riemannian gradient descent: RGD moves along the negative tangent gradient on the fixed-rank manifold and retracts the update back onto that manifold.The tangent gradient and exact line-search stepsize cost O(|Ω|r + nr^2) per iteration, while orthographic retraction uses low-rank factorizations.
2.3 Riemannian Gauss–Newton: RGN linearizes the sampled residual, solves the resulting tangent normal equation with conjugate gradients, and retracts the tangent search direction.The normal equations can be solved matrix-free; each iteration costs O(|bΩ|r + nr^2) in operator applications plus retraction cost, with CG counts determining total work.
2.3 Riemannian Gauss–Newton: Regularized RGN adds λkξ to the normal equation, making it positive definite on the tangent space at every nonterminal iteration.The regularization does not change the stated per-operator computational order.
2.4 Multiscale initialization: Multiscale initialization repeatedly reconstructs spectral components of the observed residual, using hard spectral thresholding and randomized subspace iteration.Only singular components above the current error scale need accurate representation, and no gap between adjacent singular values is assumed.
2.4 Multiscale initialization: The initialization stops after a residual increase or a maximum number of reconstructions, with rank-r outputs selected through a residual test.Each reconstruction uses matrix–factor products and a compressed singular value decomposition, with cost proportional to (mr + nr^2) log n.
2.4 Multiscale initialization: The analysis decomposes observations into independent Bernoulli subsets for initialization and reserves an additional subset for RGN iterations.In numerical implementation, however, the same observation set is reused throughout the algorithms.

3 Main Results

The main results establish high-probability global recovery for RGD and RGN using multiscale residual initialization, with linear and eventual quadratic convergence respectively. They also show why ordinary spectral initialization can require an additional κ² sampling factor.

Global convergence of RGD: O(µnr log n log(nκ)) observations suffice for RGD exact recovery with high probability, followed by linear convergence and O(log(1/ε)) iterations for relative Frobenius accuracy ε.The initialization and all subsequent iterates are well defined under the theorem’s conditions.
Global convergence of RGN: O(µnr log n log(2µrκ)) observations suffice for RGN and its regularized variant, with high-probability recovery and eventual quadratic convergence.After finitely many iterations, relative Frobenius accuracy ε requires O(log log(1/ε)) subsequent RGN iterations, with computational cost depending on CG counts Jk.
Lower bound for ordinary spectral initialization: Ordinary spectral initialization may require sampling probability of order µκ²r/n to reach the sharp-norm neighborhood needed for local convergence.The lower bound holds over an explicit family of incoherent matrices, motivating the multiscale construction.
Initialization: The multiscale residual initialization replaces ordinary spectral estimation to reach the local regions required by RGD and RGN without adding polynomial dependence on r.Successive residual reconstructions reduce sharp-norm error geometrically while controlling spectral, row, column, and entrywise errors.

4 Proof Framework: Local Convergence and Initialization

The proof framework combines multiscale initialization with local convergence analyses that use different error controls for RGD and RGN. RGD reaches a Frobenius neighborhood for linear convergence, while RGN preserves sharp-norm control before entering a regime of deterministic quadratic convergence.

Local convergence: RGD is controlled in a Frobenius neighborhood, whereas RGN requires stronger sharp-norm control before its local convergence analysis applies.The two methods therefore use different local hypotheses and error measures.
Local convergence: RGD's tangent sampling isometry controls first-order error terms, while RGN's sampled correction is driven by a quadratic normal component.These mechanisms explain the linear versus eventual quadratic local behavior.
Local convergence: RGD's local theorem holds uniformly over a Frobenius neighborhood, so its initial point need not be independent of the observation set.RGN instead requires the initial point to be independent of its reserved observation set for the leave-one-out argument.
Multiscale initialization: The initialization produces a rank-r sequence with sharp-norm error decreasing geometrically across scales and reaches the hypotheses required by both local convergence theorems.The two choices of the number of scales require at most O(log(nκ)) and O(log(2µrκ)) reconstructions, respectively.
Multiscale initialization: A residual test certifies that when the initialization algorithm returns, its output satisfies the local condition needed for subsequent convergence.The proposition rules out returning after a residual increase before the corresponding local convergence condition is reached.

5 Local Convergence of RGD

The local RGD analysis combines geometric bounds, tangent-space sampling isometries, and retraction control to establish an invariant neighborhood around X⋆. Within this neighborhood, the iterates remain well defined and reach exact recovery.

Proof structure: The local argument begins with singular-subspace and normal-error bounds, then applies geometric estimates and sampling control to prove the convergence theorem.These ingredients also ensure the retraction and line-search quantities remain well defined.
Geometric estimates: The analysis controls tangent and normal error components together with row, column, and entrywise norms under a sharp-norm error bound.The graph-factor representation and normal-component estimates also control incoherence-related quantities.
Update analysis: The population tangent correction recovers X⋆ exactly, while perturbation and retraction estimates control the sampled update.The proof uses graph retraction identities and Frobenius remainder bounds to keep the iterates within the local region.
Sampling control: Sampling isometries hold uniformly over a Frobenius neighborhood of X⋆, allowing the same bounds to apply when the iterate depends on the sampled entries.The transfer from the true tangent space to nearby tangent spaces is deterministic once the sampling event holds.
Local convergence: RGD preserves a Frobenius neighborhood of X⋆ and every terminal iterate in that neighborhood equals X⋆.The proof establishes invariance under the update and shows that a zero tangent correction implies exact recovery.

6 Multiscale Initialization and Global Convergence of RGD

RGD uses multiscale residual spectral reconstruction to enter the local convergence region from incomplete observations. The resulting global argument combines reconstruction guarantees, residual stopping, and local invariance.

Initialization: The initialization contracts the sharp-norm error across scales while retaining rank at most r and eventually attaining rank r.The reconstruction uses observed residual corrections and truncated randomized subspace iterations.
Initialization: The multiscale reconstruction produces a rank-r candidate satisfying the local entrance conditions needed for RGD convergence.Approximate singular factors suffice, so the randomized subspace iteration can stop after a prescribed number of steps.
Initialization: The reconstruction analysis controls sampling perturbations and approximate singular factors without requiring a spectral gap between adjacent singular values.Only singular components above the current error scale must be accurately represented.
Global convergence: The residual stopping rule returns an iterate of rank r that satisfies both local entrance conditions for the subsequent RGD analysis.The proof handles both cases where the residual test stops early and where the full reconstruction sequence is completed.
Global convergence: The number of reconstruction stages is logarithmic in nκ, and a union bound gives the stated high-probability global convergence guarantee.The proof uses K + 1 ≤ 12 log(nκ) for RGD and combines the initialization event with the local theorem.

7 Convergence of RGN

RGN is analyzed through leave-one-out auxiliary trajectories, uniform sampling control, and local retraction estimates. Once the iterates enter a sufficiently small neighborhood, the Frobenius error obeys a Q-quadratic recurrence.

Initialization condition: The proof assumes an initial point independent of the RGN observation set and sufficiently close to X⋆ in the sharp norm.The stated initialization condition is ∥X0 − X⋆∥♯ ≤ σr(X⋆)/(1000µr).
Dependence control: Leave-one-out row and column completions restore independence between auxiliary trajectories and the Bernoulli variables used for concentration.Each completed operator replaces one row or column by its population counterpart.
Sampling control: Uniform sampling isometries and tangent-normal operator bounds hold simultaneously for the original and completed operators.These estimates support uniqueness of tangent least-squares minimizers and control the difference between sampled and population corrections.
Trajectory coupling: The stopped auxiliary processes agree with the actual algorithm through the analyzed horizon because all candidate updates are accepted.Acceptance follows from invertibility, well-defined graph retractions, and the propagated sharp-norm bounds.
Quadratic convergence: After entering the local neighborhood, RGN iterates satisfy a Q-quadratic recurrence and converge to X⋆.The induction starts at a finite index after the initial sharp-norm control and continues for every subsequent iterate.

8 Numerical Experiments

Numerical experiments compare RGD with factorized and scaled gradient methods, then measure recovery rates across ranks and observation counts. The experiments report linear-in-nr recovery transitions over the tested range.

Convergence and running time: The convergence and running-time experiment compares FGD, ScaledGD, RGD, and RGN for condition numbers κ ∈ {1, 10, 100}.All four methods use the same observations for each condition number, and Figure 2 reports error against iteration count and elapsed time.
Empirical recovery rates: The recovery-rate experiment varies r ∈ {2, 4, ..., 30} and m/n ∈ {4, 8, ..., 84}, declaring success when errk ≤ 10^-6.RGD and RGN use relative observed-residual tolerances of 10^-12 and 10^-8, respectively.
Empirical recovery rates: Recovery transitions occur as observations increase, with an approximately linear dependence on nr across the tested ranks.Figure 3 reports successful-trial fractions over 30 random trials for each rank and observation level.

9 Concluding Remarks

The paper establishes near-optimal global recovery guarantees for RGD and RGN, with linear-in-r convergence for RGD and eventual quadratic convergence for RGN. Numerical experiments examine reconstruction errors and empirical recovery transitions as observations increase.

O(µnr log n log(nκ)) and O(µnr log n log(2µrκ)) observations suffice for high-probability recovery by RGD and RGN, respectively.The requirements are linear in n and r up to logarithmic factors.
RGD converges linearly, while RGN has an initial sharp-norm phase followed by a quadratic Frobenius recurrence.Both methods use multiscale residual initialization with residual stopping.
The paper identifies inexact tangent solves and computable stopping criteria for RGN as extensions needed to relate convergence to total CG iterations.
Figure 3 measures recovery rates across rank and observation levels, using 30 trials for each tested pair.White denotes success in all trials and black denotes failure in all trials; reference lines are m = (2r + 9)n for RGN and m = (2.5r + 10)n for RGD.

A Lower bound for ordinary spectral initialization

This section constructs incoherent matrix instances showing that ordinary spectral initialization can require an additional condition-number-dependent sampling factor. The proof uses block-diagonal constructions and degree-concentration arguments to establish the lower bound.

The lower-bound proof constructs a block-diagonal family of incoherent matrices.
The construction chooses pairwise disjoint support sets and defines a sampled block matrix with independent Bernoulli entries.The parameters relate incoherence and condition number through µ = n/(rs) and κ^2 ≤ s.
An active row is empty with probability at least e^-2d, and the proof uses this event to obtain a failure probability for the spectral estimator.
A Chernoff-bound event controls every row and column degree of each sampled block by 16d.
The proof separates cases according to the singular values of the sampled blocks and applies best rank-r approximation properties to localize the estimator.The argument concludes with the stated theorem.

B Probabilistic Lemmas

This appendix collects concentration tools used in the sampling arguments and proves a tangent-space sampling isometry. The proof applies matrix Bernstein inequalities to independent sampled tangent components.

The appendix states rectangular and self-adjoint matrix Bernstein inequalities for independent mean-zero random matrices and operators.
The tangent-space sampling proof represents sampled basis components through projected coordinate matrices and rank-one operators.
Orthogonality and incoherence bound the summand norms, while the sampling variance is controlled through the Bernoulli observation model.
Because dim(T_X⋆) = r(2n − r) ≤ 2nr, a sampling rate p_Λ ≥ c1µr log n/n enables the Bernstein bound at threshold 1/16.
The resulting concentration estimate proves the tangent-space sampling lemma.

B.2 Proof of Lemma 6.1

This proof develops geometric and probabilistic estimates controlling tangent spaces, graph factors, retractions, and comparisons between nearby low-rank matrices. These estimates support local convergence analyses for RGD and RGN.

For nearby matrices, separately aligned Procrustes gauges and resolvent identities control factor, projector, graph-core, and retraction differences while preserving invertibility.
The proof controls singular spaces, tangent projectors, normal components, and graph factors using Weyl, incoherence, and projector estimates.The resulting bounds establish the sharp-norm control needed for local analysis.
The graph representation expresses the normal component through a vanishing Schur complement, yielding bounds on left and right graph factors.
The population tangent correction is exact for the target matrix, with tangent coordinates M = G_X − Σ, B = L_X, and C = R_X.
A retraction estimate bounds the error by 2∥X − X⋆∥_F∥η∥_F + ∥η∥_F^2, providing the quadratic remainder used in local convergence.

C.4.2 Proof of Lemma 7.6

The proof establishes sampling, subspace, and reconstruction estimates that support RGN control without requiring singular-value separation. It then connects these estimates to finite-accuracy and computational guarantees for RGD and RGN.

Reconstruction estimates: The reconstruction estimates control the reconstructed matrix without requiring separation between adjacent singular values, and the finite computation attains the required accuracy.The proof uses dilation, retained singular factors, and discarded components to bound approximation errors and establish well-defined QR steps almost surely.
Sampling estimates: The sampling analysis proves simultaneous isometries for actual and completed operators when q ≥ c1μr log n/n, using Bernstein bounds and a union bound.With c1 = 215, the Bernstein exponent at threshold 1/16 is at least 24 log n.
Sampling estimates: Weighted product estimates transfer sampling control to nearby tangent spaces, while conditional row and column bounds hold jointly with probability at least 1 − (n + r + 2)n^-24.The argument combines bounds on Euclidean and entrywise norms through Bernstein events.