Uniform bound on the sampling and regularizer terms of (Chen–Li Lemma 4.8, exact case)
DisprovedMatrixCompletion.NoSpuriousMin.perturbation_terms_boundmatrix-completionmc-no-spuriousnonconvex-optimization
In the setting of the goal theorem — incoherent , tuning windows (where , so ) and , sampling rate in the regime of Corollary 2.2, and a good sample — the sampling-deviation and regularizer parts of the decomposition of are uniformly small along every aligned direction :
This is where the regularizer earns its keep: rows of larger than 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 sorrySource
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.