bernoulli_tangent_sampling_concentration_formula_bound
DisprovedRole. It belongs to the tangent-space injectivity branch, where concentration of the sampled tangent operator rules out nonzero feasible tangent perturbations.
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 . For tangent-space nodes, the main event is that the sampled tangent operator is well conditioned; this prevents a nonzero tangent perturbation from agreeing with M on the sampled entries.
Claim. Formula-scale version of Theorem 4.1 for tangent sampling concentration: the deviation estimate is converted directly into the pointwise concentration event needed by the Neumann-series proof.
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. A corresponding proof sketch reduces this node to smaller mathematical subclaims. The checked reduction uses 3 subclaims: Bernoulli tangent sampling deviation formula bound; Bernoulli tangent sampling concentration from deviation bound; sample ratio between zero and one.
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
theorem bernoulli_tangent_sampling_concentration_formula_bound :
∃ C c : ℝ, 0 < C ∧ 0 < c ∧
∀ (β : ℝ), 2 < β →
∀ (n₁ n₂ r m : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
(μ₀ μ₁ : ℝ) (S : SVD M r),
0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
1 ≤ μ₀ → 1 ≤ μ₁ →
A0 S μ₀ → A1 S μ₁ →
bernoulliEventProb ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
TangentSamplingConcentration Omega S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(tangentSamplingDeviationScale C β μ₀ (max n₁ n₂) r m)) ≥
1 - c * Real.rpow (↑(max n₁ n₂)) (-β) := by
sorry