nonempty_closed_matrix_set_has_frobenius_sq_minimizer
Provedcandes-rechtdual-certificatefinite-dimensional-optimizationlean4least-squaresmatrix-completion
This is the finite-dimensional optimization lemma behind the least-squares certificate problem.
For matrices , let
The theorem says that if is a nonempty closed subset of this finite-dimensional matrix space, then there exists such that
This packages the coercivity/properness argument for the Frobenius norm in finite dimensions. In the Candes-Recht proof it is used for the feasible affine set in equation (4.1).
Source: formal finite-dimensional optimization bridge for Candes-Recht 2008, PDF p. 17, equation (4.1).
Preamble
import Mathlib.Tactic import Definitions.Def_matrix_completion_tangent open MatrixCompletion
Formal statement
theorem nonempty_closed_matrix_set_has_frobenius_sq_minimizer
{n₁ n₂ : ℕ} (C : Set (Matrix (Fin n₁) (Fin n₂) ℝ)) :
C.Nonempty → IsClosed C →
∃ Y : Matrix (Fin n₁) (Fin n₂) ℝ,
Y ∈ C ∧ ∀ Z : Matrix (Fin n₁) (Fin n₂) ℝ,
Z ∈ C → frobeniusNormSq Y ≤ frobeniusNormSq Z := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.