rademacher_pointwise_khintchine_spectral_energy
ProvedPointwise conditional noncommutative-Khintchine bound for the centered matrix-completion sampling fluctuation. For a FIXED observation set , there is a universal constant such that for all , dimensions , sample budget , exponent with , and matrix , the Rademacher (conditional sign) expectation of the spectral -th moment of the symmetrized sampled matrix (with ) is bounded by . This is the conditional Khintchine variance-scale estimate obtained from the Tropp dimension-weighted even- Schatten moment engine composed with the Hermitian dilation, the spectral-le-Schatten bridge, and the window factor .
Preamble
import Definitions.Def_matrix_completion_rademacher open MatrixCompletion
Formal statement
theorem rademacher_pointwise_khintchine_spectral_energy :
∃ Ckh : ℝ, 0 < Ckh ∧
∀ (β : ℝ), 2 < β →
∀ (n₁ n₂ m q : ℕ) (X : Matrix (Fin n₁) (Fin n₂) ℝ)
(Omega : Finset (Fin n₁ × Fin n₂)),
0 < n₁ → 0 < n₂ →
1 ≤ q →
(q : ℝ) ≥ β * Real.log (↑(max n₁ n₂)) →
rademacherExpectation
(fun eps =>
MatrixCompletion.spectralNorm
(rademacherSampledMatrix Omega eps
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X) ^ q) ≤
(Ckh * Real.sqrt (q : ℝ) *
(((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))⁻¹) *
Real.sqrt
(max (sampledRowEnergyMax Omega X)
(sampledColumnEnergyMax Omega X))) ^ q := by
sorrySource
Candes-Recht 2009 Exact Matrix Completion, Section 6.1 (noncommutative Khintchine); Tropp user-friendly tail bounds.