PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees

Yudong Chen, Martin J. Wainwright

arXiv:1509.03025v1math.STcs.LGstat.ML

TL;DR

Low-rank estimation often requires solving computationally difficult rank-constrained problems, while factorized iterative methods can suffer from local optima. This paper develops a general theory for projected gradient descent and shows that, with suitable initialization, it converges geometrically to statistically useful solutions across many models, even without local convexity.

  • Problem

    Rank-constrained low-rank estimation is computationally difficult, and factorized iterative methods may suffer from local optima.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes projected gradient descent applied to factorized low-rank optimization through general conditions governing computational and statistical behavior.

    Source: §1 · p. 2, §2.1 · p. 4

  • Results

    With suitable initialization, projected gradient descent converges geometrically to statistically useful solutions across matrix sensing, completion, PCA, clustering, and decomposition models.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework provides guarantees for noisy low-rank estimation without requiring local convexity, including settings such as sparse PCA and clustering.

    Source: §1 · p. 3

    The analyzed initialization requires sample size scaling quadratically with rank, rather than the best possible linear scaling.

    Source: §4.2 · p. 16

Abstract

from arXiv · show

Optimization problems with rank constraints arise in many applications, including matrix regression, structured PCA, matrix completion and matrix decomposition problems. An attractive heuristic for solving such problems is to factorize the low-rank matrix, and to run projected gradient descent on the nonconvex factorized optimization problem. The goal of this problem is to provide a general theoretical framework for understanding when such methods work well, and to characterize the nature of the resulting fixed point. We provide a simple set of conditions under which projected gradient descent, when given a suitable initialization, converges geometrically to a statistically useful solution. Our results are applicable even when the initial solution is outside any region of local convexity, and even when the problem is globally concave. Working in a non-asymptotic framework, we show that our conditions are satisfied for a wide range of concrete models, including matrix regression, structured PCA, matrix completion with real and quantized observations, matrix decomposition, and graph clustering problems. Simulation results show excellent agreement with the theoretical predictions.

1 Introduction

The paper develops a unified theory for projected gradient descent on factorized low-rank estimation problems, establishing geometric convergence and statistical usefulness under conditions broader than local convexity. It applies this framework across diverse noisy statistical models while retaining computational advantages over convex relaxations.

Motivation

  • Projected gradient descent operates in an O(rd)-dimensional factor space instead of the O(d^2) matrix space, addressing the practical cost of semidefinite relaxations.Standard interior-point methods can scale as d^6, while specialized SDP algorithms require at least d^2 time.Source: §1 · pp. 1–2

Core contribution

  • With suitable initialization, projected gradient descent converges geometrically to a statistically useful solution even outside locally convex regions, including globally concave problems.Each iteration typically takes time linear in dr and the input size, supporting both statistical consistency and computational efficiency.Source: §1 · p. 2

Applications

  • The theory is verified for matrix sensing, standard and one-bit matrix completion, sparse principal component analysis, graph clustering, and matrix decomposition or robust PCA.For each model, efficient initialization methods are provided, with sample complexity and statistical error bounds comparable to, and sometimes better than, the best existing results.Source: §1 · p. 2

Scope and distinctions

  • The approach avoids fresh samples at every iteration and repeated singular value decompositions while achieving guarantees for concrete statistical models beyond earlier nonconvex analyses.Noiseless observations are included as a special case of the statistical framework.Source: §1 · pp. 2–3

General theory

  • The unified conditions apply to arbitrary-rank matrices and noisy observations, require neither local convexity nor vanishing gradients, and use only a natural gradient smoothness condition.The framework therefore covers models such as sparse PCA and clustering, where local convexity may be absent.Source: §1 · p. 3

2 Background

This section formulates low-rank matrix estimation through a generally nonconvex factorized program and projected gradient descent. It illustrates the framework with matrix regression, row-sparse PCA, and low-rank-plus-sparse decomposition, while noting further applications.

2.1 Matrix estimators in the factorized formulation

  • The framework minimizes a random data-dependent cost over symmetric matrices, then factorizes low-rank targets and applies projected gradient descent to the resulting nonconvex problem.The theory seeks convergence, up to statistical tolerance ε_n, to an equivalent valid factorization of the target matrix.Source: §2.1 · p. 4
  • The target need not minimize the population objective or have a vanishing population gradient, and the analysis therefore measures error over equivalent factorizations.All valid factorizations share singular values, making the pseudometric invariant to factorization ambiguity.Source: §2.1 · pp. 4–5

2.2.1 Matrix regression

  • Matrix regression observes noisy linear projections of a low-rank matrix; rank-constrained least squares is generally intractable, motivating nuclear-norm relaxation and factorized gradient descent.Under zero-mean noise and the stated regression conditions, the target is the unique population-cost minimizer.Source: §2.2.1 · pp. 5–6

2.2.2 Rank-r PCA with row sparsity

  • Row-sparse rank-r PCA estimates a k-supported leading eigenspace using a factorized relaxation, and the example shows the theory applies even when the factorized objective is globally concave.For R ≥ ∥F∗⊗F∗∥1, M∗ is the unique population minimizer under the stated constraint.Source: §2.2.2 · pp. 6–7

2.2.3 Low-rank and sparse matrix decomposition

  • Low-rank-plus-sparse decomposition models Y = M∗ + S∗ + E and uses nuclear- and ℓ1-norm surrogates, with M∗ generally only a near-minimizer of the population objective.The projected updates use incoherence control and readily computable soft-thresholding projections; the theory also covers real- and binary-observation matrix completion and planted clustering.Source: §2.2.3 · pp. 7–8

3 Main results

The section establishes conditions under which projected gradient descent for low-rank factorizations converges to a statistically accurate neighborhood, with sublinear or faster linear rates. The guarantees remain applicable beyond locally convex objectives, including globally concave examples.

3 Main results

  • Projected gradient iterates are shown to converge to a multiple of a ball around an equivalent factorization, with radius determined by statistical tolerance εn.The framework targets convergence to statistical precision rather than exact recovery.Source: §3 · p. 8

3.1 Conditions on the pair ( eLn, F)

  • The analysis combines M∗-faithfulness, local descent, and local Lipschitz conditions, while local smoothness is additionally required for geometric convergence.Local descent yields quadratic improvement away from equivalent factorizations; the conditions can hold even when the loss is nonconvex or globally concave.Source: §3.1 · pp. 8–10

3.2 Sublinear convergence under Lipschitz condition

  • Theorem 1 guarantees sublinear convergence from a suitable initialization, with optimization error decreasing at O(1/t) and a residual statistical error determined by εn.The constraint set must be M∗-faithful and convex, and the bound separates optimization and statistical errors.Source: §3.2 · pp. 10–11

3.3 Linear convergence under smoothness condition

  • Theorem 2 improves the optimization error to geometric rate O((1 − c)^t) up to statistical error when local smoothness is added.The result requires initialization within a specified neighborhood; step size and rate depend on the factor condition number and initialization quality.Source: §3.3 · p. 11

4 Concrete results for specific models

This section applies the projected-gradient framework to concrete models including matrix completion and regression, sparse PCA, planted densest subgraph, and low-rank-plus-sparse matrix decomposition. It establishes geometric convergence and statistical, exact, or near-optimal recovery guarantees under model-specific initialization, sparsity, noise, and computational conditions, with simulations supporting the predicted behavior.

4 Concrete results for specific models

  • Across the models, the analysis verifies local descent, Lipschitz, and smoothness conditions needed for Theorem 2, while Theorem 1 also supports weaker corollaries without local smoothness.The results use constant-step-size projected gradient descent and require suitable initialization, with model-specific conditions establishing geometric convergence.Source: §4 · p. 11

4.1 Noisy matrix completion

  • For noisy matrix completion, if d(F 0, F ∗) ≤ 1/5|||F ∗|||op and n = pd2 ≿ max{µrd log d, µ2r2d}, then with probability at least 1−4d−3, eLn satisfies local descent, Lipschitz, and smoothness conditions.Source: §4.1 · p. 13

4.2 Matrix regression

  • For matrix regression, RIP with δ4r ∈ [0, 1/12) yields geometric convergence from any initialization within (1−√12δ4r)σr of F∗, even though the loss need not be convex in that region.For Gaussian designs, n ≿ rd log d suffices for RIP and a constant contraction factor, while the basic SVD initialization requires the looser n ≿ dr^2κ^4 log d scaling; more sophisticated initialization can avoid this quadratic rank dependence [36, 37].Source: §4.2 · pp. 15–16

4.3 Rank-r PCA with row sparsity

  • For row-sparse PCA, projected gradient descent is analyzed under previously stated conditions from any initialization within distance 1−τ of F*, while the loss is globally concave in F.The error rate εn is minimax optimal up to a logarithmic factor in n, d, k, and r [59, 15]. Initialization can be obtained by diagonal thresholding when n ≿ k2 log d, reflecting a computational barrier.Source: §4.3 · p. 17
  • In rank-r PCA with row sparsity, both diagonal-thresholding and perturbation initializations show initially geometric statistical convergence followed by an error floor at statistical precision.With fixed (d, r, γ), the squared estimation error scales proportionally with k/n when n is sufficiently large, as confirmed by Figure 2(c).Source: §4.3 · p. 18

4.4 Planted densest subgraph

  • For planted densest subgraph, projected gradient descent achieves exact cluster recovery under condition (27), matching the best existing results, with recovery emerging above a constant threshold in the simulated regime.The algorithm converges at least geometrically, and simulations confirm that exact recovery occurs with probability close to one once pd exceeds a constant threshold when q = p/3 and k = d/2.Source: §4.4 · pp. 19–20

4.5 One-bit matrix completion

  • For one-bit matrix completion, projected gradient descent converges geometrically from a constant-radius initialization and attains the exact-low-rank minimax error rate in polynomial time.The guarantee applies to binary observations generated through logistic, probit, or Laplacian links; its error bound has the same form as standard matrix completion, with a prefactor depending on the SNR ν.Source: §4.5 · pp. 22–23

4.6 Low-rank and sparse matrix decomposition

  • The low-rank-plus-sparse matrix decomposition model assumes incoherent equal-eigenvalue factors and a deterministic sparse perturbation with at most k nonzeros per row or column, then replaces convex regularization with projected gradient descent.The constrained formulation uses nuclear- and ℓ1-norm surrogates, while the factorized loss is convex because it measures squared distance to a closed convex set.Source: §4.6 · pp. 23–24
  • Under the stated conditions, projected-gradient iterates from a sufficiently close initialization satisfy the matrix-decomposition guarantee.The conditions include faithfulness of the constraint set, bounded sparsity, and a noise norm bound relative to the signal.Source: §4.6 · p. 24
  • The same result matches the best existing deterministic matrix-decomposition results and extends to adversarial missing entries when each row and column has at most k ≤ c1 d µr missing entries.Missing entries can be filled arbitrarily and treated as sparse corruption.Source: §4.6 · p. 24
  • In the noiseless setting, hard-thresholding followed by projected top-r singular vectors provides an initialization satisfying the corollary’s requirement under the stated condition.The construction assumes ||F ∗||op = 1 and uses thresholding at level µr/d.Source: §4.6 · pp. 24–25
  • Figure 5 shows geometric convergence; with σ = 0, exact recovery occurs with probability close to one once k/d is sufficiently small, while recovery succeeds with high probability below a constant rk/d threshold.The experiments use the SVD-based initialization and fixed step size ηt ≡ 1; Panel (c) confirms the predicted recovery threshold.Source: Figure 5 · p. 25, §4.6 · p. 25
  • The gradient computation uses efficient row-wise projections onto ℓ1 balls, while projection onto the factor constraint set is implemented by row-wise clipping.These operations compute ∇MLn(M) = M + ΠS(Y − M) − Y.Source: §4.6 · p. 25

5 Proofs of general theorems

The section proves the paper’s two general projected-gradient convergence theorems using induction, projection geometry, and auxiliary matrix lemmas. It establishes the geometric and recursive bounds required for Theorems 1 and 2.

5.1 Proof of Theorem 1

  • Theorem 1 is proved by induction: its base assumptions are preserved by projected gradient descent, yielding d(F_t+1, F*) ≤ ρ and the theorem’s bound.The argument uses the two-step gradient/projection decomposition, non-expansiveness of Euclidean projection, and the Lipschitz condition to control each iterate.Source: §5.1 · pp. 26–27

5.1.1 Proof of Lemma 1

  • Lemma 1 proves that when d(F, F*) < σ_r(F*), the projection onto E(M*) has a unique optimizer with positive-definite alignment and symmetric residual cross-product.The proof shows F has full column rank, F^T F*_0 is invertible, and orthogonal alternatives are strictly worse.Source: §5.1 · p. 26, §5.1.1 · p. 28

5.2 Proof of Theorem 2

  • Theorem 2’s analysis uses Lemma 1 to define the relevant projections at each iterate, then combines the relaxed Lipschitz and smoothness conditions with Lemma 2 to prove the intermediate inequality.The resulting inequalities establish the update control needed for induction and the theorem’s recursive convergence argument.Source: §5.2 · pp. 29–31
  • Theorem 2’s proof establishes the induction step through a bound on the update and a recursive inequality, completing the theorem under its relaxed smoothness conditions.With C = 272 and max{τ, 1/κ, α/β} ≤ 1, the update satisfies ||Λ_t||_F ≤ τ(1 − τ)ψ before the recursive bound is derived.Source: §5.2 · pp. 29–30

5.2.1 Proof of Lemma 2

  • Lemma 2 controls the change between aligned iterates by bounding singular values of the alignment matrices and applying a perturbation bound for matrix square roots.After normalization to ψ = 1, the singular values of the relevant matrices lie in [τ^2, κ + (1 − τ^2)].Source: §5.2.1 · pp. 31–32

6 Proofs of corollaries

This section proves the corollaries by transferring the general factorized-loss theory and verifying the required descent, Lipschitz, and smoothness conditions across the matrix models considered. The arguments use model-specific decompositions and concentration bounds.

6 Proofs of corollaries

  • Theorem 3 states that, under the corresponding conditions for L_n, the conclusion of Theorem 2 holds.The transfer uses eL_n(F) = L_n(F⊗F) and verifies equivalent local descent, relaxed Lipschitz, and smoothness conditions.Source: §6 · pp. 32–33

6.1 Proof of Corollary 2

  • For matrix sensing, RIP-based inner-product preservation verifies local descent, Lipschitz, and smoothness with α = 6δ_4r, L = β = 64κ^2, and ρ = 1−12δ_4r.The proof normalizes σ_r = 1 and derives the conditions from the matrix-sensing gradient and RIP bounds.Source: §6.1 · pp. 33–35

6.2 Proof of Corollary 1

  • For matrix completion, incoherence and clipping establish faithfulness, while projection lemmas preserve relevant inner products and control small matrices with probabilities at least 1−2d^-3 and 1−2d^-4.These bounds support verification of local descent, Lipschitz, and smoothness conditions for L_n.Source: §6.2 · pp. 35–36

6.3 Proof of Corollary 3

  • For sparse PCA, row sparsity ensures faithfulness and places the error in a sparse cone, while covariance-noise control establishes local descent with probability at least 1−8d^-4.The proof lower-bounds the deterministic term using γ and τ and applies Lemma 6 to control the noise term.Source: §6.3 · pp. 38–39
  • For Corollary 3, the proof establishes the relaxed Lipschitz condition and the second smoothness condition for Ln, while the first smoothness condition holds trivially.The bounds combine signal and noise terms, with the noise control supplied by Lemma 6 and probability at least 1 −8d−4.Source: §6.3 · p. 40

6.4 Proof of Corollary 4

  • For planted densest subgraph, the proof establishes the local descent condition (49) and relaxed Lipschitz condition (50) for Ln, combining bounds under clustering condition (27) with β = 12(p −q)k.Source: §6.4 · pp. 41–42

6.5 Proof of Corollary 5

  • The cited proof establishes the local descent condition (49) for Ln with probability at least 1 −3d−12 and separately establishes the local smoothness condition (52a).It also gives P[E(B)] ≤2d−14 and P[E0] ≤d−12.Source: §6.5 · pp. 44–46

6.6 Proof of Corollary 6

  • For matrix decomposition, the proof decomposes the gradient into four terms and combines their bounds to establish the local descent condition (49).It normalizes |||F ∗|||op = 1 and uses the non-expansiveness of ΠS to obtain |||∆S|||F ≤ |||M −M∗|||F ≤3|||∆|||F.Source: §6.6 · p. 47
  • The argument establishes that L_n satisfies the local Lipschitz condition in (51).Source: §6.6 · p. 48
  • The first smoothness condition (52a) follows by bounding the gradient difference using the operator- and Frobenius-norm relationship.Source: §6.6 · p. 48
  • The second smoothness condition (52b) is verified by combining inequality (68) with |||E|||F ≤ 2.Source: §6.6 · p. 48

7 Discussion

The paper presents a general framework for analyzing projected gradient descent on factorized low-rank optimization problems and demonstrates its implications across several concrete models.

7 Discussion

  • The framework analyzes projected gradient descent for low-rank optimization in factorized space and applies to matrix regression, structured PCA, matrix completion, matrix decomposition, and graph clustering.These models illustrate the consequences of the general theory.Source: §7 · p. 48

A Proof of Theorem 3 · B Technical lemmas for Corollary 2

The appendix proves Theorem 3 by transferring descent, Lipschitz, and smoothness conditions from L_n to its factorized counterpart eL_n under matching parameters and ρ < σ_r(F*). It also introduces technical lemmas used to establish Corollary 2 for matrix sensing.

A Proof of Theorem 3

  • Theorem 3 follows by showing that L_n’s conditions in Definitions 5–7 imply the corresponding conditions for eL_n with identical parameters and ρ < σ_r(F*).The transferred conditions are relaxed local Lipschitzness, local descent, and smoothness.Source: A Proof of Theorem 3 · p. 49
  • Because ρ < σ_r(F*), Lemma 1 makes the projection F_π* onto E(M*) uniquely defined, enabling the proof’s error decomposition.The argument uses Δ_π* = F − F_π* and Δ = F − F* for F near F*.Source: A Proof of Theorem 3 · p. 49
  • Applying L_n’s local descent and smoothness conditions to the decomposed error establishes the local descent condition for eL_n.The derivation uses Δ = Δ_π* + F_π* − F* and bounds based on the triangle inequality, AM-GM, and α ≤ β.Source: A Proof of Theorem 3 · p. 49
  • Using symmetry of G(F⊗F) and L_n’s relaxed Lipschitz condition proves the relaxed local Lipschitz condition for eL_n.The argument applies the corresponding condition for arbitrary F in the factor domain.Source: A Proof of Theorem 3 · p. 49
  • L_n’s smoothness conditions (52a) and (52b), applied to the gradient difference decomposition, establish smoothness condition (16) for eL_n.The decomposition separates terms involving G(F⊗F)−G(F′⊗F′) from those involving F−F′.Source: A Proof of Theorem 3 · p. 50

B Technical lemmas for Corollary 2

B.1 Proof of Lemma 3 · C Technical lemmas for Corollary 1

The appendix proves Lemma 3 using bilinearity and a rank-based RIP argument, then develops technical lemmas for Corollary 1 in the matrix completion model.

B.1 Proof of Lemma 3

  • Bilinearity permits assuming |||A|||F = |||B|||F = 1 in the proof of Lemma 3.Source: §B.1 · p. 50
  • The proof applies the RIP with δ4r to matrices A ± B.Source: §B.1 · p. 50
  • Both matrices A + B and A − B have rank at most 4r, matching the RIP order used in the argument.Source: §B.1 · p. 50
  • A similar argument yields the subsequent bound in the proof of Lemma 3.Source: §B.1 · p. 50

C Technical lemmas for Corollary 1

C.1 Proof of Lemma 4

The proof defines a tangent-like subspace T, uses incoherence-based matrix-completion concentration on T, and applies the resulting projection inequality to establish both inequalities in Lemma 4.

C.1 Proof of Lemma 4

  • The proof defines T as matrices of the form (F*⊗U) + (V⊗F*) and lets Π_T denote Euclidean projection onto T.Source: §C.1 · p. 50
  • Because F* is 4µ-incoherent, a known exact matrix-completion result guarantees exact matrix completion as long as p ≥ cµr log d.Source: §C.1 · p. 51
  • Applying the concentration inequality to matrices in T proves the first lemma inequality; the second follows identically because (F*⊗H) ± (F*⊗G) also lie in T.Source: §C.1 · p. 51

C.2 Proof of Lemma 5

The proof invokes a random-graph result with universal constants, then establishes inequalities (57a)–(57c) using degree concentration and conditioning on a bounded-degree event.

C.2 Proof of Lemma 5

  • A random-graph result involving universal constants c1 and c2 is used in the proof.Source: §C.2 · p. 51
  • The bounded-degree event yields the first inequality (57a), supports the second inequality (57b) by assumption, and enables the proof of the third inequality (57c) by conditioning.Source: §C.2 · pp. 51–52
  • When p ≥ C log d for sufficiently large C, all sets Ω_i have size at most 2pd with probability at least 1 − d^-4.Source: §C.2 · p. 52

D Proof of Lemma 6

The proof rescales the matrices, reduces the target bound to convex combinations of rank-constrained components, and controls the resulting supremum using Cauchy–Schwarz and Gaussian concentration. A concentration lemma from Loh and Wainwright [46] then yields the required bound with probability 1−2d−4.

Rescaling

  • The argument rescales U and V to unit Frobenius norm before proving the bound.It works with U,V∈B2,1(k).Source: D Proof of Lemma 6 · p. 52

Geometric reduction

  • A geometric result, presented as a generalization of Lemma 11 in [46], reduces the proof to pairs in conv{B2,0(k)∩BF(3)}.Continuity justifies this reduction.Source: D Proof of Lemma 6 · p. 52

Convex decomposition

  • Each reduced matrix is represented as a weighted combination of rank-constrained constituents with weights summing to one.The constituents Ui and Vj lie in B2,0(k)∩BF(3).Source: D Proof of Lemma 6 · p. 52

Supremum bound

  • Cauchy–Schwarz and the Frobenius-norm bound reduce the remaining task to controlling a supremum by 18t.The constituent matrices have Frobenius norm at most 3.Source: D Proof of Lemma 6 · p. 53

Gaussian concentration

  • For Gaussian samples with covariance Σ=γ(F*⊗F*)+I_d, Lemma 15 of Loh and Wainwright [46] supplies the needed concentration.Combining this result with the selected t and c′=8c gives the target inequalities with probability 1−2d−4.Source: D Proof of Lemma 6 · p. 53

D.1 Proof of Lemma 10 · E Technical lemmas for Corollary 5 · E.1 Proof of Lemma 7

The appendix proves the set-inclusion argument for Lemma 10 and develops technical bounds needed for Corollary 5 on one-bit matrix completion. The proof of Lemma 7 combines symmetrization, Gaussian-process comparison, rank and Lipschitz bounds, and concentration to control both tails.

D.1 Proof of Lemma 10

  • Lemma 10 verifies set inclusion by comparing support functions of the relevant closed convex sets.The argument uses the equivalence φ_A(U) ≤ φ_B(U) for all U and A ⊆ B.Source: §D.1 · p. 53
  • Selecting the top ⌊k⌋ rows of U in ℓ2 norm controls the complementary row norm and supports the support-function comparison.The proof combines the row-selection inequality with an earlier bound and the expression for φ_B(U).Source: §D.1 · pp. 53–54

E Technical lemmas for Corollary 5

  • The appendix introduces proofs of the technical lemmas required for Corollary 5 on one-bit matrix completion.This establishes the scope of the technical appendix before the detailed proof of Lemma 7.Source: E Technical lemmas for Corollary 5 · p. 54

E.1 Proof of Lemma 7

  • Lemma 7 bounds the expected supremum by symmetrizing the process, comparing it with a Gaussian process, and applying Sudakov–Fernique.The Gaussian variables are independent standard normals, and the comparison uses metric domination between the original and alternative processes.Source: §E.1 · pp. 54–55
  • The process comparison is controlled using bounded, Lipschitz coordinate functions, Cauchy–Schwarz, generalized Hölder, and rank-at-most-r structure.The proof also invokes E_Q,g[||g ◦ Q||_op] ≤ c(√pd + log d) ≤ 2c√pd under p ≥ log^2 d/d.Source: §E.1 · pp. 55–56
  • The resulting upper-tail bound is P[Z ≥ E_Q,Y[Z] + 1/8 αεn] ≤ d^-14, together with the expectation bound E_Q,Y[Z] ≤ 1/8 αεn.Source: §E.1 · p. 56

E.2 Proof of Lemma 8

The proof reduces Lemma 8 to bounding T1, T2, and T3 by 1/12 αε_n with probability at least 1−d^-12. It controls these terms using Lipschitz properties, operator-norm bounds, and a censored sub-Gaussian matrix result.

E.2 Proof of Lemma 8

  • T1 is bounded using h's element-wise 4L4ν-Lipschitz property, |||F|||op≤2, and ν=µr.The argument applies Cauchy–Schwarz to the gradient expression and uses the definition of ν.Source: §E.2 · p. 57
  • With probability at least 1−d^-12, it suffices to show each of T1, T2, and T3 is at most 1/12 αε_n.This reduction organizes the remainder of the proof term by term.Source: §E.2 · p. 57
  • The censored sub-Gaussian bound gives |||ΠΩh(M∗/σ)|||op≤CL4ν√pd with probability at least 1−d^-12, implying T2≤4CL4ν.This uses ∥M∗/σ∥∞≤4ν and Lemma 11.Source: §E.2 · p. 57
  • T3 is controlled from |||F|||op≤2 and the bounds |f′(x)f(x)(1−f(x))|≤√L4ν and |f(x)−f(x′)|≤√L4ν|x−x′|.Together with ν=µr, these estimates complete the lemma's proof.Source: §E.2 · p. 57

F Proof of inequality (32) · G Spectral norms of censored sub-Gaussian random matrices

The appendix proves inequality (32) by combining incoherence, sparsity, singular-value separation, and perturbation bounds. It also establishes spectral-norm bounds for symmetric censored sub-Gaussian random matrices using symmetrization, truncation, concentration, and tail integration.

F Proof of inequality (32)

  • F uses incoherence to bound ∥F ∗⊗F ∗∥∞ by µrSource: F Proof of inequality (32) · p. 58
  • F shows that Y −F ∗⊗F ∗ is supported on the nonzero entries of S∗, with at most k nonzeros in each row and column.Source: F Proof of inequality (32) · p. 58
  • Using Proposition 3, the unit singular-value gap, and Wedin’s sin Θ theorem [30], F bounds the projected initialization error by d(F 0, F ∗) ≤4µr√rk.The argument first controls the principal-angle distance between the top-r singular subspaces of Y and F ∗⊗F ∗, then uses non-expansiveness of projection onto the convex set F.Source: F Proof of inequality (32) · p. 58

G Spectral norms of censored sub-Gaussian random matrices

  • G states Lemma 11 for symmetric matrices X with entries Xij = gijQij, where gij are independent zero-mean sub-Gaussian variables and Qij are independent Bernoulli variables with parameter p.The two families of variables are mutually independent, and the lemma provides a universal-constant spectral-norm bound.Source: G Spectral norms of censored… · p. 58
  • G reduces the lemma to symmetric variables, applies Bandeira and van Handel’s proposition [5], and truncates entries at b√log d to handle unbounded sub-Gaussian values.For the truncated matrix, the proposition is applied using ˜σ∗≤b√log d and ˜σ ≤√pd.Source: G Spectral norms of censored… · pp. 58–59
  • G derives the truncated-matrix spectral-norm bounds by selecting t proportional to log d and combining Proposition 1 with the resulting tail bound.Source: G Spectral norms of censored… · p. 59
  • G controls the discarded large-entry matrix through sub-Gaussian maxima, concentration for convex Lipschitz functions, and integration of tail bounds, completing Lemma 11.Source: G Spectral norms of censored… · p. 59

Related papers

Loading 1509.03025v1…