bernoulli_pair_decoupling_spectral_tail_bound
Disprovedconcentrationdecouplingmatrix-completionu-statistics
Abstract order-2 (pair) de la Pena-Montgomery-Smith decoupling tail bound for the spectral norm of a matrix-valued bilinear sampling contribution over the Bernoulli powerset model. For any matrix-valued function G of two independent observation sets, the tail of the diagonal statistic G(Omega,Omega) is controlled by the tail of the fully decoupled statistic G(Omega1,Omega2) using independent copies, with universal constants K, L depending only on the order k=2. This is the order-2 case of the decoupling inequality P(|S|>t) <= C_k P(|S_decoupled| > t/C_k).
Preamble
import Definitions.Def_matrix_completion_neumann open MatrixCompletion open scoped BigOperators Classical
Formal statement
theorem bernoulli_pair_decoupling_spectral_tail_bound :
∃ K L : ℝ, 0 < K ∧ 0 < L ∧
∀ {n₁ n₂ : ℕ}
(G : Finset (Fin n₁ × Fin n₂) →
Finset (Fin n₁ × Fin n₂) → RealMatrix n₁ n₂)
(p Cdec cdec failureScale thresholdScale : ℝ),
0 ≤ p → p ≤ 1 → 0 < Cdec → 0 < cdec →
bernoulliPairEventProb p
(fun Omega1 Omega2 =>
spectralNorm (G Omega1 Omega2) ≤ Cdec * thresholdScale) ≥
1 - cdec * failureScale →
bernoulliEventProb p
(fun Omega =>
spectralNorm (G Omega Omega) ≤ (K * Cdec) * thresholdScale) ≥
1 - (L * cdec) * failureScale := by
sorrySource
de la Pena, V. H. and Montgomery-Smith, S. J., "Decoupling Inequalities for the Tail Probabilities of Multivariate U-Statistics", Annals of Probability 23 (1995), no. 2, 806-816 (arXiv:math/9309211), main decoupling theorem (order k=2). Applied in Candes-Recht 2009 (arXiv:0805.4471), Section 4-6, to decouple the bilinear Neumann sampling contributions.