CR eq. (4.10): the Talagrand exponential tail absorbs into a polynomial failure
ProvedMatrixCompletion.talagrand_tangent_exponential_tail_absorbs_into_polynomial_failure_denseCandès–Recht (2009, Exact Matrix Completion via Convex Optimization, arXiv:0805.4471 / Found. Comput. Math. 9:717–772), Appendix §9.1, the derivation of eq. (4.10) from Theorem 9.1 (eq. (9.2)), p. 46. Starting from the Talagrand/Bousquet exponential tail , specialise and , plug , and use together with the Theorem 4.1 sampling density to absorb the prefactor 3 into a polynomial failure probability . Pure algebra — no probability appears. Explicit witnesses , . This is the faithful correction of the earlier weak-density form , which is FALSE (letting at drives the tail to for any fixed ). It is the eq. (4.10) bridge that, together with the abstract Talagrand sup-concentration core, closes CR Theorem 4.2.
Preamble
import Definitions.Def_matrix_completion_talagrand open MatrixCompletion
Formal statement
namespace MatrixCompletion
theorem talagrand_tangent_exponential_tail_absorbs_into_polynomial_failure_dense
(K Cexpect : ℝ) :
0 < K → 0 < Cexpect →
∃ Ctail c : ℝ, 0 < Ctail ∧ 0 < c ∧
∀ (β μ₀ : ℝ) (n r m : ℕ),
2 < β → 1 ≤ μ₀ → 0 < n → 0 < r → 0 < m →
(m : ℝ) ≥ μ₀ * (r : ℝ) * β * (n : ℝ) * Real.log (n : ℝ) →
3 * Real.exp
(-(tangentSamplingDeviationScale Ctail β μ₀ n r m /
(K * (2 * μ₀ * (n : ℝ) * (r : ℝ) / (m : ℝ)))) *
Real.log
(1 +
(2 * μ₀ * (n : ℝ) * (r : ℝ) / (m : ℝ)) *
tangentSamplingDeviationScale Ctail β μ₀ n r m /
((2 * μ₀ * (n : ℝ) * (r : ℝ) / (m : ℝ)) +
(2 * μ₀ * (n : ℝ) * (r : ℝ) / (m : ℝ)) *
tangentSamplingDeviationScale Cexpect β μ₀ n r m))) ≤
c * Real.rpow (n : ℝ) (-β) := by sorry
end MatrixCompletionSource
Candès & Recht 2009, arXiv:0805.4471, Appendix §9.1 (Proof of Theorem 4.2), eq. (4.10) derived from Theorem 9.1 / eq. (9.2), p. 46. Sampling density m ≥ μ₀ r β n log n is CR Theorem 4.1.