Negative-definite quadratic bound on : (Chen–Li eq. (4.14), exact case)
DisprovedMatrixCompletion.NoSpuriousMin.K_superlevel_boundIn the setting of the goal theorem, along every aligned direction (with , ), writing and :
The quadratic form on the right is negative definite (), so it is with equality only at . Combined with at any local minimum, this forces , i.e. — the entire landscape argument in one inequality. The proof combines the decomposition of , the perturbation bound, the expansion , and the trace inequalities and furnished by the alignment.
import Definitions.Def_MCNoSpuriousMinModel import Mathlib.LinearAlgebra.Matrix.PosDef open Matrix MatrixCompletion.NoSpuriousMin
theorem MatrixCompletion.NoSpuriousMin.K_superlevel_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) :
Kfun Z Ω lam α X U ≤
p * (-(1999 / 1000) * frobSq ((X - U)ᵀ * (X - U))
+ (6001 / 1000) * frobNorm ((X - U)ᵀ * (X - U)) * frobNorm ((X - U)ᵀ * U)
- 6 * frobSq ((X - U)ᵀ * U)) := by sorryRead-back
What the Lean code literally says, in plain math · claude-fable-5
Read-back of MatrixCompletion.NoSpuriousMin.K_superlevel_bound
Fix natural numbers with and ; real matrices ; a finite set of index pairs ; and real numbers . Throughout, the following custom notions are used, and every sum/supremum is over the finite index ranges or :
- (Euclidean norm of a vector); ; and .
- denotes the -th row of , and (a maximum, since ).
- and , taken as real-valued supremum/infimum over the set of exactly-unit vectors. (These are Lean's real-number : if the indexing set were empty or the family unbounded they would take the junk value ; here unit vectors exist since and .)
- is the matrix equal to on entries in and elsewhere; is the indicator matrix of .
- where is the all-ones matrix.
- .
- , where is Lean's total matrix inverse, equal to the zero matrix when is not invertible.
- The regularizer's Hessian-type quadratic form: writing and ,
and the regularizer gradient has entries . In both, division by yields by Lean's convention, so rows of that are zero contribute and have zero gradient entries, even when (possible if ).
- The objective gradient (a matrix).
- The Hessian-type form .
- The quantity under bound: .
The theorem asserts: under all of the following hypotheses —
- and ; and ;
- , and ;
- incoherence: for every row , ;
- normalization: (the squared Frobenius norm equals exactly);
- ;
- ;
- sample-size condition: and (natural logarithm; cast to reals);
- a "good sample" package on , consisting of four facts: (a) is symmetric as a set of pairs, ; (b) for every , the number of pairs in whose first coordinate is is at most ; (c) ; (d) for all symmetric matrices satisfying and , one has ;
- ;
- is positive semidefinite in Mathlib's sense: it is symmetric and for every vector —
then, writing , the following non-strict inequality holds:
Note that no minimizer, first-order, or second-order stationarity condition on is assumed: is an arbitrary matrix subject only to hypothesis 10 (and the conclusion bounds the specific algebraic combination , not the objective function itself). The hypotheses in 5–6 force and only to the extent that and are nonnegative; they also force and into multiplicative windows that are empty unless those two quantities are, respectively, nonnegative. The statement is a plain implication (not an if-and-only-if), and its proof body is omitted in the file (sorry), so the file records the claim, not a completed proof.
Confirmed by the mission captain (proposal self-audit).