binomial_lower_tail_at_matrix_sample_mean_ge_half
ProvedRole. It is a reusable node in the Candes-Recht decomposition, phrased as a standalone theorem so that downstream sketches can import it directly.
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. A binomial random variable with mean has at least half its mass at cardinalities ≤ m, specialized to and .
Lecture-note formulation:
Decomposition status. A corresponding proof sketch reduces this node to smaller mathematical subclaims. The checked reduction uses 1 subclaim: binomial lower tail at integer mean ge half.
import Definitions.Def_matrix_completion_fixed_cardinality open MatrixCompletion
theorem binomial_lower_tail_at_matrix_sample_mean_ge_half
(n₁ n₂ m : ℕ) :
0 < n₁ → 0 < n₂ → m ≤ n₁ * n₂ →
(1 / 2 : ℝ) ≤
binomialLowerTailProb (n₁ * n₂) m
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) := by
sorry