PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-Optimal Nonconvex Matrix Completion

Jian-Feng Cai, Xiliang Lu, Juntao You

arXiv:2609.17048v1math.NAcs.LG

TL;DR

Matrix completion seeks to recover a low-rank matrix from sampled entries, but efficient nonconvex methods lacked near-linear-in-rank global guarantees. This paper analyzes RGD and RGN with multiscale residual initialization, establishing high-probability exact recovery at near-optimal sample complexity, with linear and eventually Q-quadratic convergence, respectively.

  • Problem

    Efficient nonconvex matrix-completion methods generally lacked global recovery guarantees with sample complexity linear in n and r up to logarithmic factors.

    Source: §1 · p. 1

  • Method

    The paper analyzes Riemannian gradient descent and Riemannian Gauss–Newton with multiscale residual initialization under standard incoherence.

    Source: §1 · pp. 2–3

  • 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.

    Source: §9 · p. 29

  • Takeaways & Limitations

    The results establish sample requirements linear in n and r up to logarithmic factors, with RGD converging linearly and RGN eventually converging Q-quadratically.

    Source: §9 · p. 29

    The same guarantees remain to be established when initialization reuses the entire observation set or RGN uses an inexact tangent solve and computable stopping criterion.

    Source: §9 · p. 30

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

The paper develops efficient nonconvex matrix-completion methods with near-optimal sample complexity by combining multiscale residual initialization with simultaneous error and incoherence control. RGD converges linearly, while RGN eventually converges Q-quadratically.

Contributions

  • Near-optimal global recovery guarantees for RGD and RGN close the rank-dependence gap faced by existing efficient nonconvex methods.The methods achieve sample complexity linear in n and r up to logarithmic factors under standard incoherence.Source: §1 · pp. 1–2

Related work

  • Prior matrix-completion guarantees for efficient nonconvex methods generally retain higher polynomial dependence on r, unlike the optimal O(nr) scaling known for Gaussian matrix sensing.Matrix completion is harder because its sampling operator lacks uniform restricted isometry over low-rank matrices and iterates must remain incoherent.Source: §1 · pp. 1–2

Proof strategy

  • Multiscale residual initialization controls spectral, row, column, and entrywise errors simultaneously, avoiding extra polynomial dependence on r.It reaches the required local regions without the additional rank loss associated with spectral-to-Frobenius conversion.Source: §1 · p. 2

Initialization

  • Residual reconstructions reduce sharp-norm error at sampling level p ≳ μr log n/n, avoiding the ordinary spectral estimator’s additional κ^2 factor.The paper also establishes that the μκ^2r/n sampling scale of ordinary spectral initialization is necessary for an explicit incoherent matrix family.Source: §1 · pp. 2–3

Local convergence

  • RGD enters a Frobenius neighborhood and then converges linearly through a uniform tangent-space sampling estimate.For RGN, leave-one-out analysis maintains sharp-norm control initially, after which a local deterministic argument yields quadratic convergence.Source: §1 · pp. 2–3

2 Problem Formulation and Riemannian Algorithms

The paper formulates matrix completion as recovering an incoherent rank-r matrix from Bernoulli-sampled entries and develops RGD, RGN, and regularized RGN on the fixed-rank manifold. A multiscale residual spectral initialization supplies the starting point required by the local algorithms.

2.1 Problem setup

  • The problem is to recover an unknown rank-r matrix X⋆ from entries observed independently under a Bernoulli sampling model, using a nonconvex rank-r manifold formulation.The observation set is Ω and PΩ retains observed entries; incoherence prevents the singular spaces from concentrating on a few coordinates.Source: §2.1 · p. 4

2.2 Riemannian gradient descent

  • RGD projects the sampled gradient onto the tangent space, takes an exact line-search step, and uses orthographic retraction to return to the fixed-rank manifold.Each RGD iteration costs O(|Ω|r + nr^2) operations when implemented with sparse matrix–factor products and low-rank factorizations.Source: §2.2 · pp. 4–5

2.3 Riemannian Gauss–Newton

  • RGN linearizes the sampled residual in the tangent space, solves the resulting normal equation by conjugate gradients, and retracts the search direction onto the manifold.Matrix-free normal-operator applications make the kth iteration cost O(J_k(|bΩ|r + nr^2)) operations up to the stated retraction terms.Source: §2.3 · pp. 5–6
  • Regularized RGN adds λ_kξ to the normal equation, ensuring positive definiteness on the tangent space at every nonterminal iteration while retaining the same computational order.The regularized direction is computed with the same conjugate-gradient and termination conventions as RGN.Source: §2.3 · p. 6

2.4 Multiscale initialization

  • Multiscale initialization repeatedly corrects the current approximation using observed residuals and decreasing spectral thresholds, avoiding the stronger sampling requirement of standard spectral initialization.The construction begins at Z_0 = 0, uses τ_ℓ = 4^-ℓτ_0, and applies hard spectral truncation at each scale.Source: §2.4 · p. 7
  • The initialization stops when the observed residual first increases or after K reconstructions, and its output seeds the subsequent Riemannian iterations.The analysis partitions observations into independent Bernoulli subsets, reserving a final subset bΩ for RGN; implementations instead reuse Ω throughout.Source: §2.4 · pp. 7–8

3 Main Results

The paper establishes global recovery guarantees for RGD and RGN using multiscale residual initialization, with linear convergence for RGD and eventual quadratic convergence for RGN. It also proves that ordinary spectral initialization can require an additional κ^2 sampling penalty.

3 Main Results

  • The main results combine multiscale residual initialization with global convergence analyses for RGD and RGN under the paper’s incoherence and Bernoulli sampling assumptions.The section states global recovery guarantees for both methods before establishing the lower bound for ordinary spectral initialization.Source: §3 · p. 8, §3.1 · p. 8, §3.2 · p. 9

3.1 Global convergence of RGD

  • RGD exactly recovers the matrix with high probability from O(μnr log n log(nκ)) observations and reaches relative Frobenius accuracy ε in O(log(1/ε)) iterations.The initialization and every subsequent iterate are well defined with probability at least 1 − n^-10.Source: §3.1 · pp. 8–9

3.2 Global convergence of RGN

  • RGN and its regularized variant recover exactly with high probability from O(μnr log n log(2μrκ)) observations and achieve quadratic convergence after finitely many iterations.Relative Frobenius accuracy ε is reached in O(log log(1/ε)) subsequent RGN iterations; the initialization and iterates are well defined with probability at least 1 − n^-10.Source: §3.2 · p. 9

3.3 Lower bound for ordinary spectral initialization

  • Ordinary spectral initialization may require sampling probability of order μκ^2r/n to enter the sharp-norm neighborhood needed for local convergence.The lower bound holds over an explicit family of incoherent rank-r matrices, while multiscale initialization applies reconstruction to residuals whose sharp error decreases geometrically.Source: §3.3 · p. 10

4 Proof Framework: Local Convergence and Initialization

The proof framework combines local convergence of fixed-sample RGD and RGN iterations with multiscale initialization that reaches their respective hypotheses.

4.1 Local convergence

  • RGD uses Frobenius-neighborhood control with first-order tangent errors, whereas RGN uses sharp-norm control driven by a quadratic normal component.Finite leave-one-out control brings iterates into a neighborhood where RGN’s quadratic convergence follows deterministically.Source: §4.1 · pp. 10–11, Figure 1 · p. 11
  • RGD’s uniform high-probability event permits an initialization dependent on the observations, while RGN requires independence for its leave-one-out argument.After this independence condition controls the initial RGN iterates, the quadratic Frobenius recursion applies.Source: §4.1 · p. 11

4.2 Multiscale initialization

  • With q ≥ C5μr log n/n, Algorithm 4 produces rank-r iterates whose sharp-norm error contracts geometrically as 4^-ℓτ0 with high probability.The construction controls sampling perturbations and reaches the local hypotheses without requiring a gap between adjacent singular values.Source: §4.2 · p. 12
  • The residual test is justified so that a return occurs only after the corresponding local convergence condition is satisfied.The two choices of K require at most O(log(nκ)) and O(log(2μrκ)) reconstructions for RGD and RGN, respectively.Source: §4.2 · p. 13

5 Local Convergence of RGD

Section 5 develops deterministic geometric and sampling estimates that establish local convergence of RGD. Uniform sampling control over a neighborhood makes the RGD update invariant and guarantees well-defined iterates that converge to X⋆.

5.1 Deterministic geometry

  • Under e♯ ≤ σr(X⋆)/8, singular-space geometry controls incoherence, projector variation, and tangent/normal error components.The error decomposition uses GX for the representation in current singular bases and LX, RX for components outside those subspaces.Source: §5.1 · p. 13

The singular-space projectors satisfy the rowwise bounds

  • Local retraction estimates bound perturbations and nonlinear remainders, supporting both RGD convergence and eventual quadratic convergence of RGN.The analysis includes a population tangent correction that exactly recovers X⋆ and uses graph-factor representations under local error bounds.Source: The singular-space projectors satisfy… · p. 14

5.2 Sampling isometry and uniform transfer

  • With pΛ ≥ c1μr log n/n, tangent-space sampling isometry holds with probability at least 1 − n^-10/48 and transfers uniformly to nearby tangent spaces.The transfer is simultaneous throughout the Frobenius neighborhood, so X may depend on Λ.Source: §5.2 · pp. 15–16

5 Local Convergence of RGD

  • The proof combines uniform sampling estimates with tangent/normal error decomposition to establish the RGD contraction inequalities and admissible line-search steps.The resulting bounds keep the iterates inside the local neighborhood throughout the induction.Source: §5.3 · pp. 16–17

5.3 Proof of Theorem 4.1

  • The RGD update preserves the stated neighborhood, remains well defined, and reaches X⋆ whenever initialized within the theorem’s local basin.Every terminal iterate in the neighborhood equals X⋆, while induction preserves the hypotheses and positivity of nonterminal line-search denominators.Source: §5.3 · p. 17

6 Multiscale Initialization and Global Convergence of RGD

This section establishes that multiscale initialization produces controlled rank-r iterates and satisfies the local conditions needed for global RGD convergence. The proof combines sharp spectral reconstruction, residual stopping, and high-probability induction across scales.

6.1 Sharp spectral reconstruction

  • The reconstruction operator Tτ has rank at most r and satisfies the required approximate singular-factor conditions whenever σr+1(Y) ≤τ/512.Its randomized subspace iteration needs no gap between adjacent singular values, and the sharp reconstruction estimate contracts the error to at most τ/4.Source: §6.1 · p. 18

6.2 Proof of Theorem 4.3

  • Theorem 4.3 follows by applying the reconstruction lemma conditionally at each scale and combining the resulting events with a union bound.The conditional conclusion preserves rank(Tτ(Y)) ≤ r and the approximation conditions except on the stated per-scale failure event.Source: §6.2 · p. 18

6.3 Proof of Proposition 4.5

  • The proof of Proposition 4.5 controls observed residuals using independent successive observation sets and propagates rank-r reconstruction after the first rank-r iterate.Finite subspace iteration retains all r singular values, so every subsequent iterate also has rank r.Source: §6.3 · pp. 19–20
  • The residual stopping rule returns a rank-r iterate satisfying both local entrance conditions required by the RGD theorem.If the residual increases, consecutive rank-r iterates are compared; the sampling condition then yields the sharp-norm bound and q ≥ r/n.Source: §6.3 · p. 20, §6.4 · p. 21

6.4 Proof of Theorem 4.4

  • At each scale, sampling and Gaussian reconstruction estimates preserve the multiscale invariant through step K, and the terminal iterate has rank r.The induction succeeds on an event with the stated failure control, while Weyl’s inequality verifies rank(ZK)=r.Source: §6.3 · p. 19, §6.4 · p. 21

6.5 Proof of Theorem 3.1

  • Multiscale initialization reaches the local RGD neighborhood with probability at least 1−n^-10/3, after at most K+1 ≤12 log(nκ) scales.The convergence theorem applies simultaneously throughout this neighborhood, so no independence between the initialization and the full observation set is required.Source: §6.5 · p. 22

7 Convergence of RGN

This section proves RGN convergence by combining leave-one-out auxiliary sequences, simultaneous sampling controls, and sharp-norm error bounds to establish eventual Q-quadratic convergence. It then transfers the result to the initialization and regularized RGN theorems.

7.1 Dependence and the leave-one-out construction

  • Leave-one-out sequences replace one row or column with its population counterpart, restoring independence from the corresponding Bernoulli variables for the initial iterations.A stopping rule keeps each auxiliary process defined on every outcome and preserves this independence.Source: §7.1 · pp. 22–23

7.2 Simultaneous sampling events

  • Simultaneous sampling events control row and column degrees, the original operator, completed operators, and all stopped trajectories with high probability.These events provide the concentration and sampling-isometry inputs used throughout the convergence proof.Source: §7.1 · p. 22, §7.2 · pp. 23–24

7.3 Error bounds for the initial RGN iterates

  • Uniform sharp-norm bounds control sampled tangent normal operators and the differences between sampled and population tangent corrections near X⋆.Coordinatewise correction estimates are additionally used to propagate sharp-norm control through the initial RGN iterates.Source: §7.3 · pp. 24–25

Then every correction satisfies

  • Every correction obeys the required bound under q ≥ c4µr log n/n, while nearby retracted iterates remain well defined and controlled.The retraction comparison lemma transfers correction estimates into bounds on the iterates.Source: Then every correction satisfies · p. 25

7.4 Proof of Theorem 4.2

  • The proof inductively verifies invertibility, valid retractions, accepted auxiliary updates, and propagation of the sharp-norm bounds through the transition index.After that index, the Frobenius error enters the regime where the Q-quadratic recurrence applies.Source: §7.4 · pp. 26–27
  • RGN iterates eventually satisfy a Q-quadratic Frobenius recurrence and converge to X⋆, provided the sharp-norm initialization lies within σr(X⋆)/(1000µr).The proof shows all auxiliary updates are accepted before the transition index and establishes convergence thereafter.Source: §7.4 · p. 27

7.5 Proof of Theorem 3.2

  • The initialization theorem follows by combining independent multiscale initialization with Theorem 4.2, yielding the stated convergence failure-probability bound.The initializer depends only on the earlier sampling sets and independent Gaussian matrices, so it is independent of the RGN sampling set.Source: §7.5 · p. 28

7.6 Proof of Theorem 3.3

  • The regularized RGN iterates remain in an invariant neighborhood after the transition index, establishing the claimed result by induction.The argument compares ordinary and regularized normal equations and applies the correction bound within the neighborhood.Source: §7.6 · p. 28

8 Numerical Experiments

Numerical experiments compare FGD, ScaledGD, RGD, and RGN on randomly generated matrix-completion problems. They examine convergence and running time across condition numbers, and empirical recovery rates across ranks and observation counts.

Convergence and running time

  • The convergence comparison gives all four methods the same observations, while RGD and RGN share the multiscale initialization and FGD and ScaledGD share spectral initialization.For each condition number, the methods receive identical observed entries; RGN uses conjugate-gradient solves stopped at relative residual 0.05 or 200 iterations.Source: §8 · p. 29
  • Figure 2 compares convergence and elapsed time for FGD, ScaledGD, RGD, and RGN at condition numbers κ ∈ {1, 10, 100}.The experiments use n = 1000, r = 10, p = 0.2, and elapsed time includes initialization and subsequent iterations.Source: §8 · p. 29

Empirical recovery rates

  • Recovery trials use uniformly sampled entries, algorithm-specific residual tolerances, and declare success when err_k ≤ 10^-6.The relative observed-residual tolerances are 10^-12 for RGD and 10^-8 for RGN.Source: §8 · p. 29
  • Across both panels, recovery transitions from failure to successful recovery as m increases, with an approximately linear dependence on nr over the tested ranks.Recovery is declared successful when errk ≤ 10^-6, and Figure 3 reports the fraction of successful trials at each (r, m).Source: §8 · p. 29

9 Concluding Remarks

The paper establishes global recovery guarantees for RGD and RGN under standard incoherence and Bernoulli sampling, with sample requirements linear in n and r up to logarithmic factors. Both methods use multiscale residual initialization, while RGD converges linearly and RGN transitions from doubly exponential sharp-norm convergence to quadratic Frobenius convergence.

Guarantees

  • O(µnr log n log(nκ)) and O(µnr log n log(2µrκ)) observations suffice for global recovery by RGD and RGN, respectively, with high probability.The sample requirements are linear in n and r up to logarithmic factors.Source: §9 · p. 29

Convergence

  • RGD converges linearly, whereas RGN has a doubly exponential sharp-norm error bound initially and a quadratic Frobenius recurrence thereafter.The methods use multiscale residual initialization with residual stopping and distinct reconstruction-count bounds for their local conditions.Source: §9 · pp. 29–30

Method properties

  • The observation set is fixed at initialization, and the sampling requirement does not depend on the target accuracy.Both methods use multiscale residual initialization with residual stopping.Source: §9 · p. 30

Future work

  • Future work includes reusing the entire observation set at every initialization step and analyzing RGN with inexact tangent solves and computable stopping criteria.The latter would relate convergence rates to the total number of conjugate-gradient iterations.Source: §9 · p. 30

A Lower bound for ordinary spectral initialization

The lower-bound proof constructs a block-diagonal family of incoherent matrices whose sampled blocks can contain empty active rows. Degree control and singular-value arguments then show that ordinary spectral initialization cannot reliably recover the intended rank structure.

Construction

  • The proof constructs a block-diagonal family using pairwise-disjoint supports of equal size, yielding incoherent rank-r matrices.The construction sets disjoint active sets I_1,...,I_r and verifies the incoherence assumption.Source: A Lower bound for ordinary spectral… · p. 31

Sampling obstruction

  • Each active row is empty with probability π = (1 − q)^s ≥ e^−2d ≥ (rs)^−1/2, making empty rows likely across the active blocks.The argument also bounds the probability that at least one active row is empty.Source: A Lower bound for ordinary spectral… · pp. 31–32

Spectral lower bound

  • With high-degree control and singular-value case analysis, every best rank-at-most-r approximation is forced toward a single active block or incurs a large approximation error, proving the theorem.The proof controls row and column degrees by a Chernoff bound and applies the Eckart–Young–Mirsky theorem to the resulting singular values.Source: A Lower bound for ordinary spectral… · p. 32

B Probabilistic Lemmas · B.1 Proof of Lemma 5.6

The section collects matrix Bernstein concentration tools and applies them to prove the true-tangent sampling isometry required by local RGD analysis. The proof bounds sampling operators using tangent-space geometry and verifies the concentration threshold under the stated sampling assumptions.

B Probabilistic Lemmas

  • Matrix Bernstein inequalities provide the concentration tools used throughout the sampling arguments [26, Theorems 1.6 and 6.1].Both rectangular and self-adjoint forms are collected.Source: B Probabilistic Lemmas · p. 33
  • Lemma B.1 applies to independent mean-zero random matrices with an almost-sure operator-norm bound and specified variance control.The lemma also includes a self-adjoint-operator form on a d-dimensional Hilbert space.Source: B Probabilistic Lemmas · p. 33

B.1 Proof of Lemma 5.6

  • The proof of Lemma 5.6 establishes the true-tangent sampling isometry used in local RGD analysis.It fixes c1 = 215 and represents the sampling deviation through tangent-projected coordinate matrices.Source: §B.1 · p. 33
  • Orthogonality of the tangent-space decomposition and the bound ∥aij∥² ≤ 2μr/(npΛ) control each summand in the concentration argument.The proof also uses E(δij/pΛ − 1)² = (1 − pΛ)/pΛ and (a ⊗ a)² = ∥a∥².Source: §B.1 · p. 33
  • Using dim(TX⋆) = r(2n − r) ≤ 2nr and pΛ ≥ c1μr log n/n, Bernstein concentration applies at threshold 1/16.The argument additionally assumes r ≤ n and n ≥ 2.Source: §B.1 · p. 33
  • These estimates complete the proof of the stated sampling-isometry lemma.The proof concludes after the concentration bound is established.Source: §B.1 · p. 33

B.2 Proof of Lemma 6.1 … C.4.1 Variation of the aligned factors

The appendices establish sampling, geometric, retraction, and comparison estimates supporting the paper’s local analyses. They control singular spaces, graph factors, tangent corrections, nonlinear remainders, and aligned-factor variation under explicit perturbation conditions.

B.2 Proof of Lemma 6.1

  • The union bound in (63)–(64) yields, simultaneously for i ∈[2n] and z ∈Γ, failure probability at most n−12/48 after increasing c2, and the identity proves (37).Source: §B.2 · pp. 34–35

C Deterministic geometry of fixed-rank matrices

  • The deterministic geometry develops tangent coordinates, a graph-retraction identity, sharp-norm and Frobenius estimates, and orthogonal-basis invariance for comparing nearby rank-r matrices.Separate left and right bases are aligned by orthogonal Procrustes transformations, with cores transformed consistently and σmin(S)=σr(X).Source: C Deterministic geometry of fixed-rank… · p. 35, §C.1 · p. 35

C.1 Tangent coordinates and the graph-retraction identity

  • Tangent coordinates decompose perturbations into core and off-subspace blocks, yielding the graph-retraction identity whenever the updated core Σ+M is nonsingular.The coordinates are M=U^TξV, B=(I−UU^T)ξV, and C=(I−VV^T)ξ^TU.Source: §C.1 · p. 35

C.2 Sharp-norm estimates

  • Sharp-norm analysis controls current singular spaces and projectors from Weyl and incoherence bounds, then bounds the normal component and graph factors through a vanishing Schur complement.The resulting estimates support both projector control and rowwise graph-factor bounds under e♯≤σr(X⋆)/8.Source: §C.2 · p. 36, §C.2.1 · p. 36, §C.2.2 · p. 37

C.2.3 Proof of Lemma 5.3; C.2.4 Proof of Lemma 5.4

  • The population tangent correction is exact, while its perturbation admits a nonlinear remainder bound under e♯≤σr(X⋆)/8 and ∥η∥♯≤σr(X⋆)/16.The proof identifies tangent coordinates through graph factors and uses the Schur complement identity for the rank-r target.Source: §C.2.3 · p. 38, §C.2.4 · p. 38

C.3 Proof of Lemma 5.5

  • Frobenius estimates control tangent-space motion and establish the retraction error ∥RetrX(tX+η)−X⋆−η∥F≤2∥X−X⋆∥F∥η∥F+∥η∥F^2.These estimates are used in the local RGD argument and quadratic convergence analysis.Source: §C.3 · p. 39

C.4 Comparison of two nearby matrices; C.4.1 Variation of the aligned factors

  • For nearby matrices, independently aligned Procrustes gauges compare singular factors, projectors, and graph cores while preserving the matrix representation.The comparison framework uses orthogonal basis alignment and graph-factor representations for each matrix.Source: §C.4 · p. 40, §C.4.1 · pp. 40–41

C.4.1 Variation of the aligned factors

  • When both matrices satisfy ρ≤σr(X⋆)/(1000µr), rank(X−Y)≤2r and dX,Y≤2√(2r)ρ; projector estimates show CU and CV are invertible, and both retractions are well defined.Source: §C.4.1 · pp. 40–41

C.4.2 Proof of Lemma 7.6 … F.2 Computational complexity of RGD and RGN

This section develops the technical bounds underpinning spectral initialization, early RGN analysis, and tangent corrections, including sharp-norm control, sampling isometries, leave-one-out estimates, and local correction control. It also establishes comparison tools for nearby iterates and describes matrix-free RGD/RGN implementations with computational-complexity guarantees.

C.4.2 Proof of Lemma 7.6

  • max{∥M_X−M_Y∥_F, ∥B_X−B_Y∥_F, ∥C_X−C_Y∥_F} ≤ Δ, enabling comparison of aligned singular factors.The proof combines aligned bases, tangent and graph coordinates, resolvent identities, and correction-size assumptions.Source: §C.4.2 · pp. 42–43

D.1 Proof of Lemma 6.2

  • The Lemma 6.2 proof controls entrywise reconstruction error by decomposing it into true-space, mixed, and residual terms.The argument uses dilation, singular equations, residual bounds, and incoherence; it also handles the case Z+ = 0.Source: §D.1 · p. 44

D.2 Proof of Lemma 6.3

  • The Lemma 6.3 proof analyzes Gaussian initialization through weighted subspace estimates, retained Ritz factors, spectral separation, and the unreconstructed component.The proof also establishes that thin QR steps are well defined almost surely and that the auxiliary decompositions are not required computationally.Source: §D.2 · pp. 44–46

E.1 Sampling estimates for the completed operators

  • Simultaneous sampling isometries hold for the actual and completed operators, supporting the leave-one-out analysis of initial RGN iterates.The proof uses centered Bernstein bounds, completed row and column restrictions, and a union bound over tangent-space dimensions and index sets.Source: §E.1 · p. 46, §E.1.1 · p. 47

E.1.2 A weighted product estimate

  • The weighted product estimate transfers sampling bounds from the reference tangent space to nearby spaces by controlling weighted row and column sums.Actual weighted sums are at most 2n, while completing one row or column raises the bound to at most 3n.Source: §E.1.2 · p. 47

E.2 Proof of Lemma 7.3

  • Leave-one-out row and column inequalities hold simultaneously with failure probability at most n^-10/48 for all stopped iterates when ¯K ≤ n.The argument conditions outside each row or column, applies Bernstein estimates, and uses transposition plus a union bound.Source: §E.2 · pp. 48–49

E.3 Local solvability and correction size

  • Local sampling invertibility yields the tangent correction estimate needed for early RGN analysis, while nearby-matrix correction variation is treated through Lemma E.3.The local argument assumes e♯ ≤ σ_r(X⋆)/(1000µr) and uses sampling isometries, incoherence, and Weyl’s inequality.Source: §E.3 · pp. 49–50, §E.4 · p. 50

E.4 Comparison of the tangent corrections

  • Tangent transport bounds quantify the error from projecting a tangent correction onto a nearby tangent space under the stated neighborhood and conditioning assumptions.The proof uses tangent decompositions, orthogonality, singular-value lower bounds, and bounds on the correction components.Source: §E.4 · pp. 51–52

E.5 Proof of Lemma 7.5

  • Lemma 7.5 compares actual and leave-one-out tangent corrections through coordinatewise estimates and separate bounds on four correction-error terms.The argument uses row and column transposition, tangent decompositions, conditional Bernoulli independence, and the inverse-operator bound 10/9.Source: §E.5 · pp. 52–55

F Matrix-free implementation and computational complexity

  • Matrix-free RGD iterations cost O(|Ω|r + nr^2), while RGN avoids forming the r(2n − r) × r(2n − r) normal matrix and applies its operators in O(|bΩ|r + nr^2).Graph retractions add O(nr^2 + r^3), and exact conjugate gradients terminate in at most r(2n − r) iterations when the tangent normal operator is positive definite.Source: F Matrix-free implementation and… · p. 56

F.1 Proof of Proposition 2.2

  • The subspace-iteration reconstruction procedure requires O((mr + nr^2) log n) operations, with O(mr + nr^2) additional work for final spectral reconstruction and residual evaluation.This follows from the matrix products, thin QR factorizations, the final r × r singular value decomposition, and evaluating entries on Λ.Source: §F.1 · p. 56

F.2 Computational complexity of RGD and RGN

  • Under Theorems 3.1 and 3.2, RGD and RGN attain relative Frobenius accuracy ε with arithmetic-complexity bounds that combine initialization, matrix-free iterations, sampling rates, and their respective convergence guarantees.For RGN, the complexity bound applies with J_k ≤ J ≤ r(2n − r) for every iteration used to reach the prescribed accuracy.Source: §F.2 · pp. 56–57

Related papers

Loading 2609.17048v1…