Rozszerzenie operatora hałasu

16

W przypadku problemu, nad którym obecnie pracuję, naturalnie pojawia się rozszerzenie operatora hałasu i byłem ciekawy, czy były wcześniejsze prace. Najpierw pozwól mi zrewidować podstawowy operator hałasu na funkcjach boolowskich o wartościach rzeczywistych. Biorąc pod uwagę funkcję i , st , , definiujemy jako $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$ jest dystrybucja w uzyskane przez ustawienie każdego bitu o wektora bitowych się niezależnie z prawdopodobieństwem i w inny sposób. Równolegle możemy myśleć o tym procesie jako odwracaniu każdego bitu niezależnym prawdopodobieństwem . Teraz ten operator szumów ma wiele przydatnych właściwości, w tym bycie multiplikatywnym i posiadanie ładnych wartości własnych i wektorów własnych ( gdzie należy do podstawy parzystości). $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$

Pozwól mi teraz zdefiniować moje rozszerzenie , które oznaczam jako . jest podane przez . Ale tutaj nasz rozkład jest taki, że zamieniamy bit od z prawdopodobieństwem i bitów do z prawdopodobieństwem . ( jest teraz wyraźnie rozkładem zależnym od którym funkcja jest oceniana, i jeśli $T_\varepsilon$ $R_{(p_1,p_2)}$ $R_{(p_1,p_2)} \to \mathbb{R}$ $R_{(p_1,p_2)} f(x) = E_{y \sim \mu_{p,x}} [f(x+y)]$ $\mu_{p,x}$ $1$ $x$ $0$ $p_1$ $0$ $x$ $1$ $p_2$ $\mu_{p,x}$ $x$ $p_1 = p_2$ następnie redukuje się do „zwykłego” operatora hałasu.) $R_{(p_1,p_2)}$

Zastanawiałem się, czy ten operator został już dobrze zbadany gdzieś w literaturze? A może jego podstawowe właściwości są oczywiste? Zaczynam od analizy boolowskiej, więc może to być dla kogoś bardziej obeznanego z teorią niż ja. W szczególności interesuje mnie, czy wektory własne i wartości własne mają jakąś ładną charakterystykę, czy też istnieje jakaś właściwość multiplikatywna. $R_{(p_1,p_2)}$

boolean-functions fourier-analysis

— Amir
źródło

14

Odpowiem na drugą część pytania.

I. Wartości własne i funkcje własne

Rozważmy najpierw przypadek jednowymiarowy . Łatwo jest sprawdzić, czy operator ma dwie funkcje własne: i z wartościami własnymi i $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$

Teraz rozważ ogólny przypadek. Dla niech . Zauważ, że jest funkcją własną . Rzeczywiście, ponieważ wszystkie zmienne są niezależne, mamy $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*}$

Otrzymujemy, że jest funkcją własną z wartością własną dla każdego . Ponieważ funkcje obejmują całą przestrzeń, $\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}$ nie ma innych funkcji własnych (które nie są liniowymi kombinacjami ). $\xi_S(x)$

II. Mnożliwość

Ogólnie rzecz biorąc, „właściwość multiplikatywna” nie dotyczy ponieważ podstawa własna zależy od i . Jednakże, ma w którym $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'},$

i

. Aby stwierdzić, czy pierwsze zauważyć, że

i

mają ten sam zestaw funkcyj

. Mamy,

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\}$

od

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. Związek z operatorem Bonami — Beckner

$\{0,1\}^n$ ${\mathbb R}$ $\delta = \frac{1}{2}\cdot \frac{p_1-p_2}{p_1+p_2}$

{ZA}_{δ} (fa) = fa (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)}} (fa) = {ZA}_{δ}^{- 1} {T.}_{ε} {ZA}_{δ} (fa),

$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
źródło

Yury, dziękuję za odpowiedź! To dobry punkt wyjścia do pracy; Powinienem być w stanie ustalić, czy istnieją analogie hiper-kurczliwej nierówności. Wrócę tutaj, jeśli otrzymam bardziej interesującą analizę.

— Amir

To jest bardzo długo po fakcie, ale jestem ciekawy, jak wyprowadziłeś trzecią część i relację z operatorem Beckera Bonami?

— Amir

(a) Wystarczy sprawdzić tożsamość

f = 1

$f=1$ i

f = x_{i}

$f=x_i$ . Jeśli tak jest

1

$1$ i

x_{i}

$x_i$ , łatwo zauważyć, że dotyczy wszystkich postaci. Według liniowości dotyczy wszystkich funkcji. (b) Alternatywnie, od I,

T_{ε}

$T_\varepsilon$ i

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

$R_{p_1,p_2}$ mieć ten sam zestaw wartości własnych; wektor własny

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

$\prod_{i\in S} x_i$ z

T

$T$ „Odpowiada” wektorowi własnemu

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

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

R

$R$ . A zatem

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

$R(f) = A^{-1} T A(f)$ gdzie A jest mapą liniową, która odwzorowuje

ξ (x)

$\xi(x)$ do

x

$x$ .

— Yury

3

W końcu byliśmy w stanie przeanalizować hiperkontraktyczne właściwości $R_{p_1, p_2}$ ( http://arxiv.org/abs/1404.1191 ), bazując na głównej analizie Fouriera dla $R_{p,0}$ autorzy: Ahlberg, Broman, Griffiths and Morris ( http://arxiv.org/abs/1108.0310 ).

Podsumowując, efekt tendencyjnego operatora $R_{p,0}$ na funkcji $f$ może być analizowany jako symetryczny operator hałasu w przestrzeni pomiaru stronniczości. Daje to słabą formę hiperkontraktacji, która zależy od tego, jak $\ell_2$ norma $f$ zmienia się po przełączeniu na wybór miary stronniczej $\mu$ zależny od $p$ .

— Amir
źródło

Możesz „zaakceptować” tę odpowiedź, aby pytanie nie wyskakiwało dalej (zrzeczenie się odpowiedzialności: jestem autorem na powiązanym papierze)

— Suresh Venkat