bernoulli_restricted_sampling_injectivity_from_tangent_concentration_pos
ProvedPOSITIVE-p CORRECTION of the disproved node bernoulli_restricted_sampling_injectivity_from_tangent_concentration. With the inclusion probability hypothesis strengthened to (the original allowed , where it is false: take , then tangent concentration holds vacuously but is the zero map and hence not injective on a nontrivial tangent space). Claim: if and the high-probability tangent-concentration event has Bernoulli probability , then the event that the sampling operator is injective on the tangent space also has probability . Pointwise, concentration at scale gives for , so ; the Bernoulli statement then follows by monotonicity of under event inclusion ( makes all observation weights nonnegative). Source: Candès–Recht 2009 (arXiv:0805.4471), §4.2 "The injectivity property", Theorem 4.1 eq. (4.5) and the well-conditioning conclusion after eq. (4.11), p.19–20.
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
theorem bernoulli_restricted_sampling_injectivity_from_tangent_concentration_pos
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ} (S : SVD M r)
(p c β : ℝ) :
0 < p → p ≤ 1 →
bernoulliEventProb p
(fun Omega => TangentSamplingConcentration Omega S p ((1 : ℝ) / 2)) ≥
1 - c * Real.rpow (↑(max n₁ n₂)) (-β) →
bernoulliEventProb p (fun Omega => SamplingOperatorInjectiveOnT Omega S) ≥
1 - c * Real.rpow (↑(max n₁ n₂)) (-β) := by
sorry