quadratic_neumann_all_equal_mean_factored_scale_from_sample_lower
Provedcandes-rechtlean4matrix-completionneumann-certificateprobabilityquadratic-termssample-complexity
This corrected scalar lemma is the all-equal deterministic-mean sample-size absorption needed in the quadratic Neumann part of the Candes-Recht certificate proof. Write
p=rac{m}{n_1n_2},qquad n=max(n_1,n_2).For every positive base constant there is a positive constant such that, under the Lemma 4.6 sample lower bound
mge lambda,mu_0^{4/3},n,r^{4/3},etalog n,with eta>2, , positive dimensions, positive rank, and , one has
C_{base},left|p^{-2}(1-3p+2p^2) ight|left(rac{mu_0r}{n} ight)^2le C_{scale},lambda^{-3/2}.The retained coefficient is essential: it vanishes at endpoint sampling rates such as , which is exactly where the retired unfactored scale lemma failed.
Preamble
import Definitions.Def_matrix_completion_neumann open MatrixCompletion
Formal statement
theorem quadratic_neumann_all_equal_mean_factored_scale_from_sample_lower
(Cbase : ℝ) :
0 < Cbase →
∃ Cscale : ℝ, 0 < Cscale ∧
∀ (β lam : ℝ), 2 < β → 1 ≤ lam →
∀ (n₁ n₂ r m : ℕ) (μ₀ : ℝ),
0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
1 ≤ μ₀ →
(m : ℝ) ≥
lam * Real.rpow μ₀ ((4 : ℝ) / 3) *
(↑(max n₁ n₂)) * Real.rpow (r : ℝ) ((4 : ℝ) / 3) *
(β * Real.log (↑(max n₁ n₂))) →
Cbase *
(|((((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))⁻¹) ^ 2 *
(1 - 3 * ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) +
2 * ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) ^ 2))| *
((μ₀ * (r : ℝ) / (↑(max n₁ n₂))) ^ 2)) ≤
Cscale * Real.rpow lam (-((3 : ℝ) / 2)) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.