Negative-definite quadratic bound on : (Chen–Li eq. (4.14), exact case)
DisprovedMatrixCompletion.NoSpuriousMin.K_superlevel_boundmatrix-completionmc-no-spuriousnonconvex-optimization
In 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.
Preamble
import Definitions.Def_MCNoSpuriousMinModel import Mathlib.LinearAlgebra.Matrix.PosDef open Matrix MatrixCompletion.NoSpuriousMin
Formal statement
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 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. 20, eq. (4.14), obtained via eqs. (4.8)-(4.13), exact-rank specialization (psi = 0). The psd trace identities (4.10)-(4.13) use the alignment X^T U >= 0 from Section 4.2.1.