linear_neumann_off_diagonal_two_term_bernstein_threshold_absorbed_under_sample_bound
Disprovedbernsteincandes-rechtlemma-66matrix-completionsample-complexityscalar-arithmetic
This theorem is the scalar sample-size absorption that turns the two-term Bernstein threshold in Candes--Recht equation (6.17) into the final Lemma 6.6 coefficient scale.
The raw threshold is
with
The conclusion is that this threshold is at most
under the stated sample lower bound. The accepted sketch splits the claim into the Frobenius/variance summand and the entry-sup/range summand, then adds the two inequalities.
Source location: Candes--Recht, Section 6.2, Lemma 6.6, equation (6.17) and the paragraph immediately following it.
Preamble
import Definitions.Def_linear_neumann_offdiag_bernstein open MatrixCompletion
Formal statement
theorem linear_neumann_off_diagonal_two_term_bernstein_threshold_absorbed_under_sample_bound
(Ctwo Centry Cfro : ℝ) :
0 < Ctwo → 0 < Centry → 0 < Cfro →
∃ Ccoef : ℝ, 0 < Ccoef ∧
∀ (β lam : ℝ), 2 < β → 1 ≤ lam →
∀ (n₁ n₂ r m : ℕ) (μ₀ μ₁ : ℝ),
0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
1 ≤ μ₀ → 1 ≤ μ₁ →
(m : ℝ) ≥
lam * μ₁ * max (Real.sqrt μ₀) μ₁ *
(↑(max n₁ n₂)) * (r : ℝ) *
(β * Real.log (↑(max n₁ n₂))) →
Ctwo *
(Real.sqrt
(((β + 2) * Real.log (↑(max n₁ n₂))) /
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) *
(Cfro * μ₁ *
Real.sqrt ((r : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) *
Real.sqrt (μ₀ * (r : ℝ) / (↑(max n₁ n₂)))) +
(((β + 2) * Real.log (↑(max n₁ n₂))) /
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) *
(Centry * μ₁ *
Real.sqrt ((r : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) *
(μ₀ * (r : ℝ) / (↑(max n₁ n₂))))) ≤
Ccoef * μ₁ *
Real.sqrt ((r : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) *
Real.sqrt
((μ₀ * (↑(max n₁ n₂)) * (r : ℝ) *
(β * Real.log (↑(max n₁ n₂)))) / (m : ℝ)) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.