bernoulli_tangent_sampling_concentration_formula_bound_dense
Openconcentrationmatrix-completionprobability
Corrected (density-carrying) form of bernoulli_tangent_sampling_concentration_formula_bound, whose no-density version was disproved. Under , AND the density side condition (, ), there exist such that with the tangent sampling concentration for all holds with probability at least , where . Candès–Recht 2009, Theorem 4.1 (eq. (4.5)), restored with its density hypothesis.
Preamble
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
Formal statement
theorem bernoulli_tangent_sampling_concentration_formula_bound_dense :
∃ 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 μ₁ →
(m : ℝ) ≥ β * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) *
Real.log (↑(max n₁ n₂)) →
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 sorrySource
Candès & Recht, Exact Matrix Completion via Convex Optimization, arXiv:0805.4471, Theorem 4.1 (eq. (4.5), p.18).