Warum funktioniert die Fourier-Analyse von Booleschen Funktionen?

Im Laufe der Jahre habe ich mich daran gewöhnt, dass viele TCS-Theoreme mithilfe der diskreten Fourier-Analyse bewiesen wurden. Die Walsh-Fourier (Hadamard) -Transformation ist in praktisch jedem Teilbereich von TCS nützlich, einschließlich Eigenschaftstests, Pseudozufälligkeit, Kommunikationskomplexität und Quantencomputing.

Ich habe mich zwar daran gewöhnt, die Fourier-Analyse von Booleschen Funktionen als sehr nützliches Werkzeug zu verwenden, wenn ich ein Problem anpacke, und obwohl ich eine ziemlich gute Vorstellung davon habe, für welche Fälle die Fourier-Analyse wahrscheinlich einige gute Ergebnisse liefern würde. Ich muss zugeben, dass ich nicht wirklich sicher bin, was diesen Basiswechsel so nützlich macht.

Hat jemand eine Ahnung, warum die Fourier-Analyse beim Studium der TCS so fruchtbar ist? Warum werden so viele scheinbar schwierige Probleme gelöst, indem die Fourier-Erweiterung geschrieben und einige Manipulationen ausgeführt werden?

Bemerkung: Meine bisherige Hauptintuition, so dürftig es auch sein mag, ist, dass wir ein ziemlich gutes Verständnis dafür haben, wie sich Polynome verhalten, und dass die Fouriertransformation eine natürliche Sichtweise auf eine Funktion als multilineares Polynom ist. Aber warum gerade diese Basis? Was ist an der Basis der Paritäten so einzigartig?

Hier ist meine Sichtweise, die ich von Guy Kindler gelernt habe, obwohl jemand mit mehr Erfahrung wahrscheinlich eine bessere Antwort geben kann: Betrachten Sie den linearen Raum der Funktionen , und betrachte einen linearen Operator der Form (für ), der eine Funktion wie oben auf die Funktion f ( x + w ) abbildet . In vielen Fragen des TCS besteht ein grundsätzlicher Bedarf, die Auswirkungen solcher Operatoren auf bestimmte Funktionen zu analysieren.σ w w ∈ { 0 , 1 } n f ( x $f: \{0,1\}^n\to\mathbb{R}$$\sigma_w$$w\in\{0,1\}^n$$f(x)$$f(x+w)$

Der Punkt ist nun, dass die Fourier-Basis die Basis ist, die alle diese Operatoren gleichzeitig diagonalisiert, was die Analyse dieser Operatoren viel einfacher macht. Allgemeiner ausgedrückt diagonalisiert die Fourier-Basis den Faltungsoperator, der auch vielen dieser Fragen zugrunde liegt. Somit ist die Fourier-Analyse wahrscheinlich immer dann effektiv, wenn diese Operatoren analysiert werden müssen.

Die Fourier-Analyse ist übrigens nur ein Sonderfall der Darstellungstheorie endlicher Gruppen. Diese Theorie betrachtet den allgemeineren Raum der Funktionen wobei G eine endliche Gruppe ist, und Operatoren der Form σ h (für h ∈ G ), die f ( x ) auf f ( x ⋅ h ) abbilden , The theory Auf diese Weise können Sie eine Grundlage finden, die die Analyse solcher Operatoren erleichtert - auch wenn Sie bei allgemeinen Gruppen die Operatoren nicht wirklich diagonalisieren müssen.$f:G\to \mathbb{C}$$G$$\sigma_h$$h\in G$$f(x)$$f(x\cdot h)$

Hier könnte eine andere Einstellung zu dieser Frage sein.

Unter der Annahme, dass die pseudo-boolesche Funktion k-begrenzt ist, kann die Walsh-Polynomdarstellung der Funktion in k Unterfunktionen zerlegt werden. Alle linearen Terme werden in einer Unterfunktion zusammengefasst, alle paarweisen Wechselwirkungen in einer Unterfunktion, dann die 3-Wege-Wechselwirkungen usw.

Jede dieser Unterfunktionen ist eine "Elementarlandschaft" und somit ist jede der Unterfunktionen ein Eigenvektor der Laplace-Adjazenzmatrix (dh der Nachbarschaft Hamming-Abstand 1). Jede Unterfunktion hat eine entsprechende "Wellengleichung", wie sie in allen Elementarlandschaften vorkommt. Außer jetzt gibt es k Wellengleichungen, die in Kombination wirken.

Durch die Kenntnis der Wellengleichungen ist es möglich, den entsprechenden Suchraum relativ genau statistisch zu charakterisieren. Sie können den Mittelwert und die Varianz berechnen und über beliebige (exponentiell große) Hamming-Bälle und über beliebige Hyperebenen des Suchraums schiefen.

Siehe Peter Stadlers Arbeit über Elementare Landschaften.

Andrew Sutton und ich (Darrell Whitley) haben an diesen Methoden gearbeitet, um lokale Suchalgorithmen für die pseudo-boolesche Optimierung zu verstehen und zu verbessern. Mithilfe der Walsh-Polynome können Sie automatisch Verbesserungsschritte für lokale Suchalgorithmen identifizieren. Es ist niemals notwendig, Nachbarschaften des Suchraums zufällig aufzulisten. Die Walsh-Analyse kann Ihnen direkt mitteilen, wo sich die Verbesserungsschritte befinden.

Eine gute Antwort auf diese Frage gibt es wahrscheinlich noch nicht, da es sich um ein relativ junges und sehr aktives Forschungsgebiet handelt. Ingo Wegeners umfassendes Buch über Boolesche Funktionen aus dem Jahr 1987 hat beispielsweise nichts zu diesem Thema (außer der Analyse der Schaltungskomplexität der DFT).

Eine einfache Anschauung oder Vermutung ist, dass große Fourier-Koeffizienten höherer Ordnung das Vorhandensein von Unterfunktionen anzeigen, die viele Eingangsvariablen berücksichtigen müssen und daher viele Gatter erfordern. Das heißt, die Fourier-Expansion ist offensichtlich eine natürliche Methode, um die Härte einer Booleschen Funktion quantitativ zu messen. habe dies nicht direkt bewiesen gesehen aber denke es ist in vielen ergebnissen angedeutet. Beispielsweise kann die untere Grenze von Khrapchenkos mit Fourier-Koeffizienten in Beziehung gesetzt werden. [1]

Eine andere grobe Analogie kann bis zu einem gewissen Grad aus EE oder anderen technischen Bereichen übernommen werden, in denen die Fourier-Analyse in großem Umfang angewendet wird. Es wird häufig für EE-Filter / Signalverarbeitung verwendet . Die Fourier-Koeffizienten repräsentieren ein bestimmtes "Band" des Filters. Die Geschichte dort ist auch, dass "Rauschen" sich in bestimmten Frequenzbereichen zu manifestieren scheint, z. B. niedrig oder hoch. In CS ist eine Analogie zu "Rauschen" "Zufälligkeit", aber auch aus vielen Untersuchungen (die einen Meilenstein in z. B. [4] erreichten) geht hervor, dass Zufälligkeit im Grunde genommen mit Komplexität identisch ist. (In einigen Fällen taucht im selben Kontext auch "Entropie" auf.) Die Fourier-Analyse scheint geeignet zu sein, "Rauschen" auch in CS-Umgebungen zu untersuchen. [2]

Eine andere Intuition oder ein anderes Bild stammt aus der Voting / Choice-Theorie. [2,3] Es ist hilfreich, Boolesche Funktionen so zu analysieren, dass sie Unterkomponenten haben, die "voten" und das Ergebnis beeinflussen. dh die Analyse des Votings ist eine Art Zerlegungssystem für Funktionen. Dies nutzt auch einige Voting-Theorien, die Höhen der mathematischen Analyse erreichten und anscheinend vor der Verwendung vieler Fourier-Analysen von Booleschen Funktionen liegen.

Auch das Konzept der Symmetrie scheint in der Fourier-Analyse von größter Bedeutung zu sein. Je "symmetrischer" die Funktion ist, desto mehr wird der Fourier-Koeffizient aufgehoben und desto "einfacher" ist die Funktion zu berechnen. Aber je "zufälliger" und damit komplexer die Funktion ist, desto weniger heben sich die Koeffizienten auf. mit anderen Worten, Symmetrie und Einfachheit und umgekehrt Asymmetrie und Komplexität in der Funktion scheinen auf eine Weise koordiniert zu sein, die die Fourier-Analyse messen kann.

[1] Zur Fourier-Analyse von Booleschen Funktionen von Bernasconi, Codenotti, Simon

[2] Eine kurze Einführung in die Fourier-Analyse zum Booleschen Würfel (2008) von De Wolf

[3] Einige Themen zur Analyse boolescher Funktionen von O'Donnell

[4] Natürliche Beweise von Razborov & Rudich