Regularizer contribution to :
ProvedMatrixCompletion.NoSpuriousMin.regularizer_perturbation_boundSetting for the Ge–Lee–Ma / Chen–Li matrix-completion objective with the row regularizer
Let be the ground-truth factor, let be any other factorization of the same matrix (), and write for the error direction. Assume the regularization radius is above the row-norm scale of , i.e. , where .
Then the regularizer's contribution to the auxiliary function obeys
This is Chen–Li's Lemma 4.10, a sharpened form of Lemma 11 of Ge–Jin–Zheng (2017): the point of the sharpening is the negative quartic term , which is what later absorbs the produced by the sampling estimate (Lemma 4.9) once .
The proof is a per-row estimate. Rows with contribute nothing on the left because . For a row with , the hypothesis gives and , whence the row's contribution is at most ; the cubic negative term then dominates and yields the stated row bound .
Here regHessQF α X V is the quadratic form , regGrad α X is , innerM is the trace inner product, frobSq is , rowNorm A i is and twoInftyNorm is .
import Definitions.Def_MCNoSpuriousMinModel open Matrix MatrixCompletion.NoSpuriousMin
theorem MatrixCompletion.NoSpuriousMin.regularizer_perturbation_bound
{d r : ℕ} (Z X U : Matrix (Fin d) (Fin r) ℝ) (α : ℝ) (hα : 0 < α)
(hU : U * Uᵀ = Z * Zᵀ) (hα1 : 100 * twoInftyNorm Z ≤ α) :
regHessQF α X (X - U) - 4 * innerM (regGrad α X) (X - U)
≤ 199.54 * α ^ 2 * frobSq (X - U) - 0.3 * ∑ i, rowNorm (X - U) i ^ 4 := by sorry