First- and second-order optimality conditions of the objective (Chen–Li Lemma 4.3; GLM Prop. 5.1)
ProvedMatrixCompletion.NoSpuriousMin.optimality_conditionsLet with , threshold , and a symmetric observation set (as in Chen–Li's off-diagonal symmetric sampling model, where symmetry is ambient). If is a local minimum of , then satisfies the explicit first-order condition
and, for every direction , the second-order condition
Together these give at every local minimum — the entry point of the Chen–Li superlevel-set argument.
Formalization Note The symmetry of is a genuine hypothesis of the first-order clause, not a convenience: the gradient of the sampled term is for , which equals exactly when is symmetric. For non-symmetric there are strict local minima at which , so the clause would be false as stated. The second-order clause holds regardless; the hypothesis is stated once for the conjunction.
import Definitions.Def_MCNoSpuriousMinModel import Mathlib.Topology.Order.LocalExtr import Mathlib.Topology.Instances.Matrix open Matrix MatrixCompletion.NoSpuriousMin
theorem MatrixCompletion.NoSpuriousMin.optimality_conditions
{d r : ℕ} (Z X : Matrix (Fin d) (Fin r) ℝ) (Ω : Finset (Fin d × Fin d))
(lam α : ℝ) (hlam : 0 ≤ lam) (hα : 0 < α)
(hsym : ∀ i j : Fin d, (i, j) ∈ Ω ↔ (j, i) ∈ Ω)
(hmin : IsLocalMin (objective Z Ω lam α) X) :
FirstOrderPt Z Ω lam α X ∧ SecondOrderPt Z Ω lam α X := by sorryRead-back
What the Lean code literally says, in plain math · claude-fable-5
Read-back — MatrixCompletion.NoSpuriousMin.optimality_conditions
For every pair of natural numbers (including the degenerate cases or , where all matrices below are trivial and all sums over rows or entries are empty), every pair of real matrices and , every finite set of index pairs , and all real numbers and , under the hypotheses
- (non-strict),
- (strict),
- is symmetric: for all , if and only if ,
- is a local minimum of the function defined below, in the sense that there exists a neighborhood of (in the standard entrywise topology on the space of real matrices) on which for every matrix in that neighborhood (a non-strict local minimum, so e.g. any point of a locally constant function qualifies),
the theorem concludes the conjunction of two conditions, (A) and (B) below. Throughout, denotes the matrix that keeps the entry when and sets it to otherwise; is the entrywise (Frobenius) inner product; is the sum of squared entries; is the Euclidean norm of row ; and . The objective is
(A) First-order condition. The matrix
is the zero matrix, where is the explicitly given matrix with entries
with the convention (from the ambient division on the reals) that division by zero yields zero — so when the entry is by that convention (its numerator also vanishes since ). Note that is a fixed closed-form formula, not a derivative computed by the theorem: condition (A) asserts that this particular expression equals zero, not that is differentiable at . (B) Second-order condition. For every real matrix (not merely directions in some restricted set),
where is the explicitly given quantity
with , and again the division-by-zero-equals-zero convention applying wherever (in which case both summands for row vanish). As in (A), is a fixed closed-form formula asserted directly; the theorem makes no claim that it coincides with an actual second derivative of . The hypotheses on , , and the symmetry of are assumptions of the theorem; nothing in the statement constrains , and may be empty (in which case is identically zero and the projection terms in , (A), and (B) all vanish).
Confirmed by the mission captain (proposal self-audit).