Una extensión del operador de ruido.

16

En un problema en el que estoy trabajando actualmente, surge una extensión del operador de ruido de forma natural, y tenía curiosidad por saber si ha habido trabajo previo. Primero permítanme revisar el operador de ruido básico en funciones booleanas de valor real. Dada una función y , st , , definimos como $T_{\varepsilon}$ $f: \{0,1\}^n \to \mathbb{R}$ $\varepsilon$ $p$ $0 \leq \varepsilon \leq 1$ $\varepsilon = 1 - 2p$ $T_{\varepsilon} \to \mathbb{R}$ $T_{\varepsilon} f(x) = E_{y \sim \mu_p} [f(x+y)]$

$\mu_p$ es la distribución en obtenida estableciendo que cada bit de un vector de bits sea independientemente con probabilidad y caso contrario. De manera equivalente, podemos pensar en este proceso como voltear cada bit de con probabilidad independiente . Ahora este operador de ruido tiene muchas propiedades útiles, incluyendo ser multiplicativo y tener buenos valores propios y vectores propios ( donde pertenece a la base de paridad). $y$ $n$ $1$ $p$ $0$ $x$ $p$ $T_{\varepsilon_1} T_{\varepsilon_2} = T_{\varepsilon_1 \varepsilon_2}$ $T_{\varepsilon}(\chi_S) = \varepsilon^{|S|} \chi_S$ $\chi_S$

Permítanme ahora definir mi extensión de $T_\varepsilon$ , que denoto como $R_{(p_1,p_2)}$ . $R_{(p_1,p_2)} \to \mathbb{R}$ viene dado por $R_{(p_1,p_2)} f(x) = E_{y \sim \mu_{p,x}} [f(x+y)]$ . Pero aquí nuestra distribución $\mu_{p,x}$ es tal que volteamos los $1$ bits de $x$ a $0$ con probabilidad $p_1$ y $0$ bits de $x$ a $1$ con probabilidad $p_2$ . ( $\mu_{p,x}$ ahora es claramente una distribución dependiente de la $x$ donde se evalúa la función, y si $p_1 = p_2$ entonces $R_{(p_1,p_2)}$ reduce al operador de ruido 'regular').

Me preguntaba, ¿este operador $R_{(p_1,p_2)}$ ya ha sido bien estudiado en algún lugar de la literatura? ¿O son obvias sus propiedades básicas? Estoy empezando con el análisis booleano, por lo que esto podría ser sencillo para alguien más familiarizado con la teoría que yo. En particular, me interesa saber si los vectores propios y los valores propios tienen una buena caracterización, o si existe alguna propiedad multiplicativa.

boolean-functions fourier-analysis Amir
fuente

14

Contestaré la segunda parte de la pregunta.

I. Valores propios y funciones propias

Consideremos primero el caso unidimensional . Es fácil comprobar que el operador tiene dos funciones propias: y con valores propios y , respectivamente. $n=1$ $R_{p_1,p_2}$ $1$

ξ (x) = (p_{1} + p_{2}) x - p_{1} = {\begin{cases} - p_{1}, & if x = 0, \\ p_{2}, & if x = 1. \end{cases}

$\xi(x) = (p_1+p_2)x - p_1 = \begin{cases} -p_1, &\text{ if } x =0,\\ p_2, &\text{ if } x =1. \end{cases}$

1

$1$

1 - p_{1} - p_{2}

$1-p_1 - p_2$

Ahora considera el caso general. Para , deje . Observe que es una función propia de . De hecho, dado que todas las variables son independientes, tenemos $S\subset \{1,\dots,n\}$ $\xi_S(x) = \prod_{i\in S} \xi(x_i)$ $\xi_S$ $R_{p_1,p_2}$ $x_i$

\begin{aligned} R_{p_{1}, p_{2}} (ξ (x)) & = R_{p_{1}, p_{2}} (\prod_{i \in S} ξ (x_{i})) = \prod_{i \in S} R_{p_{1}, p_{2}} (ξ (x_{i})) \\ = \prod_{i \in S} ((1 - p_{1} - p_{2}) ξ (x_{i})) = (1 - p_{1} - p_{2})^{| S |} ξ_{S} (x) . \end{aligned}

$\begin{align*} R_{p_1,p_2}(\xi(x)) &= R_{p_1,p_2}\left(\prod_{i\in S} \xi(x_i)\right) = \prod_{i\in S} R_{p_1,p_2}(\xi(x_i)) \\ &= \prod_{i\in S}\left((1-p_1 - p_2)\xi(x_i)\right) = (1-p_1 - p_2)^{|S|} \xi_S(x). \end{align*}$

Obtenemos que es una función propia de con valor propio para cada . Como las funciones abarcan todo el espacio, no tiene otras funciones propias (que no sean combinaciones lineales de ). $\xi_S(x)$ $R_{p_1,p_2}$ $(1-p_1-p_2)^{|S|}$ $S\subset \{1,\dots,n\}$ $\xi_S(x)$ $R_{p_1,p_2}$ $\xi_S(x)$

II Propiedad Multiplicativa

En general, la "propiedad multiplicativa" no se cumple para ya que la base propia de depende de y . Sin embargo, tenemos donde y . Para verificar eso, primero tenga en cuenta que y tienen el mismo conjunto de funciones propias . Tenemos, desde $R_{p_1,p_2}$ $R_{p_1,p_2}$ $p_1$ $p_2$

R_{p_{1}, p_{2}}^{2} = R_{p_{1}^{'}, p_{2}^{'}},

$R_{p_1,p_2}^2 = R_{p_1',p_2'},$

p_{1}^{'} = 2 p_{1} - (p_{1} + p_{2}) p_{1}

$p_1' = 2p_1- (p_1+p_2)p_1$

p_{2}^{'} = 2 p_{2} - (p_{1} + p_{2}) p_{2}

$p_2' = 2p_2- (p_1+p_2)p_2$

R_{p_{1}, p_{2}}

$R_{p_1,p_2}$

R_{p_{1}^{'}, p_{2}^{'}}

$R_{p_1',p_2'}$

{ξ_{S}}

$\{\xi_S\}$

R_{p_{1}, p_{2}}^{2} (ξ_{S}) = (1 - p_{1} - p_{2})^{2 | S |} ξ_{S} = (1 - p_{1}^{'} - p_{2}^{'})^{| S |} ξ_{S} = R_{p_{1}^{'}, p_{2}^{'}} (ξ_{S})

$R_{p_1,p_2}^2(\xi_S) = (1-p_1-p_2)^{2|S|} \xi_S=(1-p_1'-p_2')^{|S|}\xi_S = R_{p_1',p_2'} (\xi_S)$

\begin{aligned} 1 - p_{1}^{'} - p_{2}^{'} & = 1 - p_{1} \cdot (2 - (p_{1} + p_{2})) - p_{2} \cdot (2 - (p_{1} + p_{2})) \\ = 1 - (p_{1} + p + 2) (2 - (p_{1} + p_{2})) \\ = 1 - 2 (p_{1} + p_{2}) + (p_{1} + p_{2})^{2} = (1 - p_{1} - p_{2})^{2} . \end{aligned}

$\begin{align*} 1-p_1'-p_2' &= 1 - p_1\cdot (2- (p_1+p_2)) - p_2\cdot (2- (p_1+p_2)) \\ &= 1 - (p_1+p+2) (2- (p_1+p_2)) \\ &= 1 - 2(p_1 +p_2) + (p_1 + p_2)^2 = (1-p_1-p_2)^2. \end{align*}$

III. Relación con el operador Bonami-Beckner

Pensemos en las funciones desde hasta como polinomios polilíneos. Deje . Considere el operador Mapea cada polinomio multilineal a un polinomio multilineal . Tenemos, donde . Tenga en cuenta que las partes I y II se derivan de esta fórmula y las propiedades del operador Bonami-Beckner. $\{0,1\}^n$ ${\mathbb R}$ $\delta = \frac{1}{2}\cdot \frac{p_1-p_2}{p_1+p_2}$

A_{δ} (f) = f (x_{1} + δ, \dots, x_{n} + δ) .

$A_{\delta}(f) = f(x_1 + \delta, \dots, x_n + \delta).$

f

$f$

A [f]

$A[f]$

R_{p_{1}, p_{2}} (f) = A_{δ}^{- 1} T_{ε} A_{δ} (f),

$R_{p_1,p_2}(f) = A_{\delta}^{-1} T_{\varepsilon}A_{\delta}(f),$

ε = 1 - p_{1} - p_{2}

$\varepsilon = 1 - p_1 - p_2$

Yury
fuente

Yury, gracias por la respuesta! Ese es un buen punto de partida para trabajar con mí; Ahora debería poder averiguar si hay análogos de la desigualdad hipercontractiva. Volveré a publicar aquí si obtengo algún análisis más interesante.

Amir

Esto es mucho tiempo después del hecho, pero tengo curiosidad por saber cómo obtuvo la tercera parte y la relación con el operador Becker Bonami.

Amir

(a) Es suficiente para comprobar la identidad para y . Si es válido para y

f = 1

$f=1$

f = x_{i}

$f=x_i$

1

$1$

x_{i}

$x_i$ , entonces es fácil ver que se cumple para todos los caracteres. Por linealidad, se cumple para todas las funciones. (b) Alternativamente, de I, y tienen el mismo conjunto de valores propios; autovector de “corresponde” a autovector de . Por lo tanto, donde A es un mapa lineal que asigna a .

T_{ε}

$T_\varepsilon$

R_{p_{1}, p_{2}}

$R_{p_1,p_2}$

\prod_{i \in S} x_{i}

$\prod_{i\in S} x_i$

T

$T$

\prod_{i \in S} ξ (x_{i})

$\prod_{i\in S} \xi(x_i)$

R

$R$

R (f) = A^{- 1} T A (f)

$R(f) = A^{-1} T A(f)$

ξ (x)

$\xi(x)$

x

$x$

Yury

3

Eventualmente pudimos analizar las propiedades hipercontractivas de ( http://arxiv.org/abs/1404.1191 ), a partir del análisis de Fourier principal de por Ahlberg, Broman, Griffiths y Morris ( http://arxiv.org/abs/1108.0310 ). $R_{p_1, p_2}$ $R_{p,0}$

Para resumir, el efecto de un operador sesgado en una función puede analizarse como un operador de ruido simétrico en un espacio de medida sesgado. Esto proporciona una forma débil de hipercontractividad, que depende de cómo norma de cuando se cambia a una elección de medida sesgada depende de . $R_{p,0}$ $f$ $\ell_2$ $f$ $\mu$ $p$

Amir
fuente

Es posible que desee 'aceptar' esta respuesta para que la pregunta no siga apareciendo (descargo de responsabilidad: soy un autor en el documento vinculado)

Suresh Venkat

Una extensión del operador de ruido.

Respuestas: