bernoulli_event_failure_probability_decomposes_by_cardinality
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. Bernoulli failure probability decomposes as a binomial mixture of fixed-cardinality failure probabilities.
Lecture-note formulation:
Decomposition status. A corresponding proof sketch reduces this node to smaller mathematical subclaims. The checked reduction uses 3 subclaims: Bernoulli event success probability decomposes by cardinality; binomial cardinality probabilities sum to one; Bernoulli event failure decomposition from success decomposition.
import Definitions.Def_matrix_completion_fixed_cardinality open MatrixCompletion open scoped Classical BigOperators
theorem bernoulli_event_failure_probability_decomposes_by_cardinality
{n₁ n₂ : ℕ} (p : ℝ)
(Event : Finset (Fin n₁ × Fin n₂) → Prop) :
0 ≤ p → p ≤ 1 →
1 - bernoulliEventProb p Event =
∑ k ∈ Finset.range (n₁ * n₂ + 1),
binomialCardinalityProb (n₁ * n₂) k p *
(1 - fixedCardinalityEventProb k Event) := by
sorry