Apakah Domain Frekuensi Itu Tempat yang Nyata?

• Discrete Fourier Transform (DFT) adalah alat inti dalam komunikasi dan pemrosesan sinyal, tetapi domain frekuensi bukan satu-satunya cara untuk menafsirkan realitas
• Dalam struktur seperti DCT, yang menghitung bin frekuensi dengan mengalikan sampel input dengan nilai fungsi basis, cukup dengan mengganti basis kita bisa membuat domain frekuensi dengan aturan berbeda
• Matriks Walsh menyediakan basis gelombang kotak yang hanya memakai +1 dan -1; jika sequency dan ortogonalitas diselaraskan, kita bisa bolak-balik antara domain waktu dan representasi frekuensi
• Matriks Hadamard adalah bentuk matriks Walsh yang disusun ulang; dibuat dengan Kronecker product atau operasi bit, lalu barisnya diurutkan kembali berdasarkan sequency untuk digunakan dalam WHT
• Input yang sama akan tersebar ke beberapa komponen harmonik dalam DCT dan terbagi menjadi komponen gelombang kotak dalam transformasi Walsh-Hadamard, menunjukkan bahwa DFT tidak memonopoli “kebenaran”

---

Meninjau ulang domain frekuensi Fourier

• Domain frekuensi adalah ruang matematis yang merepresentasikan sinyal kompleks dengan mengubahnya menjadi amplitudo dan fase gelombang sinus
• Berkat representasi ini, tugas pemrosesan sinyal yang sulit ditangani langsung di domain waktu atau domain spasial dapat dilakukan dengan lebih mudah
• DFT memainkan peran sentral dalam komunikasi dan pemrosesan sinyal, tetapi apakah penafsiran yang mengubah gelombang kotak menjadi jumlah harmonik sinus berorde ganjil adalah satu-satunya penafsiran realitas merupakan persoalan terpisah
• Gelombang sinus banyak hadir di alam sehingga perangkat keluarga Fourier cocok untuk banyak pekerjaan, tetapi domain frekuensi yang terdefinisi dengan baik yang bekerja dengan aturan lain juga dapat dibuat

Memahami DCT sebagai fungsi basis

• Discrete Cosine Transform (DCT) dapat dilihat sebagai versi DFT yang disederhanakan dan khusus bilangan real
• DCT-II menghitung besar bin frekuensi tertentu F_k dengan mengalikan nilai input s_n dengan nilai dari rumus kosinus tertentu, lalu menjumlahkannya
• Intinya adalah fungsi basis yang membuat gelombang kosinus pada frekuensi yang sesuai dengan nomor bin DCT saat ini
• Jika digeneralisasi, strukturnya menjadi B(k, n) yang mengembalikan multiplier berdasarkan k dan n, lalu multiplier itu dikalikan dengan sampel input dan dijumlahkan
• Dari sudut pandang perangkat lunak, B(k, n) dapat dilihat sebagai array lookup; secara matematis, sebagai matriks
• Pada matriks basis DCT dengan N=16, baris pertama k=0 adalah komponen DC yang setara dengan 0Hz, berupa kosinus yang semua nilainya +1.00
• Baris-baris berikutnya berbentuk kosinus yang berubah makin cepat, seperti setengah periode, satu periode, satu setengah periode

Basis gelombang kotak dan matriks Walsh

• Fungsi basis yang memecah sinyal bukan dengan frekuensi sinus, melainkan gelombang kotak, dapat dibuat dengan matriks Walsh
• Matriks Walsh terdiri dari gelombang-gelombang kotak yang bergerak dengan kecepatan berbeda, dan semua multiplier-nya adalah +1 atau -1
• Perhitungannya menjadi sederhana: membalik tanda sebagian data input lalu menjumlahkannya
• Matriks yang tampak sederhana ini pun harus memenuhi dua syarat
  • Setiap baris harus mengikuti urutan sequency, dengan satu pergantian tanda lebih banyak daripada baris sebelumnya
  • Untuk bisa bolak-balik dengan mulus antara data domain waktu dan representasi frekuensi, ortogonalitas harus dipertahankan
• Untuk membuat matriks Walsh secara langsung, mulai dari array N×N, dengan N harus berupa pangkat dua
  • Isi kolom pertama di kiri dengan +1 untuk semua baris
  • Buat kolom baru sebagai salinan cermin dari nilai yang ada, lalu bagi area yang baru ditambahkan menjadi beberapa segmen horizontal dan balik tanda pada sebagian segmen
  • Pada setiap iterasi, salin kolom dan tingkatkan jumlah segmen baris, lalu balik tanda secara bergantian

Membuat array Walsh dari matriks Hadamard

• Dalam literatur dan kode open source, array Walsh sering diturunkan dari matriks Hadamard, alih-alih dibuat langsung
• Matriks Hadamard adalah bentuk array Walsh dengan urutan baris yang diubah
  • Misalnya pada N=16, row #15 Walsh berpindah menjadi #1 di Hadamard, dan row #1 Walsh ditempatkan di #8
• Salah satu alasan konvensi ini adalah bahwa konstruksi Hadamard muncul lebih dulu secara historis, dan Walsh dibangun di atasnya
• Secara praktis, metode untuk membuat matriks Hadamard terdokumentasi lebih baik, dan ada juga cara manipulasi bit yang sederhana dan efisien
• Konstruksi ala buku teks dimulai dari array 1×1, lalu menyalin matriks sebelumnya H_{n-1} menjadi 4 tile
  • Kiri atas, kanan atas, dan kiri bawah disalin apa adanya
  • Kanan bawah semua tandanya dibalik
  • Notasi Kronecker product ⊗ digunakan untuk ekspansi ini, tetapi operasi sebenarnya adalah menyalin dan membalik tanda
• Setelah langkah konstruksi dilakukan n kali, ukuran matriks Hadamard selalu menjadi 2^n × 2^n
• Nilai Hadamard untuk sel tertentu dapat dihitung dengan menghitung x & y, lalu melihat apakah jumlah bit yang menyala pada hasilnya genap atau ganjil
  • Jika jumlah bit yang menyala ganjil, nilainya -1; jika genap, +1
  • Dalam kode C, ini diimplementasikan sebagai __builtin_popcount(x & y) % 2

Implementasi transformasi Walsh-Hadamard

• Untuk mengubah matriks Hadamard menjadi urutan Walsh yang intuitif, baris harus diurutkan berdasarkan sequency
• Cara paling sederhana adalah menghitung jumlah perubahan tanda pada setiap baris
• Cara manipulasi bit lain juga dimungkinkan
  • Buat Gray code dengan meng-XOR nomor baris Walsh dengan dirinya sendiri yang digeser 1 bit ke kanan
  • Balik urutan n bit terakhir untuk menghitung pemetaan baris Hadamard
• Dengan array Walsh yang dibuat seperti ini, jika basis dalam implementasi DCT diganti, kita bisa membuat “discrete square transform” beserta transformasi baliknya
• Secara teknis, transformasi ini adalah Walsh–Hadamard transform (WHT)
• Jika input contoh 1 1 1 1 5 5 5 5 diproses dengan DCT, komponen harmonik tersebar ke beberapa bin frekuensi
  • DCT : +24.00 -10.25 -0.00 +3.60 +0.00 -2.41 -0.00 +2.04
• Jika input yang sama diproses dengan transformasi gelombang kotak, komponen bukan nol hanya muncul di F_0 dan F_1
  • SQFT : +24.00 -16.00 +0.00 +0.00 +0.00 +0.00 +0.00 +0.00
• Transformasi balik isqft() memulihkan input aslinya
  • ISQFT : +1.00 +1.00 +1.00 +1.00 +5.00 +5.00 +5.00 +5.00

Perbandingan spektrogram dan posisi praktis

• Spektrogram DCT dan spektrogram Walsh-Hadamard dibandingkan menggunakan klip audio 11 detik yang diambil dari “DARE” oleh Gorillaz
• Transformasi Walsh-Hadamard efisien dihitung bahkan pada komputer berperforma rendah, cocok untuk jenis data tertentu, dan digunakan untuk beberapa kebutuhan niche
• Kesimpulannya bukan bahwa WHT harus dipakai lebih banyak, melainkan bahwa Discrete Fourier Transform tidak memonopoli kebenaran
• Spektrogram dihitung dengan DCT dan WHT dari file audio mono 44,1kHz
  • Window sampel input adalah 512
  • Transform stepover adalah 1
  • Ukuran array output sekitar 512 × 485k
  • Intensitas piksel menerapkan gamma sekitar 0.4 pada nilai absolut yang dinormalisasi
  • Gambar di-resize dengan Lanczos resampling, lalu dirender dengan colormap linear hitam–biru langit–putih
• Eksperimen penggunaan Walsh-Hadamard untuk kompresi gambar juga diperkenalkan di http://rotormind.com/blog/2019/hadamard-days-night/

[GN⁺]

Pendapat Hacker News

• Secara matematis, transformasi Fourier hanyalah cara untuk merepresentasikan sinyal waktu dengan basis vektor ortogonal tertentu
  Vektor perpindahan di permukaan bumi juga bisa direpresentasikan dengan basis arah utara/timur, atau dengan arah suatu jalan dan arah yang tegak lurus terhadapnya
  Sinyal yang bergantung pada waktu atau fungsi yang “rapi” berada dalam ruang vektor berdimensi tak hingga, sehingga sulit dibayangkan, tetapi matematika intinya bekerja dengan cara yang mirip
  Dalam transformasi Fourier, vektor basisnya adalah fungsi harmonik, dan ranah frekuensi adalah salah satu “peta” yang menampilkan sinyal sebagai kombinasi tak hingga banyaknya fungsi harmonik
  Peta dengan basis lain seperti transformasi Walsh–Hadamard sama nyatanya, dan representasi ranah waktu pun hanya salah satu dari banyak peta, meski lebih akrab bagi kita

  • Ini jawaban yang tepat, dan sebagai tambahan, transformasi Fourier berlaku bukan hanya untuk sinyal waktu, tetapi juga untuk fungsi yang kontinu per bagian, terdiferensialkan, dan dapat diintegralkan menurut Dirichlet
    Ada banyak penerapannya, seperti pemrosesan gambar, penyelesaian persamaan diferensial, dan perkalian cepat
    Secara matematis, transformasi semacam ini lossless, sehingga fungsi hasil transformasi memiliki informasi yang persis sama dengan fungsi aslinya, dan hanya dengan transformasinya pun kita bisa mengembalikannya ke bentuk semula
    Dalam rekayasa, orang sering melakukan transformasi untuk membuang informasi yang tidak diinginkan, seperti komponen frekuensi tertentu, sehingga poin ini sering menjadi kabur
    Pada akhirnya, ini hanyalah salah satu dari banyak sudut pandang untuk melihat sebuah fungsi
  • Dulu saya juga menganggapnya sebagai “basis lain”, tetapi sekarang menurut saya analogi itu agak berbahaya, atau setidaknya tidak sepenuhnya mencakup semuanya
    Khususnya dalam ruang multidimensi, transformasi Fourier multidimensi yang umum hanya bekerja dengan benar jika ruang tersebut memiliki metrik datar
    Jika mengingat bahwa alam semesta itu sendiri melengkung, ini tampak seperti tanda peringatan
    Baru-baru ini ada penelitian menarik yang menggeneralisasi deret Fourier ke kisi hiperbolik tertentu, dan hasilnya dimensi ruang Fourier bisa menjadi lebih tinggi daripada ruang posisi
    Selain itu, dimensi “ruang Fourier” ini bergantung pada cara diskretisasi kisi, sehingga suatu kisi 2 dimensi bisa memiliki ranah mirip frekuensi 4 dimensi, sementara kisi 2 dimensi lain bisa memiliki ranah mirip frekuensi 8 dimensi
    https://arxiv.org/abs/2108.09314 atau https://www.pnas.org/doi/full/10.1073/pnas.2116869119
  • Para astronom pada masa lalu percaya pada model alam semesta geosentris yang diberi episiklus, dan jika butuh akurasi lebih tinggi, mereka menambahkan lebih banyak episiklus
    Meski modelnya sepenuhnya salah, pada dasarnya mereka sedang memakai deret Fourier sebagai aproksimator fungsi
  • Secara umum saya setuju, tetapi semua basis ortonormal membagi spektrum frekuensi
    Bahkan jika memakai basis seperti polinom, pada akhirnya kita menyusun fungsi dari komponen frekuensi
    Basis Fourier istimewa karena setiap elemennya berkorespondensi dengan frekuensi tertentu
    Namun tiap basis lebih mirip sesuatu yang dirancang sesuai tujuan, dan transformasi basis bisa menyusun ulang spektrum dengan cara yang rumit untuk dianalisis
    Pada saat itu, kita akan menganalisis sifat lain seperti kehalusan
    Sebagian besar fungsi yang kita minati memiliki spektrum yang khas, tetapi basis Fourier tidak menjawab semua pertanyaan
  • Bukankah vektor basis tidak harus selalu saling tegak lurus?
    Selama ada sejumlah komponen tegak lurus, seperti utara dan timur laut, [n, e] juga bisa direpresentasikan dengan koordinat lain
    Koefisien konkretnya mungkin salah karena saya sedang asal hitung, tetapi intinya itu memungkinkan

• Saya teringat percakapan di depan papan tulis di grup sistem dinamis saat S2
  “Energi disuntikkan ke sistem dari kiri, lalu terdisipasi di sini di kanan”
  “Tapi sistemnya invarian terhadap rotasi, jadi tidak ada kiri dan kanan, kan?”
  “Saya bicara dalam ruang frekuensi”
  “Oh, saya kira maksudnya ruang nyata”
  “Kamu bodoh? Siapa yang berpikir dalam ruang nyata?”

  • Tunggu, apakah ruang frekuensi juga punya kiri dan kanan?
    Bukankah itu representasi abstrak, jadi tidak berhubungan langsung dengan kiri-kanan-atas-bawah dalam dimensi ruang?
  • Kalau semua rasa jijik yang saya pancarkan sepanjang hidup terhadap dunia akademik menara gading dikumpulkan, rasanya cukup untuk menggerakkan satu negara pulau kecil selama 10 tahun
  • Di program S2 memang saling memanggil bodoh, atau ini banyak didramatisasi?

• Basis Fourier itu unik karena fungsi basis eksponensial kompleks adalah vektor eigen dari sistem linear time-invariant (LTI)
  Transformasi lain tidak memiliki sifat ini
  Banyak sistem nyata seperti rangkaian, kanal komunikasi, dan antena bersifat LTI, dan berkat sifat ini sinyal yang dikirim pada frekuensi berbeda tidak saling mengganggu
  Karena itulah transformasi Fourier digunakan lebih luas daripada transformasi lain
  Dalam fisika kuantum juga ada keterkaitan yang memakai pasangan Fourier untuk fungsi gelombang posisi dan momentum, dan transformasi lain tidak memiliki sifat seperti ini

  • Saya terkejut hampir tidak ada yang mengangkat hal ini
    Dari latar belakang teknik elektro, banyak sistem diasumsikan linear atau hanya sangat lemah nonlinear untuk analisis, dan sinyal juga umumnya periodik, sehingga transformasi Fourier terasa alami
    Konvolusi menjadi perkalian, dan turunan waktu dari eksponensial kompleks menjadi operasi mengalikan dengan j*omega
    Melakukan perkalian jauh lebih baik daripada konvolusi dan turunan waktu
    Jika kita menerima bahwa “representasi Fourier dipakai karena praktis dalam situasi tertentu yang umum”, maka tidak mengejutkan juga jika transformasi matematis lain dipakai untuk masalah lain
  • Secara teknis, bukankah itu kasus khusus dari basis Laplace?
    Saya selalu heran banyak kuliah tidak benar-benar membahas transformasi Laplace dua sisi yang paling umum, lalu langsung beralih dari transformasi Fourier dua sisi ke transformasi Laplace satu sisi
    https://en.wikipedia.org/wiki/Two-sided_Laplace_transform

• Jika ditanya apakah ini “tempat yang nyata”, saya teringat sebuah eksperimen optik dulu
  Jika sebuah gambar dilewatkan melalui beberapa lensa, terbentuk bidang frekuensi, lalu gambar itu diproyeksikan ke layar setelah melewati lensa lagi
  Jika sebagian dari bidang frekuensi itu ditutup, gambarnya berubah
  Eksperimennya sangat sulit ditangani, dan saya sangat berterima kasih kepada Dr Bruce Sinclair dari St Andrew’s
  Bekerja di laboratorium fisika membuat kita melihat bagaimana benda-benda bekerja, tetapi ketika meninjau teorinya lagi beberapa bulan setelah eksperimen, kita bisa cukup tersesat

  • Bukankah bidang frekuensi memang selalu terbentuk?
    Jadi tampaknya itu berlanjut ke hal-hal seperti apertur membatasi resolusi, dan munculnya diffraction spike pada teleskop reflektor
  • Ini juga bisa dilakukan dengan perangkat lunak: https://imagemagick.org/Usage/fourier/#noise_removal
  • Sifat optik yang memungkinkan kita memperoleh representasi domain frekuensi cukup berguna dalam berbagai metode mikroskopi dan spektroskopi berbasis sumber cahaya
  • Itu adalah optika Fourier
    Schlieren juga bekerja dengan cara seperti ini

• Generalisasi DFT lain yang menarik adalah transformasi Lomb-Scargle
  Tidak memerlukan interval pengukuran yang tetap di domain waktu
  Sering dipakai untuk menemukan frekuensi sinyal periodik ketika interval pengukuran tidak seragam, seperti dalam astrofisika
  https://iopscience.iop.org/article/10.3847/1538-4365/aab766 adalah pengantar umum, dan https://docs.astropy.org/en/stable/timeseries/lombscargle.ht... menjelaskan dengan baik cara memakainya di library astropy Python

  • Belakangan saya sering berpikir apakah merepresentasikan data Prometheus dalam domain frekuensi akan berguna untuk memvisualisasikan pola akses mingguan, harian, dan tahunan dalam capacity planning
    Autoscaling bisa membantu menghindari penurunan performa yang bersifat insiden, tetapi tidak memberi tahu berapa anggaran tahunan yang seharusnya dan alasannya
    Namun data Prometheus sulit disebut benar-benar memiliki interval sampling
    Sekalipun tiap mesin dalam kluster melaporkan pada interval tetap, mereka tidak saling tersinkronisasi

• Dari sudut pandang lain, koklea bisa dilihat sebagai implementasi “nyata” dari transformasi Fourier
  https://www.britannica.com/science/sound-physics/The-ear-as-...

  • Koklea justru mendukung inti tulisan tersebut
    Memang ia mengubah ke domain frekuensi, tetapi tidak melakukan atau mendekati transformasi Fourier
    Transformasi domain waktu→frekuensi yang “diimplementasikan” koklea lebih dekat ke transformasi wavelet
    Menafsirkan koklea sebagai transformasi Fourier mirip dengan kesalahan mengira sel kerucut mata hanya merespons cahaya merah, hijau, dan biru
    Kenyataannya, setiap sel merespons secara berbeda di sepanjang rentang frekuensi tertentu
    Sel kerucut memuncak di wilayah frekuensi rendah, menengah, dan tinggi lalu menurun di kedua sisi, sementara sel rambut koklea memiliki kurva respons yang lebih mirip wavelet, dengan puncak sekunder pada harmonik dari frekuensi puncaknya
    Saya bukan ahli, hanya amatir antusias, jadi saya berharap seseorang yang lebih tahu dapat mengoreksi
  • Mudah lupa betapa kuatnya biologi berakar pada fisika
    Saat kuliah, lini sel punca kami pernah bermasalah karena berdiferensiasi menjadi tulang; ternyata kekakuan lingkungan adalah sinyal yang bisa dirasakan sel punca
    Dengan kata lain, cawan kultur yang keras seolah memberi tahu sel bahwa mereka harus menjadi sel tulang

• Di tulisan itu disebutkan bahwa “untuk mengurutkan baris matriks Hadamard berdasarkan sequency, saya tidak tahu algoritme yang lebih elegan daripada menghitung jumlah persilangan nol”; setelah melihat matriksnya dan menebak polanya, ternyata itu sudah merupakan metode yang dikenal
  Menurut https://en.wikipedia.org/wiki/Walsh_matrix, pengurutan sequency pada matriks Walsh dapat diperoleh dengan terlebih dahulu menerapkan permutasi bit-reversal pada matriks Hadamard, lalu menerapkan permutasi Gray-code

• Tulisan itu mengajukan pertanyaan yang sangat umum dan filosofis, tetapi kemudian mengatakan bahwa karena kita bisa menemukan basis ortogonal dan transformasi lain, domain frekuensi tidak terlalu istimewa
  Meski begitu, saya menganggap domain frekuensi dan transformasi Fourier lebih istimewa daripada banyak transformasi lain
  Karena keduanya dapat diamati langsung di alam
  Misalnya, lensa melakukan transformasi Fourier dua dimensi atas gambar masukan yang dibawa oleh cahaya paralel, dan kita bisa melihatnya di layar
  Selain itu, kita bisa mengukur panjang gelombang atau frekuensi cahaya dengan memproyeksikan keluaran kisi atau prisma ke CCD; ini juga merupakan pengukuran langsung domain frekuensi
  Pengukuran serupa juga mungkin pada gelombang RF

• Gelombang sinus istimewa karena merupakan solusi alami dari persamaan gelombang Helmholtz
  Gelombang kotak juga punya masalah lain seperti energi tak hingga
  Tulisan ini mungkin masuk akal bagi matematikawan atau ilmuwan komputer, tetapi melewatkan fisika mendasar dari suara dan gelombang

  • Gelombang sinus juga istimewa karena merupakan fungsi eigen dari operator diferensial
    Hasil fisiknya kemungkinan besar merupakan konsekuensi dari sifat itu
    Pada akhirnya, pelajaran inti matematika modern adalah bahwa melihat objek dari berbagai sudut pandang itu berguna
  • Benar
    Sangat banyak objek fisik adalah osilator harmonik, dan ini memiliki dasar yang cukup fundamental dalam fisika
    Saya bisa memikirkan banyak tempat lain untuk memakai analisis Fourier, tetapi gelombang sinus secara fisik lebih “nyata”, dan pernyataan bahwa apa pun dapat direpresentasikan dengan himpunan basis mana pun lebih dekat ke sesuatu yang “valid”
    Kata “nyata” tampaknya memberi kesan bahwa ada osilator sungguhan di balik fenomenanya
    Gelombang kotak kurang fisik karena diskontinuitas pada sinyal maupun turunannya, dan alam benar-benar tidak menyukai diskontinuitas
  • Domain frekuensi membuat matematika menjadi jauh lebih mudah dalam operasi linear time-invariant yang secara aproksimatif menggambarkan banyak sistem yang ada di alam
    Misalnya, fenomena Gibbs muncul secara alami dari transformasi Fourier balik atas respons frekuensi yang membuat semua frekuensi di atas frekuensi cutoff tertentu menjadi 0
    Saya penasaran bagaimana domain frekuensi dari gelombang kotak akan menjelaskan fenomena Gibbs
    Mungkin harmonik dari frekuensi gelombang kotak dasar akan muncul, seperti ketika sistemnya nonlinear

• Saat mempelajari fisika dan matematika tingkat sarjana, saya sampai pada kesimpulan bahwa mengetahui nilai fungsi f(x) untuk tak terhingga banyaknya x setara dengan mengetahui komponen frekuensi dari f pada tak terhingga banyaknya frekuensi
  Secara filosofis, kedua representasi itu sama-sama “nyata”
  Hanya saja, beberapa masalah lebih mudah diselesaikan dalam satu representasi dibanding yang lain

  • Sepenuhnya setuju
    Mengubah dari domain waktu ke domain frekuensi itu seperti mengganti sistem koordinat
    Sinyal yang memiliki satu puncak sempit di domain waktu dapat direpresentasikan secara sangat kecil dan sparse sebagai satu delta pada posisi puncak, tetapi di domain frekuensi tidak muncul representasi yang sepadat itu
    Sebaliknya, sinyal sinus di domain waktu tidak compact di sana, tetapi di domain frekuensi cukup dengan beberapa delta saja
    Waktu dan frekuensi adalah dua cara untuk merepresentasikan hal yang sama, dan dalam beberapa kasus satu domain lebih mudah, sementara dalam kasus lain sebaliknya
    Dapat dibuktikan bahwa sesuatu yang terbatas di domain waktu menjadi tak terbatas di domain frekuensi, dan sebaliknya juga berlaku
    Jadi sesuatu yang compact di satu domain akan selalu menyebar ketika berpindah ke domain lain
    Dalam mekanika kuantum, posisi dan momentum adalah variabel konjugat seperti waktu dan frekuensi di atas, sehingga jika posisi terbatas, momentum menjadi tak terbatas, dan sebaliknya juga berlaku
    Inilah gagasan inti dari prinsip ketidakpastian Heisenberg