гиперкубаға арналған Фурье коэффициенттерінің векторының $ \ ell_1 $ нормасы

$ G $ - $ 2 ^ d $ бойынша қалыпты hypercube graph болсын. Бұл Cayley графикасы және оның меншікті мәні $ \ lambda_r = 1-2 \ frac {| r |} {d} $ әр $ r \ in \ {0,1 \} ^ d $ .

Given a function $f:[-1,1] \rightarrow[0,1]$, we can define for every $a \in \{0,1\}^d$ the Fourier coefficient $$\hat{h}_a = \sum_{r \in \{0,1\}^d}f\left(1-2\frac{|r|}{d}\right)(-1)^{\left}$$ Now, let $v$ be the vector of size $2^d$ so that $v_i = \hat{h}_i$ for $i \in \{0,1\}^d$.

Мен $ f $ бойынша $ \ frac {1} {2 ^ {d}} \ | v \ | _1 $ үстіне үстемдік іздеймін.

Сіздің көмегіңіз үшін үлкен рахмет.

4
@SashoNikolov, түсініктемеіңіз үшін алғыс айтамыз. Бұл $ f (A) $ индукциясының шексіздік нормасын байланыстыру қажеттілігіне негізделген, мұнда $ A $ - Hypercube-ның қалыпты араласқан матрицасы. $ f $ өзі - бұл қалыпты Féjer ядросы . Мен Фурье коэффициентіне қосылу мәселені жеңілдетуі мүмкін деп ойладым.
қосылды автор Dan R, көзі
Рахмет @arnab, бірақ мен дискреттеу мұнда көмектеспейді. Алайда, бұл нәтиже менің түйсігімді күшейтеді, жоғарғы шек $ d $.
қосылды автор Dan R, көзі
Бұл мәселе бір нәрсеге негізделген бе? $ F $ құрайтын $ r $ басқа симметриялы функциямен құра аласыз, бұл гиперкубаның өзіндік мәндері туралы не ерекше?
қосылды автор Sasho Nikolov, көзі
Егер $ f $ $ \ {0,1 \} $ болса, онда $ h (x) = f (1-2 | x |/d) $ симметриялық логикалық функция болып табылады, a href = «http://www.cs.mcgill.ca/~aada/papers/AFH2012.pdf» rel = «nofollow noreferrer»> cs.mcgill.ca/~aada/papers/AFH2012.pdf .
қосылды автор Juan M. Bello-Rivas, көзі

1 жауаптар

$ H (x) = f (1-2 | x |/$) ретінде анықталған $ h: \ {{1 \} \ n \ to [-1, + 1] $ симметриялы функциясының спектрлік норма туралы мәселе. г) $. (Мен $ [0,1] $ орнына $ [- 1, + 1] $ ауқымын қабылдадым, ол тиісті лента арқылы wlog болып табылады.)

Ada, Fawzi and H. Hatami show that for any boolean $g: \{0,1\}^n \to \{-1, +1\}$, $$\log \|\hat{g}\|_1 = \Theta\left(r(g) \log\left(\frac{n}{r(g)}\right)\right)$$ where $r(g) = \max(r_0(g), r_1(g))$ and $r_0(g)$ and $r_1(g)$ are minimum integers such that $g$ is either constant or perfectly correlated with parity or anti-parity for $x$ with $|x| \in [r_0(g), n-r_1(g)]$.

Енді қағаздағы лемма 3.1 дәлелін қараңыз. Бұл қарапайым аргумент $ \ {- 1, + 1 \} $ орнына $ h $ картасына $ [- 1, + 1] $ функцияларын атқарады. Мәселен, сол үстіңгі қабат сіздің ісіңізге де жауап береді. Бұл жоғарғы нүкте, кем дегенде, логикалық функциялар үшін тығыз, бірақ мен логикалық емес $ h $ үшін осындай жалпы төменгі шекара бар екенін білмеймін.

3
қосылды
Сіз дұрыс айтасыз, мен оны сағындық. Көп рақмет.
қосылды автор Dan R, көзі