Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution

1.1 Nonlinear systems and empirical loss minimization

• The underlying problems are nonlinear empirical-loss minimization tasks, including quadratic phase retrieval, incomplete low-rank matrix completion, and bilinear blind deconvolution.These applications involve reconstructing unknown objects or signals from nonlinear measurements, such as squared magnitudes, observed matrix entries, or bilinear measurements.Source: §1.1 · p. 4, • Low-rank matrix completion · p. 4

1.2 Nonconvex optimization via regularized gradient descent

• Prior theory commonly stabilizes nonconvex optimization using trimming, regularized losses, or projection, whereas vanilla gradient descent has minimal tuning but lacks guarantees for matrix completion and blind deconvolution.For phase retrieval, existing vanilla guarantees were slower than those for truncated Wirtinger flow because theory required a more conservative step size.Source: §1.2 · p. 5, §1.3 · p. 6

1.4 Numerical surprise of unregularized gradient descent

• Experiments show vanilla gradient descent reaches relative accuracy 10^-5 within around 200 iterations across the three problems, with phase-retrieval rates changing little as n grows from 20 to 1000.The experiments use constant step sizes and spectral initialization; phase retrieval uses ηt = 0.1, matrix completion ηt = 0.2, and blind deconvolution ηt = 0.5.Source: §1.4 · p. 6, • Blind deconvolution · p. 7, Figure 1 · p. 7
• In matrix completion, vanilla GD and GD with regularized cost have almost identical recovery phase transitions, while projected GD performs slightly better than both.The comparison uses 50 randomly generated instances, η = 0.2, and declares success when relative Frobenius error is at most 10^-5 within 10^4 iterations.Source: • Blind deconvolution · p. 7, Figure 2 · p. 8

1.5 This paper

• Vanilla gradient descent implicitly regularizes its iterates by keeping them incoherent with the measurement mechanism, explaining its favorable performance without explicit regularization.The paper analyzes this phenomenon for phase retrieval, matrix completion, and blind deconvolution under random designs and spectral initialization.Source: §1.5 · pp. 7–8
• For phase retrieval, matrix completion, and blind deconvolution, vanilla gradient descent achieves nearly linear convergence with near-optimal sample complexity under the paper’s stated conditions.The paper also claims statistical and computational efficiency for attaining ϵ-accuracy, while the precise informal rates are deferred to later sections.Source: §1.5 · p. 8

2.1 Gradient descent theory revisited

• Under strong convexity and smoothness, gradient descent contracts linearly, but its iteration complexity scales with the condition number β/α.The standard step size is η_t = 2/(α+β), and the same reasoning extends locally to nonconvex objectives when initialization lies inside the favorable neighborhood.Source: §2.1 · pp. 9–10

2.2 Local geometry for solving random quadratic systems

• For phase retrieval with m ≍ n log n, local strong convexity persists, but smoothness can scale as O(n), yielding an overly conservative step size and pessimistic convergence rate.Thus, generic gradient-descent theory fails to explain fast vanilla convergence unless the sample size is enormously larger than the dimension.Source: §2.2 · pp. 10–11

2.3 Which region enjoys nicer geometry?

• The region of incoherence and contraction (RIC) combines proximity to the solution with incoherence, giving phase retrieval a Hessian condition number bounded by O(log n).Within the RIC, gradient descent can use a step size as large as η_t = O(1/log n), provided iterates remain there; leaving it risks losing benign geometry and overshooting.Source: §2.3 · pp. 11–12

2.4 Implicit regularization

• Vanilla gradient descent implicitly preserves incoherence: with high probability, spectral initialization and all subsequent iterates remain in the RIC, enabling fast convergence without explicit regularization.In a phase-retrieval trial with η_t = 0.1, the incoherence measure remained bounded by 2 across all iterations.Source: §2.4 · p. 12

2.5 A glimpse of the analysis: a leave-one-out trick

• A leave-one-out trajectory omitting each sample is nearly identical to the full trajectory yet independent of that sample, allowing incoherence to be controlled and transferred back to the actual iterates.Combining closeness between the auxiliary and full iterates with independence yields the desired incoherence bound; the technique is intended to generalize beyond phase retrieval.Source: §2.5 · pp. 12–13

3 Main results

• Gradient descent achieves near-optimal statistical and computational guarantees for phase retrieval, matrix completion, and blind deconvolution through implicit regularization.The main results formalize trajectories that remain in incoherent regions despite the absence of explicit regularization.Source: §3 · p. 13

3.1 Phase retrieval

• Phase retrieval iterates remain incoherent throughout, while Wirtinger flow converges nearly linearly with η ≍1/log n in O(log n log(1/ϵ)) iterations.With m ≍n log^2 n, a constant step size η ≍1 is feasible; random initialization also attains ε-accuracy in O(log n + log(1/ε)) iterations.Source: §3.1 · p. 14
• The phase-retrieval spectral initializer is incoherent with the design vectors, strengthening prior characterizations focused primarily on ℓ2 accuracy.The analysis is expected to accommodate other spectral-initialization variants [LL17].Source: §3.1 · p. 14

3.2 Low-rank matrix completion

• For noisy matrix completion, vanilla gradient descent achieves near-optimal accuracy and complexity under near-optimal sample complexity, with linear convergence in Frobenius, ℓ2/ℓ∞, and spectral norms.The guarantees apply to µ-incoherent PSD matrices with fixed condition number and n^2p ≥Cµ^3r^3n log^3 n, using η ≤2/(25κσmax).Source: §3.2 · p. 16
• Matrix-completion iterates remain incoherent without penalty terms or projection, while their Euclidean error matches prior guarantees and minimax lower bounds [CW15].The result also yields near-optimal entrywise error control for sufficiently large iteration counts.Source: §3.2 · p. 16

3.3 Blind deconvolution

• Blind deconvolution succeeds with near-optimal statistical and computational complexity, while unregularized iterates remain incoherent and need neither scaling nor incoherence regularization.For m ≥Cµ^2K log^9 m and sufficiently small constant η, the guarantee holds with probability exceeding 1 −c1m−5 −c1me−c2K.Source: §3.3 · p. 19
• Blind deconvolution permits η ≍1 and reaches ϵ-accuracy in O(log(1/ϵ)) iterations, improving the prior O(m log(1/ϵ)) iteration bound by a factor of m.The method also succeeds at near-optimal sample complexity up to logarithmic factors, although its requirement is slightly worse than explicitly regularized theory.Source: §3.3 · p. 19

Overview

• Convex relaxations offer strong statistical guarantees for nonlinear estimation but are often prohibitively expensive at large scale, motivating nonconvex alternatives with global-recovery guarantees.Nonconvex methods have been studied for phase retrieval [NJS13, CLS15, CC17], matrix sensing and completion [CW15], blind deconvolution, and other problems.Source: §4 · pp. 19–20

Phase retrieval

• Phase-retrieval research progressed from convex lifting and linear programming to alternating minimization and globally convergent nonconvex methods, including Wirtinger Flow and amplitude-based losses.The amplitude-based loss in was shown to have better curvature, enabling vanilla gradient descent with a constant step size at order-wise optimal sample complexity.Source: §4 · p. 20

Matrix completion

• Matrix-completion work established near-optimal convex recovery under incoherence and developed regularized or projected nonconvex methods, but lacked rigorous guarantees for unregularized gradient descent without sample splitting.This work claims the first contribution toward understanding implicit regularization in that setting; treated unregularized stochastic gradient descent online using fresh samples each iteration.Source: §4 · p. 20

Blind deconvolution

• Blind-deconvolution methods include convex lifting, regularized gradient descent, and partially unregularized Riemannian descent, while existing approaches still regularize incoherence or impose restrictive signal knowledge.Ahmed et al. introduced lifting with near-optimal convex guarantees; used regularization for scaling ambiguity and incoherence, and removed only scaling regularization.Source: §4 · p. 20

Analysis framework

• Leave-one-out perturbation arguments have yielded tight guarantees for several high-dimensional statistical and spectral methods, but had not previously been applied to nonconvex optimization algorithms.Applications include robust M-estimation, sparse regression inference, phase synchronization [AFWZ17], ranking, community recovery [AFWZ17], and covariance sketching [LMCC18].Source: §4 · p. 21

Implicit regularization

• Implicit regularization has also been proposed for matrix factorization, stochastic-gradient learning, and deep neural-network training, beyond the models and algorithms studied here.Examples include minimal-norm solutions in over-parameterized matrix factorization and implicit Tikhonov regularization in statistical learning.Source: §4 · p. 21

5.2 Outline of the recipe

• Leave-one-out sequences remove one sample to make iterates independent of its design vectors, enabling induction-based control of incoherence along the original trajectory.The proof shows original and auxiliary iterates remain close through restricted strong convexity, controls auxiliary incoherence using independence, and combines both bounds to preserve the RIC; the auxiliary sequences are analytical only.Source: §5 · p. 21, §5.2 · pp. 22–23

5.1 General model

• The general bilinear/quadratic model encompasses phase retrieval, matrix completion, and blind deconvolution as special cases.It permits real or complex vector and tall-matrix objects with random or deterministic design vectors, and analyzes vanilla gradient descent from spectral initialization.Source: §5.1 · pp. 21–22

5.2 Outline of the recipe

• The recipe first identifies an incoherence-and-contraction region where restricted strong convexity and smoothness yield linear convergence when all iterates remain inside it.The contraction rate is 1 −O(α/β) for a properly chosen step size η, with β/α scaling slowly or remaining bounded with problem size.Source: §5.2 · p. 22

6.1.1 Local geometry

• With m ≥ c_0 n log n, the phase-retrieval Hessian is positive definite and nearly well-conditioned near the truth for incoherent points, with high probability.Lemma 1 identifies the relevant region through proximity to x⋆ and incoherence relative to the measurement vectors.Source: §6.1.1 · p. 24

6.1.2 Error contraction

• Within the restricted incoherence-and-contraction region, gradient descent contracts the ℓ2 error when 0 < η ≤ 1/[5C_2(10 + C_2) log n].This converts the local geometry into the contraction step used in proving Theorem 1.Source: §6.1.2 · p. 24
• Theorem 1 follows once the gradient-descent trajectory remains in a region of incoherence and contraction through time T_0 = n.The proof establishes this trajectory property inductively with high probability, after verifying spectral initialization.Source: §6.1.2 · p. 24, §6.3 · p. 26

6.2 Step 2: introducing the leave-one-out sequences

• Leave-one-out iterates remove one measurement, remain independent of its sampling vector, and enable control of the incoherence condition despite dependence between the original iterates and measurements.The auxiliary sequences are initialized from leave-one-out data and updated using the corresponding leave-one-out loss.Source: §6.2 · p. 25

6.3 Step 3: establishing the incoherence condition by induction

• Induction preserves incoherence by first bounding the gap between original and leave-one-out iterates, then applying Gaussian concentration and combining the resulting bounds.The argument uses restricted strong convexity and a union bound to establish the induction hypotheses through t ≤ T_0 = n.Source: §6.3 · p. 26

6.4 The base case: spectral initialization

• Spectral initialization establishes the induction base case with high probability when m > c_0 n log n, using Davis–Kahan bounds for proximity and leave-one-out proximity.The remaining initialization incoherence claim follows by the same argument used for the iterative bound.Source: §6.4 · p. 27

7 Analysis for matrix completion

• Together, the local geometry, norm-wise contractions, leave-one-out comparison, and initialized induction establish the matrix-completion trajectory analysis underlying Theorem 2.The proof proceeds by verifying the base case and propagating the induction hypotheses across iterations.Source: §7 · p. 27, §7.3 · p. 30, §7.4 · p. 32

7.1.1 Local geometry

• The analysis establishes restricted strong convexity and smoothness near X⋆ for incoherent points and appropriate spectral-norm directions, despite the Hessian being rank-deficient.This restricted formulation accommodates the inherent non-identifiability of the factorization.Source: §7.1.1 · p. 28

7.1.2 Error contraction

• Under the stated sample-size, noise, and stepsize conditions, the iterates contract in Frobenius norm and, when all invariants hold, also in spectral norm.The contraction events are uniform over iterations and rely on the local geometry from Lemma 7.Source: §7.1.2 · p. 28

7.2 Step 2: introducing the leave-one-out sequences

• Leave-one-out sequences replace each row or column’s samples with population means, yielding unbiased surrogates that facilitate control of the trajectory’s statistical dependence.The construction uses auxiliary losses and corresponding gradient-descent sequences for each index.Source: §7.2 · p. 29

7.3 Step 3: establishing the incoherence condition by induction

• Induction preserves incoherence by proving proximity between true and leave-one-out iterates, incoherence of the independent surrogates, and then combining both bounds.The leave-one-out iterate is independent of samples in the corresponding row or column, enabling incoherence control.Source: §7.3 · pp. 30–32

7.4 The base case: spectral initialization

• Spectral initialization satisfies the induction hypotheses simultaneously at t = 0 under the stated sample-size, noise, and condition-number assumptions.The base case invokes Davis–Kahan and entrywise eigenvector perturbation results.Source: §7.4 · p. 32

8 Analysis for blind deconvolution

• The blind-deconvolution derivation uses Wirtinger gradients and Hessians for the complex-valued empirical loss, defines alignment, and shows alignment with the ground truth.Because the loss is real-valued, conjugate-gradient terms can be omitted from the update representation.Source: §8 · pp. 32–33

8.1.1 Local geometry

• The loss has restricted strong convexity and smoothness on a local region near the truth, despite its population Hessian being rank-deficient.The region combines proximity to the ground truth, incoherence with both sensing-vector families, and scaling factors allowing different step sizes for h and x.Source: §8.1.1 · p. 34

8.1.2 Error contraction

• Gradient descent contracts the blind-deconvolution error linearly while iterates remain in the incoherence-and-contraction region, yielding Theorem 3 by induction and a union bound.The contraction factor is ρ = 1 − η/16 for sufficiently small constant step size and adequate sample complexity.Source: §8.1.2 · p. 34, §8.3 · p. 37

8.2 Step 2: introducing the leave-one-out sequences

• Leave-one-out sequences generated by spectral initialization and gradient descent remove each measurement pair, enabling independence-based control of the original iterates’ incoherence.These auxiliary trajectories are constructed from the leave-one-out loss and are central to handling statistical dependence between iterates and measurement vectors.Source: §8.2 · p. 35

8.3 Step 3: establishing the incoherence condition by induction

• An induction proves proximity between original and leave-one-out iterates and preserves incoherence for x with respect to {a_l} and h with respect to {b_l}.The h-incoherence argument propagates randomness through binning consecutive indices, while the leave-one-out bounds use Gaussian concentration and restricted convexity.Source: §8.3 · pp. 36–37

8.4 The base case: spectral initialization

• Spectral initialization satisfies the induction hypotheses with high probability when m is sufficiently large, providing closeness to truth, near-unit alignment, leave-one-out proximity, and incoherence.The initialization guarantees include | |α_0| − 1 | ≤ 1/4 and separate sample-size conditions for the required bounds.Source: §8.4 · p. 38

9 Discussions

• The paper argues that vanilla gradient descent can implicitly regularize a broad family of nonconvex statistical estimation problems, extending beyond the three studied cases.The authors present these results as initial steps toward understanding a fundamental phenomenon and identify numerous avenues for future work.Source: §9 · p. 39
• Matrix completion currently requires sub-optimal sample complexity for large rank r, despite achieving dimension-free iteration complexity.The paper expects lower sample complexity to be attainable through a more refined analysis, such as generic chaining.Source: §9 · p. 39
• The leave-one-out analysis relies on independent designs and remains difficult to extend to general sampling patterns and structured Fourier designs.Fourier designs already require more delicate treatment than purely Gaussian designs in the blind-deconvolution analysis.Source: §9 · p. 39
• Leave-one-out stability resembles uniform stability in statistical learning theory and may help analyze other uniformly stable learning algorithms [BE02].The key property is that estimates or predictions change little when one sample is excluded.Source: §9 · p. 39
• The discussion calls for theoretical and empirical comparisons across iterative methods and loss functions beyond vanilla gradient descent and squared loss.Examples include alternating minimization, block coordinate descent, sub-gradient methods, and prox-linear methods for non-smooth losses.Source: §9 · p. 39
• The paper suggests that its implicit-regularization perspective may shed light on why simple gradient-based methods succeed in over-parameterized deep learning [FMZ19].This connection is proposed cautiously because deep networks have substantially more nonlinear nonconvex geometry than the bilinear and quadratic systems studied here.Source: §9 · p. 39
• A unified theory is still missing because each nonconvex problem requires delicate, problem-specific analysis, although incoherence regions and leave-one-out stability may be building blocks.The authors contrast this situation with overarching structural ideas such as sparsity and incoherence in compressed sensing.Source: §9 · pp. 39–40

A Proofs for phase retrieval

• The phase-retrieval proofs begin by invoking concentration inequalities and union bounds to establish high-probability properties of the sampling vectors.Additional Gaussian concentration yields another stated high-probability bound for the relevant quantities.Source: A Proofs for phase retrieval · p. 48

A.1 Proof of Lemma 1

• Lemma 1 establishes the phase-retrieval Hessian’s smoothness by decomposing it into three terms and bounding their combined norm by O(log n).The final bound is at most 5C2(10 + C2) log n for sufficiently large n.Source: §A.1 · p. 48
• Lemma 1 also proves a local strong-convexity lower bound by controlling the remaining Hessian components under suitable sampling and parameter conditions.The proof combines bounds on Λ4 and Λ5, with conditions including sufficiently large m/(n log n) and m/n.Source: §A.1 · p. 49

A.2 Proof of Lemma 2

• Lemma 2 applies the Hessian bounds along the segment from x⋆ to x_t to obtain a gradient-descent contraction when η ≤ 1/[5C2(10 + C2) log n].Along the segment, the Hessian satisfies (1/2)·I_n ⪯ ∇2f(x(τ)) ⪯ [5C2(10 + C2) log n]·I_n.Source: §A.2 · p. 50

A.3 Proof of Lemma 3

• Lemma 3 recursively propagates the contraction and local conditions through all iterations, including the regime after the initial time T0, for η ≍ 1/log n.The proof repeatedly invokes Lemma 2 and uses Cauchy–Schwarz to maintain the required conditions.Source: §A.3 · p. 50

A.4 Proof of Lemma 4

• Lemma 4 extends the induction to leave-one-out iterates by decomposing gradient differences and preserving positive-definite, almost well-conditioned Hessians.The step size again satisfies 0 < η ≤ 1/[5C2(10 + C2) log n], and the induction is established for the next iteration.Source: §A.4 · pp. 51–52

A.5 Proof of Lemma 5

• Lemma 5 controls spectral initialization using Davis–Kahan and Weyl perturbation bounds around E[Y] = I + 2x⋆x⋆⊤, whose eigenvalues are 3 and 1.The spectral gap is 2, and |λ1(Y) − 3| ≤ δ implies λ1(Y) ≥ 3 − δ > 0 when δ ≤ 1.Source: §A.5 · p. 52

A.6 Proof of Lemma 6

• Lemma 6 transfers the spectral initialization bounds to leave-one-out versions with probability at least 1 − O(mn^-10) when m ≫ n log n.Weyl’s inequality places λ1(Y) and related quantities in [2, 4].Source: §A.6 · pp. 52–53

B.1 Proof of Lemma 7

• For matrix completion, Lemma 7 combines Hessian decompositions, incoherence, and tangent-space injectivity to obtain a uniform bound over admissible X, even when X depends statistically on Ω.The collective estimate is uniform over all V, while the proof requires sampling conditions such as n2p/(µnr log n) sufficiently large.Source: §B.1 · pp. 54–56, §5 · p. 56

B.2 Proof of Lemma 8

• Under the sample-size, noise, and step-size conditions, the proof completes Frobenius-norm contraction with contraction factor ρ<1.The argument combines bounds on the two decomposed terms and requires 1−(σ_min/4)·η≤ρ<1.Source: §B.2 · p. 58

B.3 Proof of Lemma 9

• The proof of Lemma 9 controls population, perturbation, and noise components, using incoherence and sample-size conditions to show the auxiliary iterate remains close to the truth.It also rotates the auxiliary iterate toward the direction aligned with X⋆ and combines the resulting bounds to obtain contraction with ρ≥1−(σ_min/3)·η.Source: §B.3 · pp. 62–63

B.3.1 Proof of Lemma 22

• Lemma 22 obtains a uniform high-probability concentration bound by first analyzing fixed ∆t, applying matrix Bernstein and an epsilon-net argument, then extending the result to symmetric sampling by decoupling.The independent-indicator argument achieves probability at least 1−C0e^(−Cnr log n), while diagonal effects are negligible under the incoherence and sample-size conditions.Source: §B.3.1 · p. 64

B.3.2 Proof of Lemma 23

• The argument upper-bounds φ2 with probability at least 1 − O(n−10), when (144) holds for all l’s, using indicators specified by ||G_l(Δ^t)||.It then divides into multiple cases based on ||G_l(Δ^t)||; by Lemma 42, this holds with probability at least 1 − c1 exp(−c2nr log n) for constants c1, c2 > 0.Source: §B.3.2 · p. 65
• For any k ≥ 0 and α ≳ log n, the proof restricts attention to sufficiently large k; otherwise, bound (140) contradicts the event ∥Al,·∥2 ≥ω, so all indices are divided into sets.Source: §B.3.2 · p. 65
• The cardinality of S_k decays exponentially in k, and only O(log n) such sets are nonempty for sufficiently large k.These properties enable summing the bounds over all strata.Source: §B.3.2 · p. 66
• The resulting Lemma 23 bound uses the incoherence condition (114) and concludes by setting α = c log n for a sufficiently large constant c.The displayed final expression includes ακµr^2p log n ||X⋆||_2.Source: §B.3.2 · p. 66

B.4 Proof of Lemma 10

• B.4 derives (73a) by applying Lemma 37 to X_t^c H_t and X_t,(l)R_t,(l), under sample-complexity and noise conditions.The required conditions include n^2p ≫ κ^2µ^2r^2n, n^2p ≫ κ^2µ^2r^2n log n, and noise condition (27).Source: §B.4 · pp. 66–67
• The proof of (73b) combines its definition with (70a), (70d), and the triangle inequality to control the Frobenius-norm estimation error.The final step requires n ≫ κµ log n.Source: §B.4 · p. 67
• For (73c) and (73d), B.4 uses (70b) and (70d), triangle inequalities, (73a), and incoherence of X⋆ to obtain the stated bounds.The last inequality for (73d) holds as long as n ≫ κ^3µr log n.Source: §B.4 · p. 67

B.5 Proof of Lemma 11

• The proof controls four terms in reverse order, bounds them individually, and applies the triangle inequality; under the stated sample-complexity assumption and step-size condition, this finishes the proof.The sample-complexity assumption is n2p ≫ κ4µ2r2n log n, with 0 < η ≤ 1/(2σmax) ≤1/(2σmin) and C7 > 0 sufficiently large.Source: §B.5 · pp. 68–70

B.5.1 Proof of Lemma 24

• Lemma 24 controls the fourth term by decoupling the sampled row and column, treating one component as independent vector sums, and applying matrix Bernstein concentration.Its conclusion uses n^2p ≫ μ^2r^2n log n together with (73c) and the noise condition (27).Source: §B.5.1 · p. 70

B.5.2 Proof of Lemma 25

• Lemma 25 bounds the second term using separate row/column control, matrix Bernstein concentration, and the incoherence condition.The argument invokes the sample complexity condition n^2p ≫ μ^2r^2n log n and requires np ≫ log n.Source: §B.5.2 · pp. 71–72

B.6 Proof of Lemma 12

• The proof of Lemma 12 introduces an auxiliary matrix, applies the triangle inequality, and bounds its two components α_1 and α_2 separately.For α_2, the contraction follows from 0 < η ≤ 1/σ_max and the lower spectral bound σ_min.Source: §B.6 · pp. 72–73
• The α_1 analysis controls β_1 and β_2 through auxiliary matrix estimates, symmetry, Lemma 36, incoherence, and the sample-size condition.The preceding estimates are combined in (171) and (175) to obtain the stated bound for α_1.Source: §B.6 · pp. 73–75

3. Combine (160), (164) and (176) to reach

• The final combination of (160), (164), and (176) yields the desired contraction inequality under the sample-size and noise conditions.The contraction factor satisfies 1 − (σ_min/3)·η ≤ ρ < 1, with additional requirements C_2 ≫ κC_9 and C_6 ≫ κC_10/√log n.Source: §3 · p. 76

B.7 Proof of Lemma 13

• The proof controls the alignment matrices using the orthogonal Procrustes solution and sign-matrix perturbation bounds for singular-vector and eigenvector comparisons.It invokes Davis–Kahan and prior component-wise estimates to establish the leave-one-out-related claim and the final alignment bound.Source: §B.7 · pp. 76, 79, 80
• The Lemma 13 conclusions rely on incoherence, sample complexity, noise control, and a bounded condition number to convert perturbation estimates into the advertised inequalities.The proof explicitly uses σmax/σmin ≲1 or ≍1 together with bounds involving σmin, σmax, and ∥X⋆∥F.Source: §B.7 · pp. 76, 77, 79
• Lemma 13 derives the required factor and subspace error bounds from a key decomposition, perturbation estimates, Weyl’s inequality, and triangle-inequality arguments.The proof separately treats spectral, Frobenius, component-wise, alignment, and initialization-related bounds under incoherence, sample-complexity, noise, and bounded-condition-number assumptions.Source: §B.7 · pp. 76–77

C Proofs for blind deconvolution

• The blind-deconvolution proofs begin with Gaussian concentration and auxiliary high-probability bounds, then identify the population Wirtinger Hessian at the truth.These concentration results provide the probabilistic groundwork for the subsequent Hessian analysis.Source: C Proofs for blind deconvolution · p. 80

C.1 Proof of Lemma 14

• Lemma 14 is proved by decomposing the empirical Wirtinger Hessian into its population value and a perturbation, then controlling each component separately.The population term is shown to satisfy the advertised restricted strong-convexity and smoothness properties, while the empirical perturbation is bounded under the stated assumptions.Source: §C.1 · p. 80
• Combining the population and perturbation lemmas verifies both the smoothness upper bound and the restricted strong-convexity lower bound for z ∈ S.The final inequalities are obtained through the two lemmas, triangle inequality, the perturbation estimate, and the constraint on δ.Source: §C.1 · p. 81
• Under m ≫µ^2K log^9 m and δ = c/log^2 m, Lemma 27 supplies the perturbation control needed for the Hessian bounds with high probability.The argument also uses ∥D∥≤1+δ and δ≤1/2 when establishing restricted strong convexity.Source: §C.1 · p. 81

• Combining these estimates with γ1 + γ2 ≤ 2(1 + δ) ≤ 3 for δ < 1/2 yields the lemma’s final bound when δ is sufficiently small.Source: §C.1.1 · pp. 82–83
• The argument reduces restricted strong convexity to bounding β, which is decomposed into four terms, with β1 isolated as the remaining principal term.The decomposition explicitly identifies β1 and treats β2, β3, and β4 as perturbative terms.Source: §C.1.1 · pp. 82–83
• Local closeness implies |β2| + |β3| + |β4| ≤ 5δ∥h1 − h2∥2∥x1 − x2∥2 ≤ 5δ∥h1 − h2∥2.The bounds use δ < 1 and the estimates ∥x2∥2, ∥h2∥2 ≤ 2.Source: §C.1.1 · p. 82
• The principal term β1 is controlled using the alignment assumption, the triangle inequality, and the local bounds ∥x1 − x2∥2 ≤ 2δ and ∥x2∥2 ≤ 2.Source: §C.1.1 · p. 83

C.1.2 Proof of Lemma 27

• The analysis controls sup_z∈S αj separately for j = 1, 2, 3, 4, including a high-probability upper bound for sup_z∈S α4.Specifically, P(sup_z∈S α4 ≤ 1/48) = 1 − O(m−10 + e−K log m).Source: §C.1.2 · pp. 83, 89

C.2 Proofs of Lemma 15 and Lemma 16

• Lemmas 15 and 16 rewrite the gradient updates through the fundamental theorem of calculus and Hessian control, then prove the required iterate bounds by induction.The induction uses the assumption ||α_t|−1| ≤ 1/2 and propagates dist(z_s,z⋆) ≤ C1(1−η/16)^s/log2 m for the stated range of iterations.Source: §C.2 · pp. 90–91

C.3 Proof of Lemma 17

• Lemma 17 compares aligned leave-one-out and actual iterates by decomposing their update discrepancy into three terms ν1, ν2, and ν3.The ν1 analysis repeats the Appendix C.2 Hessian argument under induction hypotheses, while the Hessian bound in Lemma 14 controls ν2 through gradient Lipschitzness.Source: §C.3 · pp. 91, 92, 94
• The proof of Lemma 17 combines bounds for the constituent error terms and invokes closeness to (h⋆, x⋆) through Lemma 55 to establish the lemma’s second inequality.The estimates rely on induction hypotheses and sufficiently large m conditions ensuring the error terms remain controlled.Source: §C.3 · pp. 94–95

C.4 Proof of Lemma 18

• The proof of Lemma 18 decomposes the gradient update into separate terms and controls each using induction hypotheses, incoherence, auxiliary lemmas, and binning adjacent vectors.The argument requires sufficiently large m, sufficiently small constants such as C3 and c, and a bin size τ satisfying logarithmic lower bounds.Source: §C.4 · pp. 96–97, §3 · p. 99

C.4.1 Proof of Lemma 28

• Lemma 28 bounds the relevant sum by representing it as independent random variables and applying sub-exponential concentration under incoherence, provided m ≫ K log^2 m.The proof uses sub-exponential norm relationships and takes t = µ/√m in the concentration bound.Source: §C.4 · p. 97, §C.4.1 · pp. 100–101

3. Finally, we need to control

• The final control of the third update term combines binwise bounds from Lemma 29, Cauchy–Schwarz, and Lemma 51, under conditions such as m ≫ τK log m.The proof then combines all three term estimates and chooses sufficiently small constants and a sufficiently large sample size to close the induction.Source: §3 · pp. 98–100

C.4.2 Proof of Lemma 29

• Lemma 29 controls Pτ by exploiting independent complex Gaussian variables and hypercontractivity for Gaussian polynomials when τ ≫ log^4 m.The resulting probability bound is at least 1 − O(m^-10).Source: §C.4.2 · p. 101

C.4.3 Proof of Claim (224)

• Claim (224) is proved by induction, with the induction step using the gradient update, incoherence, and the hypothesis from (85c).The argument repeatedly applies the update rule and invokes the induction hypothesis to control the relevant terms.Source: §C.4.3 · pp. 101, 103
• The induction argument relies on incoherence and the fact that x̃_{t−1} and x⋆ are extremely close, which yields ||x̃_{t−1}||_2 ≤ 2.The bound is stated after using the incoherence condition (36) and the closeness assumption.Source: §C.4.3 · p. 102
• Claim (224) holds under the sample-size condition m ≫ τK log^4 m and sufficiently small positive η, with the base case required to complete the induction.The proof explicitly states the large-m condition and concludes once the base case is verified.Source: §C.4.3 · pp. 102–103

C.5 Proof of Lemma 19

• Lemma 19 begins by applying a variant of Wedin’s sinΘ theorem [Dop00, Theorem 2.1] to the leading singular vectors of M.The proof then bounds the perturbation using ||M − E[M]|| ≤ ξ and the spectral gap of E[M].Source: §C.5 · p. 103
• Weyl’s inequality gives σ1(E[M]) − σ2(M) ≥ 1 − ξ because σ1(E[M]) = 1 and σ2(E[M]) = 0.This establishes the denominator control needed for the singular-vector perturbation bound.Source: §C.5 · p. 103
• The singular-vector perturbation argument establishes (92) when ξ ≤ 1/2 and, by similar omitted arguments, also establishes (93).The proof then takes m/(µ^2K log^2 m) sufficiently large while allowing ξ to be arbitrary.Source: §C.5 · pp. 103–104
• The final claim | |α0| − 1 | ≤ 1/4 follows directly from (92) together with Lemma 52.This closes the proof of the last assertion in Lemma 19.Source: §C.5 · p. 104

C.6 Proof of Lemma 20

• Lemma 20 is proved in three stages: normalized singular-vector proximity, transfer to scaled vectors, and conversion to the paper’s distance metric, while also establishing h0’s incoherence.The argument uses Wedin’s sinΘ theorem and Weyl’s inequality, under sample-size conditions such as m ≥ c2µ2K log2 m.Source: §C.6 · p. 104
• The proof’s byproduct establishes the additional claim required in (226) when m ≫ τK log4 m with high probability.This lemma reuses the preceding incoherence and singular-vector bounds rather than introducing a separate argument.Source: §C.6 · p. 108

C.7 Proof of Lemma 21

• Lemma 21 combines alignment, triangle-inequality, Cauchy–Schwarz, and independence arguments to obtain its high-probability bound under m ≫ µ2K log6 m and m ≫ µ2K log4 m.The proof explicitly transfers the distance estimate from Lemma 20 and controls terms involving x0,(l) and al.Source: §C.7 · pp. 108–109

D.1.1 Matrix concentration inequalities

• The matrix-concentration lemmas provide Gaussian-design spectral and quadratic-form controls with exponentially or polynomially high probability when m is at least proportional to n or n log n.The stated conditions include m ≥ c0n and m ≥ c0n log n for sufficiently large constants.Source: §D.1.1 · p. 110

D.1.2 Matrix perturbation bounds

• The matrix-perturbation lemma bounds changes in leading eigenvectors and eigenvalues when both matrices have leading eigenvalues and operator norms bounded within [C1,C2].Its derivation combines the eigenvalue–eigenvector relationship with the identity for differences of square roots.Source: §D.1.2 · pp. 110–111

D.2.1 Orthogonal Procrustes problem

• The orthogonal Procrustes minimizer is characterized by R̂⊤A⊤B being symmetric positive semidefinite and equals UV⊤ when A⊤B = UΣV⊤.When A⊤B is invertible, this characterization motivates perturbation analysis of the associated matrix-valued polar factor.Source: §D.2.1 · p. 111
• For nonsingular C and perturbation E with ∥E∥ ≤ σmin(C), the polar-factor perturbation obeys a bound in every unitarily invariant norm.This result is then applied to compare the alignment matrices associated with X1, X2, and X⋆.Source: §D.2.1 · p. 112
• 5κ: after Procrustes alignment, both ∥X1R1 − X2R2∥ ≤ 5κ∥X1 − X2∥ and its Frobenius analogue hold.The proof establishes invertibility and closed-form alignment expressions before applying the polar-factor perturbation bound.Source: §D.2.1 · pp. 112–113

D.2.2 Matrix concentration inequalities

• Bernoulli sampling concentration controls tangent-space matrices, noise matrices, and auxiliary sampling operators under stated sample-size and incoherence conditions.The results extend established asymmetric-sampling arguments to symmetric patterns, including [CR09, Section 4.2], [KMO10a, Lemma 3.2], and [CW15, Lemma 11].Source: §D.2.2 · pp. 113, 115

1. Introduce the auxiliary function

• The auxiliary-function proof combines continuity, epsilon-net covering, union bounds, and Talagrand concentration to extend fixed-matrix bounds uniformly over feasible perturbations.The epsilon-net has log-cardinality bounded by nr log n, while continuity extends the bound beyond the net; see [Tao12, Section 2.3.1] and [CC18, Proposition 1].Source: §D.2.2 · p. 115, §1 · pp. 116–117

3. Taken together, the preceding bounds (264), (268) and (273) yield

• Sparse Bernoulli matrices with at most k_r and k_c nonzeros per row and column satisfy the spectral-norm bound ∥A∥ ≤ √(k_ck_r).This follows from induced 1- and infinity-norm control, using [Hig92, equation (1.11)].Source: §3 · p. 119

D.2.3 Matrix perturbation bounds

• Matrix perturbation lemmas bound eigenspace changes when perturbations are at most σ_min/2 or σ_min/4, using [AFWZ17, Lemma 3] and the Davis-Kahan sinΘ theorem [DK70].A second lemma treats two perturbed symmetric matrices under bounded condition number and provides Frobenius and operator-norm control.Source: §D.2.3 · pp. 119–120
• Under ∥M − M⋆∥ ≤ σmin/2 and bounded σmax/σmin, the matrix perturbation lemma controls the eigenspace-factor perturbation.The proof uses Weyl’s inequality, matrix square-root perturbation bounds [Sch92, Lemma 2.1], and unitary invariance.Source: §D.2.3 · pp. 121–122

D.3.1 Wirtinger calculus

• Wirtinger calculus yields the fundamental theorem of calculus and the mean-value form of Taylor’s theorem for real-valued functions on C^n.The complex derivatives are related to conventional derivatives through the identification z = x + iy.Source: §D.3.1 · pp. 122–123

D.3.2 Discrete Fourier transform matrices

• For DFT matrices, the stated uniform estimates imply bounds of c log2 m and c/√τ under m ≥ CτK log4 m and m ≥ CτK log m, respectively.These consequences are established for constants independent of m and K, with the first requiring 0 ≤ l − 1 ≤ τ.Source: §D.3.2 · pp. 125–126

D.3.3 Complex-valued alignment

• The complex-valued alignment minimizer remains near β when (h, x) is sufficiently close to (h⋆, x⋆), while the alignment objective is locally strongly convex and locally Lipschitz in the vectors.Lemma 52 assumes 1/2 ≤ |β| ≤ 3/2 and δ ≤ 1/4, and the minimizer cannot lie beyond 18δ from β.Source: §D.3.3 · pp. 127–129
• When vector pairs are within δ ≤ 1/4 of the optimizer, their alignment parameters are controlled and aligned distance is bounded by unaligned distance.The analysis shows 1/2 ≤ |α1|, |α2| ≤ 2 and |α1 − α2| ≲ ∥x1 − x2∥2 + ∥h1 − h2∥2.Source: §D.3.3 · p. 130

D.3.4 Matrix concentration inequalities

• The concentration lemmas control random matrices and subsets through Bernstein-type arguments, including a result under m ≫ K log^3 m with probability exceeding 1 − O(…).The proofs use scalar and matrix Bernstein inequalities, sub-exponential norm and variance bounds, and a union bound.Source: §D.3.4 · pp. 131–133

D.3.5 Matrix perturbation bounds

• A perturbation lemma bounds changes in the leading singular value and corresponding left and right singular vectors when both leading singular values are nonzero.The proof derives the singular-vector bounds by combining separate inequalities for the left and right vectors.Source: §D.3.5 · pp. 133–134