Selama bertahun-tahun saya telah terbiasa melihat banyak teorema TCS terbukti menggunakan analisis Fourier diskrit. Transformasi Walsh-Fourier (Hadamard) berguna di hampir setiap subbidang TCS, termasuk pengujian properti, pseudorandomness, kompleksitas komunikasi, dan komputasi kuantum.
Sementara saya merasa nyaman menggunakan analisis Fourier dari fungsi Boolean sebagai alat yang sangat berguna ketika saya menangani masalah, dan meskipun saya memiliki firasat yang cukup bagus untuk kasus-kasus yang menggunakan analisis Fourier mungkin akan menghasilkan beberapa hasil yang bagus; Saya harus mengakui bahwa saya tidak begitu yakin apa yang membuat perubahan basis ini sangat berguna.
Apakah ada yang punya intuisi mengapa analisis Fourier begitu bermanfaat dalam studi TCS? Mengapa begitu banyak masalah yang tampaknya sulit diselesaikan dengan menulis ekspansi Fourier dan melakukan beberapa manipulasi?
Catatan: Intuisi utama saya sejauh ini, sedikit mungkin, adalah bahwa kita memiliki pemahaman yang cukup baik tentang bagaimana polinomial berperilaku, dan bahwa transformasi Fourier adalah cara alami untuk melihat suatu fungsi sebagai polinomial multinear. Tetapi mengapa secara khusus basis ini? apa yang begitu unik di dasar paritas?
sumber
Jawaban:
Inilah sudut pandang saya, yang saya pelajari dari Guy Kindler, meskipun seseorang yang lebih berpengalaman mungkin dapat memberikan jawaban yang lebih baik: Pertimbangkan ruang linear fungsi , dan pertimbangkan operator linear dari formulir σ w (untuk w ∈ { 0 , 1 } n ), yang memetakan fungsi f ( x ) seperti di atas ke fungsi f ( x + w )f: { 0 , 1 }n→ R σw w ∈ { 0 , 1 }n f( x ) f( x + w ) . Dalam banyak pertanyaan TCS, ada kebutuhan mendasar untuk menganalisis efek yang dimiliki operator tersebut pada fungsi tertentu.
Sekarang, intinya adalah bahwa basis Fourier adalah dasar yang mendiagonalisasi semua operator pada saat yang sama, yang membuat analisis operator tersebut menjadi lebih sederhana. Secara lebih umum, basis Fourier mendiagonalisasi operator konvolusi, yang juga mendasari banyak pertanyaan itu. Dengan demikian, analisis Fourier cenderung efektif setiap kali seseorang perlu menganalisis operator tersebut.
Omong-omong, analisis Fourier hanyalah kasus khusus dari teori representasi kelompok hingga. Teori ini mempertimbangkan ruang fungsi yang lebih umum mana G adalah grup hingga, dan operator dari bentuk σ h (untuk h ∈ G ) yang memetakan f ( x ) ke f ( x ⋅ h ) , Teori kemudian memungkinkan Anda untuk menemukan dasar yang membuat analisis operator seperti itu lebih mudah - meskipun untuk grup umum Anda tidak bisa benar-benar mendiagonalisasi operator.f: G → C G σh h ∈ G f( x ) f( x ⋅ h )
sumber
Ini mungkin jawaban lain untuk pertanyaan ini.
Dengan asumsi fungsi Boolean semu dibatasi k, representasi polinomial Walsh dari fungsi dapat didekomposisi menjadi subfungsi k. Semua istilah linear dikumpulkan menjadi satu subfungsi, semua interaksi berpasangan menjadi satu subfungsi, lalu interaksi 3 arah, dll.
Masing-masing dari subfungsi ini adalah "lanskap dasar" dan dengan demikian masing-masing subfungsi adalah vektor eigen dari matriks kedekatan Laplacian (yaitu, lingkungan Hamming distance 1). Setiap subfungsi memiliki "Persamaan Gelombang" yang sesuai dari jenis yang ditemukan di semua lanskap dasar. Kecuali sekarang ada k Persamaan Gelombang yang bertindak dalam kombinasi.
Mengetahui persamaan gelombang memungkinkan untuk mengkarakteristikkan ruang pencarian terkait secara statistik dengan cara yang agak tepat. Anda dapat menghitung mean dan varians dan condong lebih dari bola Hamming sewenang-wenang (eksponensial besar) dan lebih dari hyperplanes sewenang-wenang dari ruang pencarian.
Lihat karya Peter Stadler tentang Lanskap Dasar.
Andrew Sutton dan saya (Darrell Whitley) telah bekerja menggunakan metode ini untuk memahami dan meningkatkan algoritma pencarian lokal untuk optimasi pseudo-Boolean. Anda dapat menggunakan polinomial Walsh untuk secara otomatis mengidentifikasi peningkatan gerakan untuk algoritma pencarian lokal. Tidak pernah ada kebutuhan untuk menyebutkan secara acak lingkungan dari ruang pencarian. Analisis Walsh dapat langsung memberi tahu Anda di mana gerakan peningkatan berada.
sumber
jawaban yang bagus untuk pertanyaan ini mungkin belum ada karena ini merupakan area penelitian yang relatif muda dan sangat aktif. misalnya buku komprehensif Ingo Wegeners tentang fungsi boolean dari tahun 1987 tidak membahas masalah tersebut (kecuali untuk menganalisis kompleksitas rangkaian DFT).
intuisi atau dugaan sederhana adalah tampak bahwa koefisien Fourier besar orde tinggi menunjukkan adanya subfungsi yang harus memperhitungkan banyak variabel input dan karenanya memerlukan banyak gerbang. yaitu ekspansi Fourier tampaknya merupakan cara alami untuk mengukur kekerasan fungsi boolean secara kuantitatif. belum melihat ini langsung terbukti tetapi berpikir itu mengisyaratkan dalam banyak hasil. misalnya Khrapchenkos batas bawah dapat dikaitkan dengan koefisien Fourier. [1]
analogi kasar lainnya dapat dipinjam dari EE atau bidang teknik lainnya sampai tingkat tertentu di mana analisis Fourier digunakan secara luas. sering digunakan untuk filter EE / pemrosesan sinyal . koefisien Fourier mewakili "pita" tertentu dari filter. cerita di sana juga bahwa "noise" tampaknya memanifestasikan dalam rentang frekuensi tertentu, misalnya rendah atau tinggi. dalam CS analogi dengan "noise" adalah "keacakan" tetapi juga jelas dari banyak penelitian (mencapai tonggak dalam misalnya [4]) bahwa keacakan pada dasarnya sama dengan kompleksitas. (dalam beberapa kasus "entropi" juga muncul dalam konteks yang sama.) Analisis Fourier tampaknya cocok untuk mempelajari "noise" bahkan dalam pengaturan CS. [2]
intuisi atau gambar lain berasal dari teori pemilihan / pemilihan. [2,3] akan sangat membantu untuk menganalisis fungsi boolean sebagai memiliki subkomponen yang "memilih" dan mempengaruhi hasilnya. yaitu analisis pemungutan suara adalah semacam sistem dekomposisi untuk fungsi. ini juga memanfaatkan beberapa teori pemungutan suara yang mencapai ketinggian analisis matematika dan yang tampaknya mendahului penggunaan banyak analisis Fourier dari fungsi boolean.
juga, konsep simetri tampaknya menjadi yang terpenting dalam analisis Fourier. semakin "simetris" fungsinya, semakin banyak koefisien Fourier yang dibatalkan, dan juga semakin "sederhana" fungsinya untuk menghitung. tetapi juga semakin "acak" dan karena itu semakin kompleks fungsinya, semakin sedikit koefisien yang dibatalkan. dengan kata lain simetri dan kesederhanaan, dan sebaliknya asimetri dan kompleksitas dalam fungsi tampaknya dikoordinasikan sedemikian rupa sehingga analisis Fourier dapat diukur.
[1] Pada analisis Fourier fungsi boolean oleh Bernasconi, Codenotti, Simon
[2] Pengantar singkat untuk analisis Fourier pada kubus Boolean (2008) oleh De Wolf
[3] Beberapa topik tentang analisis fungsi boolean oleh O'Donnell
[4] Bukti alami oleh Razborov & Rudich
sumber