Dlaczego analiza Fouriera funkcji boolowskich „działa”?

Przez lata przyzwyczaiłem się do tego, że wiele twierdzeń TCS zostało udowodnionych przy użyciu dyskretnej analizy Fouriera. Transformacja Walsha-Fouriera (Hadamarda) jest przydatna w praktycznie każdym podpolu TCS, w tym w testowaniu właściwości, pseudolosowości, złożoności komunikacji i obliczeniach kwantowych.

Podczas gdy czułem się dobrze, stosując analizę Fouriera funkcji boolowskich jako bardzo przydatne narzędzie, gdy rozwiązuję problem, i chociaż mam całkiem niezłe przeczucie, dla których przypadki zastosowania analizy Fouriera prawdopodobnie przyniosłyby jakieś dobre wyniki; Muszę przyznać, że nie jestem do końca pewien, co sprawia, że ​​ta zmiana podstawy jest tak przydatna.

Czy ktoś ma intuicję, dlaczego analiza Fouriera jest tak owocna w badaniu TCS? Dlaczego tak wiele pozornie trudnych problemów rozwiązuje się, pisząc rozszerzenie Fouriera i wykonując pewne manipulacje?

Uwaga: moją dotychczasową intuicją, choć skromną, jest to, że dobrze rozumiemy, jak zachowują się wielomiany, i że transformacja Fouriera jest naturalnym sposobem patrzenia na funkcję jako wielomian wielomianowy. Ale dlaczego konkretnie ta baza? co jest takiego wyjątkowego w bazie parytetów?

$f: \{0,1\}^n\to\mathbb{R}$$\sigma_w$$w\in\{0,1\}^n$$f(x)$$f(x+w)$. W wielu pytaniach TCS istnieje podstawowa potrzeba analizy wpływu, jaki tacy operatorzy wywierają na niektóre funkcje.

Chodzi o to, że podstawa Fouriera jest podstawą, która przekątna wszystkie te operatory jednocześnie, co znacznie ułatwia analizę tych operatorów. Mówiąc bardziej ogólnie, podstawa Fouriera przekątna operatora splotu, który również leży u podstaw wielu z tych pytań. Dlatego analiza Fouriera może być skuteczna zawsze, gdy trzeba przeanalizować te operatory.

$f:G\to \mathbb{C}$$G$$\sigma_h$$h\in G$$f(x)$$f(x\cdot h)$

Oto kolejne spojrzenie na to pytanie.

Zakładając, że pseudo funkcja boolowska jest ograniczona przez k, wielomianowa reprezentacja funkcji Walsha może zostać rozłożona na podfunkcje k. Wszystkie warunki liniowe są zebrane w jedną podfunkcję, wszystkie interakcje parami w jedną podfunkcję, a następnie interakcje 3-kierunkowe itp.

Każda z tych podfunkcji jest „krajobrazem elementarnym”, a zatem każda z podfunkcji jest wektorem własnym lapackiej macierzy przylegania (tj. Sąsiedztwo w odległości Hamminga 1). Każda podfunkcja ma odpowiadające „Równanie fali” typu występującego we wszystkich elementarnych krajobrazach. Z wyjątkiem teraz istnieją k Równania falowe, które działają w połączeniu.

Znajomość równań falowych umożliwia dość dokładną charakterystykę statystyczną odpowiadającej przestrzeni wyszukiwania. Możesz obliczyć średnią, wariancję i pochylenie względem dowolnych (wykładniczo dużych) kul Hamminga i dowolnych hiperpłaszczyzn przestrzeni poszukiwań.

Zobacz pracę Petera Stadlera dotyczącą elementarnych krajobrazów.

Andrew Sutton i ja (Darrell Whitley) pracowaliśmy nad wykorzystaniem tych metod do zrozumienia i ulepszenia lokalnych algorytmów wyszukiwania dla pseudo-boolowskiej optymalizacji. Za pomocą wielomianów Walsha można automatycznie identyfikować usprawnienia ruchów dla lokalnych algorytmów wyszukiwania. Nigdy nie ma potrzeby losowego wyliczania dzielnic przestrzeni wyszukiwania. Analiza Walsha może bezpośrednio wskazać, gdzie znajdują się ruchy poprawiające.

świetna odpowiedź na to pytanie prawdopodobnie jeszcze nie istnieje, ponieważ jest to stosunkowo młody i bardzo aktywny obszar badań. na przykład obszerna książka Ingo Wegeners na temat funkcji boolowskich z 1987 roku nie ma nic na ten temat (oprócz analizy złożoności obwodu DFT).

prosta intuicja lub przypuszczenie jest takie, że wydaje się, że duże współczynniki Fouriera wyższego rzędu wskazują na obecność podfunkcji, które muszą uwzględniać wiele zmiennych wejściowych, a zatem wymagają wielu bramek. tzn. ekspansja Fouriera jest najwyraźniej naturalnym sposobem na ilościowy pomiar twardości funkcji boolowskiej. nie widziałem tego bezpośrednio udowodnionego, ale myślę, że wskazało to na wiele wyników. np. dolna granica Khrapchenkos może być powiązana ze współczynnikami Fouriera. [1]

inną z grubsza analogię można wypożyczyć z EE lub innych dziedzin inżynierii do pewnego stopnia, w których szeroko stosuje się analizę Fouriera. jest często używany do filtrów / przetwarzania sygnałów EE . współczynniki Fouriera reprezentują określone „pasmo” filtra. istnieje również historia, że ​​„hałas” wydaje się objawiać w określonych zakresach częstotliwości, np. niskich lub wysokich. w CS analogią do „szumu” jest „przypadkowość”, ale także z wielu badań (osiągając kamień milowy np. [4]) wynika, że ​​losowość jest zasadniczo taka sama jak złożoność. (w niektórych przypadkach „entropia” pojawia się również w tym samym kontekście). Analiza Fouriera wydaje się być odpowiednia do badania „szumu” nawet w ustawieniach CS. [2]

inna intuicja lub obraz pochodzi z teorii głosowania / wyboru [2,3]. Pomocna jest analiza funkcji boolowskich jako posiadających podskładniki, które „głosują” i wpływają na wynik. tj. analiza głosowania jest rodzajem systemu dekompozycji funkcji. wykorzystuje to również pewną teorię głosowania, która osiągnęła szczyty analizy matematycznej i która najwidoczniej poprzedza wykorzystanie analizy Fouriera funkcji boolowskich.

również koncepcja symetrii wydaje się być najważniejsza w analizie Fouriera. im bardziej „symetryczna” jest funkcja, tym bardziej współczynnik Fouriera znosi się, a także „bardziej prosta” jest funkcja do obliczenia. ale także im bardziej „losowa”, a zatem bardziej złożona funkcja, tym mniej współczynników się znosi. innymi słowy symetria i prostota oraz odwrotnie asymetria i złożoność funkcji wydają się skoordynowane w sposób, który można zmierzyć analizą Fouriera.

[1] O analizie Fouriera funkcji boolowskich autorstwa Bernasconiego, Codenottiego, Simona

[2] Krótkie wprowadzenie do analizy Fouriera na temat kostki boolowskiej (2008) autorstwa De Wolf

[3] Niektóre tematy dotyczące analizy funkcji boolowskich autorstwa O'Donnella

[4] Dowody naturalne Razborova i Rudicha