centered_sampling_symmetrization_moment_bound_of_sample_ratio
Provedbernoulli-samplingcandes-rechtlean4matrix-completionrademachersection-6-1symmetrization
This is the sample-ratio-safe symmetrization estimate used in Section 6.1 of Candes-Recht.
For
assuming , , and , there is a universal constant such that for every matrix and every integer ,
Source: Candes-Recht 2008, PDF p. 24, Section 6.1, equation (6.5), the Jensen independent-copy paragraph, the Rademacher symmetry of , and the displayed triangle-inequality estimate.
Preamble
import Definitions.Def_matrix_completion_rademacher open MatrixCompletion
Formal statement
theorem centered_sampling_symmetrization_moment_bound_of_sample_ratio :
∃ Csym : ℝ, 0 < Csym ∧
∀ (n₁ n₂ m q : ℕ) (X : Matrix (Fin n₁) (Fin n₂) ℝ),
0 < n₁ → 0 < n₂ → m ≤ n₁ * n₂ → 1 ≤ q →
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
spectralNorm
(centeredSamplingFluctuation Omega
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X) ^ q) ≤
Csym ^ q *
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
rademacherExpectation
(fun eps =>
spectralNorm
(rademacherSampledMatrix Omega eps
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X) ^ q)) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.