rademacher_expectation_monotone
Provedmatrix-completionprobabilityrademacher
Monotonicity of the Rademacher expectation. If for every Rademacher sign realization (encoded as the finite set of coordinates carrying a sign) we have , then the Rademacher expectations satisfy rademacherExpectation F rademacherExpectation G. The expectation is a finite sum of values weighted by nonnegative uniform Rademacher weights.
Preamble
import Definitions.Def_matrix_completion_rademacher open MatrixCompletion
Formal statement
theorem rademacher_expectation_monotone :
∀ {n₁ n₂ : ℕ}
(F G : Finset (Fin n₁ × Fin n₂) → ℝ),
(∀ S, F S ≤ G S) →
rademacherExpectation F ≤ rademacherExpectation G := by sorrySource
Candes & Recht, Exact matrix completion via convex optimization, CACM 55.6 (2012).