Uniform bound on the sampling and regularizer terms of (Chen–Li Lemma 4.8, exact case)
DisprovedMatrixCompletion.NoSpuriousMin.perturbation_terms_boundIn 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.
import Definitions.Def_MCNoSpuriousMinModel import Mathlib.LinearAlgebra.Matrix.PosDef open Matrix MatrixCompletion.NoSpuriousMin
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 sorryRead-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; denotes the Euclidean norm of a vector, the entrywise (Frobenius) inner product, the Frobenius norm, and its square. For a finite set of index pairs, is the matrix that agrees with on entries and is elsewhere. The following bundle-specific quantities appear (each unfolded from its definition in the file):
- is the supremum, taken in , of over the set of vectors with (as a real-valued supremum, it takes a default junk value of if this family is empty or unbounded above); is the corresponding infimum (junk value if empty or unbounded below).
- is the supremum in of the Euclidean norms of the rows of .
- , where is the matrix with entry at positions in and elsewhere, and is the all-ones matrix.
- (note the first term equals ).
- For a matrix with rows , the regularizer's gradient is the matrix with entries , and its Hessian quadratic form at direction is
where in both formulas division by yields the junk value (so any row with contributes ).
- , where the inverse is the total matrix inverse that returns the zero matrix when is not invertible (in which case ).
The theorem asserts: for every pair of natural numbers with and ; every three real matrices ; every finite set of pairs of indices in ; and every five real numbers satisfying all of the following hypotheses:
- and ;
- , and ;
- incoherence: every row of satisfies ;
- normalization: exactly;
- ;
- ;
- sample-size condition: and (here is the natural logarithm of viewed as a real number);
- good sample (a conjunction of four conditions on ):
- is symmetric: for all ;
- for every row index , the number of pairs in whose first coordinate is is at most ;
- ;
- for all symmetric matrices satisfying and , one has ;
- ;
- the matrix is positive semidefinite in the sense that it is symmetric and for every ;
then, writing , the inequality
holds, where the first squared norm on the right is of the matrix and the second is of the matrix . The inequality is non-strict ().
Points the quantifiers silently include: nothing in the statement requires to be nonempty, to be positive on its own (positivity follows only if the left side of hypothesis 7 is positive, which holds since , , give ), or to be nonzero — rows of with zero norm enter and through the division-by-zero convention above. The hypotheses and jointly force and constrain to a nonnegative window; if they force . The theorem claims nothing about existence of such : if the combined hypotheses were unsatisfiable for some , the statement would hold vacuously there.
Confirmed by the mission captain (proposal self-audit).