Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniform bound on the sampling and regularizer terms of KKK (Chen–Li Lemma 4.8, exact case)

Disproved
MatrixCompletion.NoSpuriousMin.perturbation_terms_bound

by Shuze Chen · Aug 4, 2026 · Mathlib c5ea003 (Lean v4.30.0)

matrix-completionmc-no-spuriousnonconvex-optimization

In the setting of the goal theorem — incoherent ZZZ, tuning windows α∈[100,200]⋅νr\alpha\in[100,200]\cdot\sqrt{\nu_r}α∈[100,200]⋅νr​​ (where νr=∥ZZ⊤∥ℓ∞\nu_r=\|ZZ^\top\|_{\ell_\infty}νr​=∥ZZ⊤∥ℓ∞​​, so νr=∥Z∥2→∞\sqrt{\nu_r}=\|Z\|_{2\to\infty}νr​​=∥Z∥2→∞​) and λ∈[100,200]⋅∥Ω−pJ∥\lambda\in[100,200]\cdot\|\Omega-pJ\|λ∈[100,200]⋅∥Ω−pJ∥, sampling rate in the regime of Corollary 2.2, and a good sample Ω\OmegaΩ — the sampling-deviation and regularizer parts of the decomposition of KKK are uniformly small along every aligned direction Δ=X−U\Delta=X-UΔ=X−U:

DΩ,p(ΔΔ⊤,ΔΔ⊤)−3DΩ,p(XX⊤−UU⊤,XX⊤−UU⊤)+λ(⟨Δ,∇2R(X)[Δ]⟩−4⟨∇R(X),Δ⟩)D_{\Omega,p}(\Delta\Delta^\top,\Delta\Delta^\top)-3D_{\Omega,p}(XX^\top-UU^\top,XX^\top-UU^\top)+\lambda\Bigl(\langle\Delta,\nabla^2R(X)[\Delta]\rangle-4\langle\nabla R(X),\Delta\rangle\Bigr)DΩ,p​(ΔΔ⊤,ΔΔ⊤)−3DΩ,p​(XX⊤−UU⊤,XX⊤−UU⊤)+λ(⟨Δ,∇2R(X)[Δ]⟩−4⟨∇R(X),Δ⟩) ≤ p1000(∥Δ⊤Δ∥F2+∥UΔ⊤∥F2).\le\ \frac{p}{1000}\Bigl(\|\Delta^\top\Delta\|_F^2+\|U\Delta^\top\|_F^2\Bigr).≤ 1000p​(∥Δ⊤Δ∥F2​+∥UΔ⊤∥F2​).

This is where the regularizer earns its keep: rows of XXX larger than α\alphaα are penalized strongly enough that the deviation terms they create are absorbed, while small rows are handled by the deterministic master bound with the spectral and tangent-space good-sample fields. This is the only milestone whose proof consumes the good-sample hypotheses.

Preamble
import Definitions.Def_MCNoSpuriousMinModel
import Mathlib.LinearAlgebra.Matrix.PosDef
open Matrix MatrixCompletion.NoSpuriousMin
Formal statement
theorem MatrixCompletion.NoSpuriousMin.perturbation_terms_bound
    {d r : ℕ} (hd : 2 ≤ d) (hr : 1 ≤ r)
    (Z X U : Matrix (Fin d) (Fin r) ℝ) (Ω : Finset (Fin d × Fin d))
    (p μ κ lam α : ℝ)
    (hμ : 1 ≤ μ) (hκ : 1 ≤ κ) (hcond : sigmaMax Z ≤ κ * sigmaMin Z)
    (hσ : 0 < sigmaMin Z)
    (hinc : Incoherent μ Z) (hZnorm : frobSq Z = (r : ℝ))
    (hα1 : 100 * twoInftyNorm Z ≤ α) (hα2 : α ≤ 200 * twoInftyNorm Z)
    (hlam1 : 100 * sampDevNorm Ω p ≤ lam) (hlam2 : lam ≤ 200 * sampDevNorm Ω p)
    (hp : SampleCondition d r p μ κ)
    (hgood : GoodSample Z Ω p)
    (hU : U * Uᵀ = Z * Zᵀ) (hpsd : (Xᵀ * U).PosSemidef) :
    sampDev Ω p ((X - U) * (X - U)ᵀ) ((X - U) * (X - U)ᵀ)
        - 3 * sampDev Ω p (X * Xᵀ - U * Uᵀ) (X * Xᵀ - U * Uᵀ)
        + lam * (regHessQF α X (X - U) - 4 * innerM (regGrad α X) (X - U)) ≤
      p / 1000 * (frobSq ((X - U)ᵀ * (X - U)) + frobSq (U * (X - U)ᵀ)) := by sorry
Source
Chen, Li 2019, Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA, JMLR 20(142), https://arxiv.org/abs/1711.01742 (v3) [THE canonical reference: all milestones follow its Section 4], p. 19, Lemma 4.8, eq. (4.7), specialized to exact rank r (residual N = 0; bracket terms vanish under the sampling condition of Corollary 2.2). Consumes the good-sample facts (Chen-Li Lemmas 4.1-4.2) through Lemma 4.4.
Read-back

What the Lean code literally says, in plain math · claude-fable-5

Read-back: MatrixCompletion.NoSpuriousMin.perturbation_terms_bound

Throughout, "matrix" means a real matrix with rows and columns indexed by finite index sets of the stated sizes; ∥v∥=∑jvj2\|v\| = \sqrt{\sum_j v_j^2}∥v∥=∑j​vj2​​ denotes the Euclidean norm of a vector, ⟨A,B⟩=∑i,jAijBij\langle A, B\rangle = \sum_{i,j} A_{ij}B_{ij}⟨A,B⟩=∑i,j​Aij​Bij​ the entrywise (Frobenius) inner product, ∥A∥F=∑i,jAij2\|A\|_F = \sqrt{\sum_{i,j} A_{ij}^2}∥A∥F​=∑i,j​Aij2​​ the Frobenius norm, and ∥A∥F2=∑i,jAij2\|A\|_F^2 = \sum_{i,j} A_{ij}^2∥A∥F2​=∑i,j​Aij2​ its square. For a finite set Ω\OmegaΩ of index pairs, PΩ(A)\mathcal{P}_\Omega(A)PΩ​(A) is the matrix that agrees with AAA on entries (i,j)∈Ω(i,j) \in \Omega(i,j)∈Ω and is 000 elsewhere. The following bundle-specific quantities appear (each unfolded from its definition in the file):

  • σmax⁡(A)\sigma_{\max}(A)σmax​(A) is the supremum, taken in R\mathbb{R}R, of ∥Av∥\|Av\|∥Av∥ over the set of vectors vvv with ∥v∥=1\|v\| = 1∥v∥=1 (as a real-valued supremum, it takes a default junk value of 000 if this family is empty or unbounded above); σmin⁡(A)\sigma_{\min}(A)σmin​(A) is the corresponding infimum (junk value 000 if empty or unbounded below).
  • ∥A∥2,∞\|A\|_{2,\infty}∥A∥2,∞​ is the supremum in R\mathbb{R}R of the Euclidean norms of the rows of AAA.
  • DΩ(p)=σmax⁡ ⁣(1Ω−p J)D_\Omega(p) = \sigma_{\max}\!\big(\mathbf{1}_\Omega - p\,J\big)DΩ​(p)=σmax​(1Ω​−pJ), where 1Ω\mathbf{1}_\Omega1Ω​ is the d×dd\times dd×d matrix with entry 111 at positions in Ω\OmegaΩ and 000 elsewhere, and JJJ is the all-ones d×dd\times dd×d matrix.
  • SΩp(A,B)=⟨PΩA,PΩB⟩−p ⟨A,B⟩S_\Omega^p(A,B) = \langle \mathcal{P}_\Omega A, \mathcal{P}_\Omega B\rangle - p\,\langle A, B\rangleSΩp​(A,B)=⟨PΩ​A,PΩ​B⟩−p⟨A,B⟩ (note the first term equals ∑(i,j)∈ΩAijBij\sum_{(i,j)\in\Omega} A_{ij}B_{ij}∑(i,j)∈Ω​Aij​Bij​).
  • For a d×rd\times rd×r matrix XXX with rows XiX_iXi​, the regularizer's gradient is the d×rd\times rd×r matrix Gα(X)G_\alpha(X)Gα​(X) with entries Gα(X)ij=4 max⁡(∥Xi∥−α, 0)3∥Xi∥ XijG_\alpha(X)_{ij} = \dfrac{4\,\max(\|X_i\|-\alpha,\,0)^3}{\|X_i\|}\,X_{ij}Gα​(X)ij​=∥Xi​∥4max(∥Xi​∥−α,0)3​Xij​, and its Hessian quadratic form at direction VVV is
Hα(X,V)=∑i=1d[ 12 max⁡(∥Xi∥−α,0)2(⟨Xi,Vi⟩∥Xi∥) ⁣2+4 max⁡(∥Xi∥−α,0)3∥Xi∥(∥Vi∥2−(⟨Xi,Vi⟩∥Xi∥) ⁣2)],H_\alpha(X,V) = \sum_{i=1}^{d}\left[\,12\,\max(\|X_i\|-\alpha,0)^2\left(\frac{\langle X_i,V_i\rangle}{\|X_i\|}\right)^{\!2} + \frac{4\,\max(\|X_i\|-\alpha,0)^3}{\|X_i\|}\left(\|V_i\|^2-\left(\frac{\langle X_i,V_i\rangle}{\|X_i\|}\right)^{\!2}\right)\right],Hα​(X,V)=i=1∑d​[12max(∥Xi​∥−α,0)2(∥Xi​∥⟨Xi​,Vi​⟩​)2+∥Xi​∥4max(∥Xi​∥−α,0)3​(∥Vi​∥2−(∥Xi​∥⟨Xi​,Vi​⟩​)2)],

where in both formulas division by ∥Xi∥=0\|X_i\| = 0∥Xi​∥=0 yields the junk value 000 (so any row with ∥Xi∥=0\|X_i\| = 0∥Xi​∥=0 contributes 000).

  • PZ=Z(ZTZ)−1ZTP_Z = Z(Z^{\mathsf T}Z)^{-1}Z^{\mathsf T}PZ​=Z(ZTZ)−1ZT, where the inverse is the total matrix inverse that returns the zero matrix when ZTZZ^{\mathsf T}ZZTZ is not invertible (in which case PZ=0P_Z = 0PZ​=0).

The theorem asserts: for every pair of natural numbers d,rd, rd,r with d≥2d \ge 2d≥2 and r≥1r \ge 1r≥1; every three d×rd\times rd×r real matrices Z,X,UZ, X, UZ,X,U; every finite set Ω\OmegaΩ of pairs of indices in {1,…,d}×{1,…,d}\{1,\dots,d\}\times\{1,\dots,d\}{1,…,d}×{1,…,d}; and every five real numbers p,μ,κ,λ,αp, \mu, \kappa, \lambda, \alphap,μ,κ,λ,α satisfying all of the following hypotheses:

  1. μ≥1\mu \ge 1μ≥1 and κ≥1\kappa \ge 1κ≥1;
  2. σmax⁡(Z)≤κ σmin⁡(Z)\sigma_{\max}(Z) \le \kappa\,\sigma_{\min}(Z)σmax​(Z)≤κσmin​(Z), and σmin⁡(Z)>0\sigma_{\min}(Z) > 0σmin​(Z)>0;
  3. incoherence: every row of ZZZ satisfies ∥Zi∥≤μd ∥Z∥F\|Z_i\| \le \dfrac{\mu}{\sqrt d}\,\|Z\|_F∥Zi​∥≤d​μ​∥Z∥F​;
  4. normalization: ∥Z∥F2=r\|Z\|_F^2 = r∥Z∥F2​=r exactly;
  5. 100 ∥Z∥2,∞≤α≤200 ∥Z∥2,∞100\,\|Z\|_{2,\infty} \le \alpha \le 200\,\|Z\|_{2,\infty}100∥Z∥2,∞​≤α≤200∥Z∥2,∞​;
  6. 100 DΩ(p)≤λ≤200 DΩ(p)100\,D_\Omega(p) \le \lambda \le 200\,D_\Omega(p)100DΩ​(p)≤λ≤200DΩ​(p);
  7. sample-size condition: 1010 μ4 κ4 r2 log⁡dd≤p10^{10}\,\mu^4\,\kappa^4\,r^2\,\dfrac{\log d}{d} \le p1010μ4κ4r2dlogd​≤p and p≤1p \le 1p≤1 (here log⁡\loglog is the natural logarithm of ddd viewed as a real number);
  8. good sample (a conjunction of four conditions on Ω\OmegaΩ):
    • Ω\OmegaΩ is symmetric: (i,j)∈Ω  ⟺  (j,i)∈Ω(i,j) \in \Omega \iff (j,i) \in \Omega(i,j)∈Ω⟺(j,i)∈Ω for all i,ji,ji,j;
    • for every row index iii, the number of pairs in Ω\OmegaΩ whose first coordinate is iii is at most 2pd2pd2pd;
    • DΩ(p)≤100(dp+log⁡d)D_\Omega(p) \le 100\big(\sqrt{dp} + \sqrt{\log d}\big)DΩ​(p)≤100(dp​+logd​);
    • for all symmetric d×dd\times dd×d matrices W,W′W, W'W,W′ satisfying (I−PZ) W (I−PZ)=0(I - P_Z)\,W\,(I - P_Z) = 0(I−PZ​)W(I−PZ​)=0 and (I−PZ) W′ (I−PZ)=0(I - P_Z)\,W'\,(I - P_Z) = 0(I−PZ​)W′(I−PZ​)=0, one has ∣SΩp(W,W′)∣≤p1000 ∥W∥F ∥W′∥F\big|S_\Omega^p(W,W')\big| \le \dfrac{p}{1000}\,\|W\|_F\,\|W'\|_F​SΩp​(W,W′)​≤1000p​∥W∥F​∥W′∥F​;
  9. UUT=ZZTU U^{\mathsf T} = Z Z^{\mathsf T}UUT=ZZT;
  10. the r×rr\times rr×r matrix XTUX^{\mathsf T}UXTU is positive semidefinite in the sense that it is symmetric and vT(XTU) v≥0v^{\mathsf T}(X^{\mathsf T}U)\,v \ge 0vT(XTU)v≥0 for every v∈Rrv \in \mathbb{R}^rv∈Rr;

then, writing E=X−UE = X - UE=X−U, the inequality

SΩp ⁣(EET, EET)  −  3 SΩp ⁣(XXT−UUT, XXT−UUT)  +  λ(Hα(X,E)−4 ⟨Gα(X), E⟩)  ≤  p1000(∥ETE∥F2+∥UET∥F2)S_\Omega^p\!\big(EE^{\mathsf T},\,EE^{\mathsf T}\big) \;-\; 3\,S_\Omega^p\!\big(XX^{\mathsf T}-UU^{\mathsf T},\,XX^{\mathsf T}-UU^{\mathsf T}\big) \;+\; \lambda\Big(H_\alpha(X,E) - 4\,\big\langle G_\alpha(X),\,E\big\rangle\Big) \;\le\; \frac{p}{1000}\Big(\big\|E^{\mathsf T}E\big\|_F^2 + \big\|U E^{\mathsf T}\big\|_F^2\Big)SΩp​(EET,EET)−3SΩp​(XXT−UUT,XXT−UUT)+λ(Hα​(X,E)−4⟨Gα​(X),E⟩)≤1000p​(​ETE​F2​+​UET​F2​)

holds, where the first squared norm on the right is of the r×rr\times rr×r matrix ETEE^{\mathsf T}EETE and the second is of the d×dd\times dd×d matrix UETU E^{\mathsf T}UET. The inequality is non-strict (≤\le≤).

Points the quantifiers silently include: nothing in the statement requires Ω\OmegaΩ to be nonempty, ppp to be positive on its own (positivity follows only if the left side of hypothesis 7 is positive, which holds since d≥2d \ge 2d≥2, r≥1r \ge 1r≥1, μ,κ≥1\mu, \kappa \ge 1μ,κ≥1 give log⁡d>0\log d > 0logd>0), or XXX to be nonzero — rows of XXX with zero norm enter GαG_\alphaGα​ and HαH_\alphaHα​ through the division-by-zero convention above. The hypotheses λ≤200 DΩ(p)\lambda \le 200\,D_\Omega(p)λ≤200DΩ​(p) and 100 DΩ(p)≤λ100\,D_\Omega(p) \le \lambda100DΩ​(p)≤λ jointly force DΩ(p)≥0D_\Omega(p) \ge 0DΩ​(p)≥0 and constrain λ\lambdaλ to a nonnegative window; if DΩ(p)=0D_\Omega(p) = 0DΩ​(p)=0 they force λ=0\lambda = 0λ=0. The theorem claims nothing about existence of such Z,X,U,Ω,p,μ,κ,λ,αZ, X, U, \Omega, p, \mu, \kappa, \lambda, \alphaZ,X,U,Ω,p,μ,κ,λ,α: if the combined hypotheses were unsatisfiable for some (d,r)(d,r)(d,r), the statement would hold vacuously there.

Human review
  • Endorsed by Community (Bot) · Aug 4, 2026

  • Endorsed by Shuze Chen · Aug 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me