rademacher_sampled_difference_moment_le_single_sample_moment
DisprovedRole. It is part of the symmetrization and matrix-moment machinery behind the spectral norm concentration estimates.
Problem and notation. Exact matrix completion asks when an unknown low-rank real matrix can be recovered from a random subset of its entries. Here has rank , entries are observed, and . Recovery means nuclear-norm minimization: minimize among matrices agreeing with on the observed entries. Probability notation. is the fixed-cardinality success probability: is chosen uniformly among all subsets of entries with , and the event is that the convex program uniquely returns . In Bernoulli nodes, or means each entry is sampled independently with probability , usually . Coherence notation. The object records SVD/singular-vector data for . The hypotheses and are the Candes-Recht incoherence assumptions: measures how spread out the singular vector spaces are, and measures the largest entry of the sign matrix . The parameter controls polynomial failure probabilities such as .
Claim. Triangle/Minkowski step after Rademacher symmetrization: the signed difference of two independent sampled matrices is controlled by the one-sample Rademacher moment up to a universal constant.
Lecture-note formulation:
The constants in this node are universal existential constants; the theorem asserts that some positive constants with these roles exist.
Decomposition status. This node is currently a leaf problem in the decomposition tree, intended to be proved directly by later agents.
import Definitions.Def_matrix_completion_rademacher open MatrixCompletion
theorem rademacher_sampled_difference_moment_le_single_sample_moment :
∃ Csym : ℝ, 0 < Csym ∧
∀ (n₁ n₂ m q : ℕ) (X : Matrix (Fin n₁) (Fin n₂) ℝ),
1 ≤ q →
bernoulliPairExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega Omega' =>
rademacherExpectation
(fun eps =>
spectralNorm
(rademacherSampledMatrix Omega eps
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X -
rademacherSampledMatrix Omega' eps
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X) ^ q)) ≤
Csym ^ q *
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
rademacherExpectation
(fun eps =>
spectralNorm
(rademacherSampledMatrix Omega eps
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X) ^ q)) := by
sorry