Liniowo niezależne współczynniki Fouriera

19

Podstawową właściwością przestrzeni wektorowych jest to, że przestrzeń wektorowa VF2n o wymiarze nd można scharakteryzować d liniowo niezależnymi wiązaniami liniowymi - to znaczy istnieją d liniowo niezależne wektory w1,,wdF2n , które są prostopadłe do V .

Z punktu widzenia Fouriera jest to równoważne ze stwierdzeniem, że funkcja wskaźnik 1V o V został d liniowo niezależne niezerowe współczynniki Fouriera. Należy zauważyć, że 1V ma w sumie 2d niezerowe współczynniki Fouriera, ale tylko d z nich jest liniowo niezależne.

Szukam przybliżonej wersji tej właściwości przestrzeni wektorowych. W szczególności szukam oświadczenia o następującej formie:

Niech SF2n będzie rozmiaru 2nd . Następnie funkcja wskaźnika 1S ma co najwyżej dlog(1/ε) liniowo niezależne współczynniki Fouriera, których wartość bezwzględna wynosi co najmniej ε .

To pytanie można rozpatrywać z perspektywy „Struktura vs. losowość” - takie stwierdzenie intuicyjnie mówi, że każdy duży zestaw można rozłożyć na sumę przestrzeni wektorowej i małego zbioru stronniczego. Jest dobrze znane, że każda funkcja można rozłożyć w „liniowej części”, które ma p o, l r ( 1 / ε ) duże współczynniki Fouriera oraz „części pseudolosowego”, który ma małe odchylenie . Moje pytanie dotyczy tego, czy część liniowa ma tylko logarytmiczną liczbę liniowo niezależnych współczynników Fouriera.f:F2nF2poly(1/ε)

Lub Meir
źródło
3
Cześć Czy mógłbyś podać odniesienie do twojego ostatniego twierdzenia, że ​​każda funkcja może zostać rozłożona na część liniową + część pseudolosową? Dzięki!
Henry Yuen,
2
Nie jestem pewien, gdzie to się pojawiło. Jest to bezpośrednia konsekwencja nierówności Parseval: z Parseval wynika, że ​​każda funkcja boolowska ma najwyżej znaki, których współczynniki Fouriera mają wartość bezwzględną co najmniej ε . Teraz weź część „liniową”, która będzie sumą ostatnich znaków (o tych samych współczynnikach), a „część pseudolosowa”, która będzie sumą wszystkich pozostałych znaków (o tych samych współczynnikach). 1/ε2ε
Lub Meir

Odpowiedzi:

12

Czy podany poniżej nie jest przykładem?

Niech będzie większością x 1 , , x 1 / ϵ 2 , co jest wskaźnikiem zbioru wielkości 2 n / 2 , więc d = 1 . Jednakże, f ( { i } ) = Θ ( ε ) dla 1 i 1 / ε 2 , więc trzeba 1 / ε 2f(x)x1,,x1/ϵ22n/2d=1f^({i})=Θ(ϵ)1i1/ϵ21/ϵ2 liniowo niezależne duże współczynniki Fouriera.

Per Austrin
źródło
9

Być może chcesz czegoś, co czasami nazywa się „Lemą Changa” lub „Lememą Talagranda” ... zwaną tutaj „Nierównością poziomu 1”: http://analysisofbooleanfunctions.org/?p=885

Oznacza to, że jeśli ma średnią 2 - d, to liczba liniowo niezależnych współczynników Fouriera, których kwadrat wynosi co najmniej γ 2 - d, wynosi co najwyżej O ( d / γ 2 ) . (Jest tak, ponieważ transformacja liniowa F 2 na wejściu nie zmienia średniej, więc zawsze możesz przesunąć liniowo niezależne znaki Fouriera do stopnia-1.)1S2dγ2dO(d/γ2)F2

Ryan O'Donnell
źródło
Wielkie dzięki! Jest zdecydowanie zbliżony do tego, czego szukałem, ale dla aplikacji, o której myślałem, kluczowe znaczenie miała zależność logarytmiczna od (co w twoim zapisie oznaczałoby również zależność logarytmiczną od γ ). Niestety, przykład Per pokazuje, że nie jest to możliwe. ϵγ
Lub Meir