fixed_cardinality_event_probability_monotone_of_event_mono
ProvedRole. It belongs to the sampling-model transfer layer, relating fixed-cardinality probabilities to Bernoulli probabilities.
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 . This node is in the sampling-model transfer layer: it compares the uniform exactly- observation model with the independent Bernoulli model.
Claim. For a monotone success event, fixed-cardinality success probability is monotone in the number of observed entries.
Lecture-note formulation:
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_fixed_cardinality open MatrixCompletion
theorem fixed_cardinality_event_probability_monotone_of_event_mono
{n₁ n₂ : ℕ} (Event : Finset (Fin n₁ × Fin n₂) → Prop) :
(∀ Omega Omega' : Finset (Fin n₁ × Fin n₂),
Omega ⊆ Omega' → Event Omega → Event Omega') →
∀ k m : ℕ, k ≤ m → m ≤ n₁ * n₂ →
fixedCardinalityEventProb k Event ≤
fixedCardinalityEventProb m Event := by
sorry