talagrand_appendix91_log_exponent_absorbs_polynomial_failure
Disprovedappendix-91candes-rechtmatrix-completionpolynomial-tailscalar-arithmeticsource-faithfultalagrand
This scalar theorem isolates the last numerical step in Candès--Recht Appendix 9.1.
Let , , and assume the sample lower bound
For a sufficiently large universal constant , set
The theorem asserts that and that the logarithmic Talagrand failure term from equation (9.2), with , is bounded by . This is exactly the scalar absorption used before Theorem 4.2 equation (4.10).
Source location: Candès--Recht 2008, Appendix 9.1, PDF p. 47, the paragraph beginning “Since ” through “Plugging and establishes the claim.”
Preamble
import Definitions.Def_matrix_completion_tangent
import Mathlib.Analysis.SpecialFunctions.Log.Basic
open MatrixCompletion
/-- Scalar failure-probability absorption in the Appendix 9.1 Talagrand
argument.
With `B = 2 μ₀ n r / m`, `E Z ≤ 1`, and the Candes--Recht sample lower bound,
the logarithmic exponent in Theorem 9.1 at the standard tangent-deviation scale
is large enough to dominate a polynomial failure probability `c n^{-β}`. The
theorem also records that the chosen deviation scale is nonnegative, so it can
be substituted into the tail bound.
Source: Candes--Recht, Appendix 9.1, PDF p. 47, the paragraph beginning
"Since E Z ≤ 1" through "Plugging t = ... establishes the claim", using
Theorem 9.1 equation (9.2). -/Formal statement
theorem talagrand_appendix91_log_exponent_absorbs_polynomial_failure
(K : ℝ) :
0 < K →
∃ C c : ℝ, 0 < C ∧ 0 < c ∧
∀ C' : ℝ, C ≤ C' →
∀ (β : ℝ), 2 < β →
∀ (n₁ n₂ r m : ℕ) (μ₀ meanZ : ℝ),
0 < n₁ → 0 < n₂ → 0 < r → 0 < m → m ≤ n₁ * n₂ →
1 ≤ μ₀ →
(m : ℝ) ≥
C' * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) *
(β * Real.log (↑(max n₁ n₂))) →
meanZ ≤ 1 →
0 ≤ tangentSamplingDeviationScale C β μ₀ (max n₁ n₂) r m ∧
3 * Real.exp
(-(tangentSamplingDeviationScale C β μ₀ (max n₁ n₂) r m /
(K * (2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)))) *
Real.log
(1 +
((2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)) *
tangentSamplingDeviationScale C β μ₀ (max n₁ n₂) r m) /
((2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)) +
(2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)) *
meanZ))) ≤
c * Real.rpow (↑(max n₁ n₂)) (-β) := by
sorrySource
Candes, Emmanuel, and Benjamin Recht. "Exact Matrix Completion via Convex Optimization" (2008).