talagrand_tangent_sampling_deviation_around_mean_raw_tail
Disprovedcandes-rechtconcentrationmatrix-completiontalagrandtangent-spacetheorem-42
This is the raw Talagrand concentration input for the tangent-sampling deviation in the Bernoulli model.
Let
be the operator norm of the centered tangent sampling fluctuation. Assume the two Talagrand hypotheses used in Candes--Recht Appendix 9.1 hold at a common scale : every coordinate increment in the supremum representation is bounded by , and the corresponding variance proxy is also bounded by .
Then there are universal constants such that, for every and ,
This node is the source theorem behind the later Candes--Recht scale substitution. Source location: Candes--Recht, PDF p. 19, equation (4.10), with the bounded-increment and variance hypotheses described in Appendix 9.1.
Preamble
import Definitions.Def_matrix_completion_talagrand open MatrixCompletion
Formal statement
theorem talagrand_tangent_sampling_deviation_around_mean_raw_tail :
∃ K c : ℝ, 0 < K ∧ 0 < c ∧
∀ (β : ℝ), 2 < β →
∀ (n₁ n₂ r m : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
(μ₀ μ₁ : ℝ) (S : SVD M r) (B : ℝ),
0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
1 ≤ μ₀ → 1 ≤ μ₁ →
A0 S μ₀ → A1 S μ₁ →
TangentSamplingTalagrandIncrementBound S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) B →
TangentSamplingTalagrandVarianceBound S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) B →
bernoulliEventProb ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
TangentSamplingDeviationBound Omega S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(bernoulliExpectation
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega' =>
tangentSamplingDeviation Omega' S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) +
K * Real.sqrt (B * (β * Real.log (↑(max n₁ n₂)))))) ≥
1 - c * Real.rpow (↑(max n₁ n₂)) (-β) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.