TCSLib

290 Boolean Analysis — Noise Kernel

290.1 Overview

Conditional expectations, orthogonal components, and spectral noise admit explicit finite resampling kernels. For noise rates between zero and one the resulting operator contracts the absolute first moment.

290.2 Declarations

Theorem 290.1 Conditional expectation kernel
✓

Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) with coordinate weights \(w_i\), \(S\subseteq [n]\), and \(f:\Omega \to \mathbb R\). Then \(E_Sf(x)=\sum _y[\prod _{i\in S}\mathbf1_{x_i=y_i}\prod _{i\notin S}w_i(y_i)]f(y)\) for every \(x\in \Omega \).

Theorem 290.2 Alternating expansion of product kernels
✓

For a finite set \(I\), \(S\subseteq I\), and real functions \(a,b\) on \(I\), \(\sum _{T\subseteq S}(-1)^{|S|-|T|}\prod _{i\in T}a_i\prod _{i\notin T}b_i=\prod _{i\in S}(a_i-b_i)\prod _{i\notin S}b_i\).

Theorem 290.3 Orthogonal component kernel
✓

Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) with coordinate weights \(w_i\), \(S\subseteq [n]\), and \(f:\Omega \to \mathbb R\). Its orthogonal component satisfies \(f_S(x)=\sum _y[\prod _{i\in S}(\mathbf1_{x_i=y_i}-w_i(y_i))\prod _{i\notin S}w_i(y_i)]f(y)\).

Theorem 290.4 Spectral noise kernel
✓

Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) with coordinate weights \(w_i\), \(\rho \in \mathbb R\), and \(f:\Omega \to \mathbb R\). Then \(T_\rho f(x)=\sum _y[\prod _i(\rho \mathbf1_{x_i=y_i}+(1-\rho )w_i(y_i))]f(y)\) for every \(x\in \Omega \).

Theorem 290.5 Absolute first moment contraction
✓

Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(0\le \rho \le 1\), and \(f:\Omega \to \mathbb R\). Then \(\| T_\rho f\| _{1,P}\le \| f\| _{1,P}\).