28 Kompleks Matrisler ve FFT

Hermitian, unitary, Fourier matrisi → n log n hızlandırma

Bölüm bilgisi

Strang’in videosu: YouTube — Lecture 26: Complex Matrices; FFT (≈48 dk)
OCW sayfası: MIT 18.06SC — Lecture 26
Okuma süresi: ≈40 dk

28.1 Bu Derste Ne Var?

Kompleks uzunluk: $\mathbf{z}^H \mathbf{z}$ ($\mathbf{z}^H = \bar{\mathbf{z}}^T$).
Hermitian ($A^H = A$) — simetri kompleks karşılığı; unitary ($Q^H Q = I$) — ortogonal kompleks karşılığı.
Fourier matrisi $F_n$: $(F_n)_{jk} = W^{jk}$, $W = e^{2\pi i/n}$.
FFT: $n^2$ yerine $\frac{1}{2} n \log_2 n$.

“FFT multiplies by an n×n matrix in one half n log n steps.” — Strang, 45:07

flowchart LR
    CPLX["Kompleks vektör/matris"] --> H["Hermitian: Aᴴ = A<br/>(gerçel λ, dik q)"]
    CPLX --> U["Unitary: QᴴQ = I"]
    U --> F["Fourier matrisi Fₙ<br/>(F)ⱼₖ = Wʲᵏ"]
    F --> FFT["⭐ FFT<br/>F₂ₙ = [I D; I -D][Fₙ 0; 0 Fₙ]P"]
    FFT --> COST["n² → ½ n log₂ n<br/>(~200× n=1024)"]
    COST --> ML["Konvolüsyon hızlandırma<br/>Unitary RNN<br/>Fourier features"]

    style FFT fill:#fff3e0,stroke:#e67e22,stroke-width:3px
    style ML fill:#fce4ec,stroke:#c2185b,stroke-width:2px

flowchart LR
    CPLX["Kompleks vektör/matris"] --> H["Hermitian: Aᴴ = A<br/>(gerçel λ, dik q)"]
    CPLX --> U["Unitary: QᴴQ = I"]
    U --> F["Fourier matrisi Fₙ<br/>(F)ⱼₖ = Wʲᵏ"]
    F --> FFT["⭐ FFT<br/>F₂ₙ = [I D; I -D][Fₙ 0; 0 Fₙ]P"]
    FFT --> COST["n² → ½ n log₂ n<br/>(~200× n=1024)"]
    COST --> ML["Konvolüsyon hızlandırma<br/>Unitary RNN<br/>Fourier features"]

    style FFT fill:#fff3e0,stroke:#e67e22,stroke-width:3px
    style ML fill:#fce4ec,stroke:#c2185b,stroke-width:2px

Şekil 28.1: Kompleks → Hermitian/unitary → Fourier → FFT (n² → n log n).

Builder Notu — FFT ML’in Sessiz Devi

Konvolüsyon teoremi → büyük çekirdek konvolüsyon FFT ile $O(n \log n)$; WaveNet, FNO, diffusion.
Unitary RNN / ortogonal başlatma — $|\lambda| = 1$ → gradyan ne patlar ne söner.
Fourier features — NeRF positional encoding, FNO PDE çözücüler.
Divide-and-conquer deseni → Strassen, FlashAttention bloklama.

28.2 Kompleks Uzunluk — $\mathbf{z}^H \mathbf{z}$

$\mathbf{z}^T \mathbf{z}$ yanlış: $\mathbf{z} = (1, i)$ → $1 + i^2 = 0$ (saçma).

Doğrusu:

\[ \mathbf{z}^H \mathbf{z} = \bar{z}_1 z_1 + \cdots = \sum |z_i|^2 > 0 \]

$\mathbf{z} = (1, i)$ → $1 + 1 = 2$, uzunluk $\sqrt 2$.

28.3 Hermitian Matris — $A^H = A$

\[ A = \begin{pmatrix} 2 & 3+i \\ 3-i & 5 \end{pmatrix} \]

Köşegen gerçel.
Köşegen-dışı eşlenik çiftler.

Spektral teorem aynen: gerçel özdeğer + dik özvektör.

28.4 Unitary Matris — $Q^H Q = I$

Ortogonalin kompleks karşılığı. $Q^{-1} = Q^H$.

28.5 Fourier Matrisi $F_n$

\[ (F_n)_{jk} = W^{jk}, \quad W = e^{2\pi i/n}, \quad W^n = 1 \]

$F_4$ örneği ($W = i$):

\[ F_4 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} \]

import numpy as np

n = 4
W = np.exp(2j * np.pi / n)
F4 = np.array([[W**(j*k) for k in range(n)] for j in range(n)])
print("F4 =\n", np.round(F4, 4))

# Kolonlar Hermitian iç çarpımda dik
print("\nF4ᴴ F4 / n =\n", np.round(F4.conj().T @ F4 / n, 4))   # = I

28.6 Ters Matris

Kolonlar $\sqrt n$ uzunluğunda, Hermitian iç çarpımda dik → $\frac{1}{\sqrt n} F_n$ unitary:

\[ F_n^{-1} = \frac{1}{n} F_n^H \]

Ters dönüşüm bedava.

28.7 FFT Fikri — $F_{2n}$ ile $F_n$

$(W_{2n})^2 = W_n$ → $F_{2n}$ iki $F_n$’e ayrıştırılabilir:

\[ F_{2n} = \begin{pmatrix} I & D \\ I & -D \end{pmatrix} \begin{pmatrix} F_n & 0 \\ 0 & F_n \end{pmatrix} P \]

$P$: çift-tek ayırma permütasyonu.
Orta: iki bağımsız $F_n$ (köşegen blok).
$D = \text{diag}(1, W, W^2, \ldots, W^{n-1})$ — düzeltme.

Özyinelemeli: her $F_n$ tekrar ikiye böl → 1-noktaya iner.

28.8 $n^2 \to \frac{1}{2} n \log_2 n$ ⭐

$\log_2 n$ adım, her birinde $\sim n/2$ çarpma:

\[ \text{FFT maliyeti} = \frac{1}{2} n \log_2 n \]

$n$	Naif ($n^2$)	FFT
1024	$\sim 10^6$	5,120
Oran	—	~200×

“We’ve reduced the calculation by a factor of 200 just by factoring the matrix properly.” — Strang, 46:25

28.9 Bu Dersin Özeti

$\mathbf{z}^H \mathbf{z} = \sum |z_i|^2$.
Hermitian iç çarpım $\mathbf{y}^H \mathbf{x}$.
Hermitian $A^H = A$ — gerçel köşegen + eşlenik çiftler.
Unitary $Q^H Q = I$.
$F_n$: $(F_n)_{jk} = W^{jk}$.
$F_n^{-1} = \frac{1}{n} F_n^H$.
FFT ayrıştırması.
$\frac{1}{2} n \log_2 n$.

Tek bir cümle

Kompleks dünyada “transpoze + eşlenik” (Hermitian); Fourier matrisi $F_n$ kolonları unitary; FFT $F_{2n} = [I\,D / I\,-D][F_n / F_n]P$ özyinelemesi $n^2$’den $\frac{1}{2} n \log_2 n$’e iner — modern hesaplamanın temel hızlandırması.

28.10 Kontrol Soruları

Soru 1: z = (1, i) uzunluğu? zᵀz neden yanlış?

$\mathbf{z}^T \mathbf{z} = 1 - 1 = 0$ (yanlış). $\mathbf{z}^H \mathbf{z} = 2$, uzunluk $\sqrt 2$.

Soru 2: Hermitian matrisin köşegeninde ne tür sayılar?

Gerçel — kendi eşleniğine eşit olmalı.

Soru 3: F₄’te W kuvvetleri?

$W = i$. Kuvvetler: $i, -1, -i, 1$. Birim çember çeyrek turları.

Soru 4: n = 1024 FFT vs naif?

FFT: $5120$. Naif: $\sim 10^6$. Oran ~200×.

28.11 Egzersizler

Egzersiz 1. $\mathbf{z} = (2, 1+i, i)$ uzunluk.

Egzersiz 2. $A = ((1, 2-i), (2+i, 3))$ Hermitian mi?

Egzersiz 3. $F_2$ ($W = -1$) yaz. (Hadamard.)

Egzersiz 4. (Python) np.fft.fft ile çarpım karşılaştır.

Egzersiz 5. İspatla: Unitary $Q$ uzunluk korur ($\|Q\mathbf{z}\| = \|\mathbf{z}\|$). (İpucu: $\mathbf{z}^H Q^H Q \mathbf{z}$.)

28.12 Sonraki Ders İçin Hazırlık

Ders 27: Pozitif Tanımlı Matrisler ve Minimumlar

Enerji testi: $\mathbf{x}^T A \mathbf{x} > 0$.
Optimizasyon, eliptik geometri.

Ders 27 öncesi

Egzersiz 5 (uzunluk koruma).
fft ile dene.

28.13 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım
Kompleks uzunluk	$\mathbf{z}^H \mathbf{z} = \sum \|z_i\|^2$
Hermitian iç çarpım	$\mathbf{y}^H \mathbf{x}$
Hermitian matris	$A^H = A$, gerçel köşegen
Unitary	$Q^H Q = I$, $Q^{-1} = Q^H$
Fourier matrisi	$(F_n)_{jk} = W^{jk}$, $W^n = 1$
$F_4$ $W$	$i$
Ters	$F_n^{-1} = \frac{1}{n} F_n^H$
FFT ayrışım	$[I\,D / I\,-D][F_n / F_n]P$
Maliyet	$\frac{1}{2} n \log_2 n$

28.14 ML Bağlantıları Özeti

5 köprü

FFT = konvolüsyon hızlandırma → WaveNet, FNO, diffusion.
Fourier features → NeRF positional encoding, FNO.
Unitary RNN / ortogonal başlatma → Gradyan kararlılığı.
Kompleks-değerli ağlar → MRI, radar, ses; Wirtinger calculus.
Divide-and-conquer → Strassen matris çarpımı, FlashAttention bloklama.

Tek bir şey alıp gideceksen

“Transpoze + eşlenik” (Hermitian) — kompleks dünyanın kuralı. FFT $n^2 \to \frac{1}{2} n \log_2 n$ — modern hesaplamanın temel hızlandırması.

--- title: "Kompleks Matrisler ve FFT" subtitle: "Hermitian, unitary, Fourier matrisi → n log n hızlandırma" --- ::: {.callout-note title="Bölüm bilgisi"} - **Strang'in videosu:** [YouTube — Lecture 26: Complex Matrices; FFT](https://www.youtube.com/watch?v=M0Sa8fLOajA) (≈48 dk) - **OCW sayfası:** [MIT 18.06SC — Lecture 26](https://ocw.mit.edu/courses/18-06sc-linear-algebra-fall-2011/resources/lecture-26-complex-matrices-fast-fourier-transform-fft/) - **Okuma süresi:** ≈40 dk ::: ## Bu Derste Ne Var? {#sec-bu-derste} 1. **Kompleks uzunluk:** $\mathbf{z}^H \mathbf{z}$ ($\mathbf{z}^H = \bar{\mathbf{z}}^T$). 2. **Hermitian** ($A^H = A$) — simetri kompleks karşılığı; **unitary** ($Q^H Q = I$) — ortogonal kompleks karşılığı. 3. **Fourier matrisi** $F_n$: $(F_n)_{jk} = W^{jk}$, $W = e^{2\pi i/n}$. 4. **FFT:** $n^2$ yerine $\frac{1}{2} n \log_2 n$. > *"FFT multiplies by an n×n matrix in one half n log n steps."* — Strang, 45:07 ```{mermaid} %%| label: fig-concept-map %%| fig-cap: "Kompleks → Hermitian/unitary → Fourier → FFT (n² → n log n)." flowchart LR CPLX["Kompleks vektör/matris"] --> H["Hermitian: Aᴴ = A (gerçel λ, dik q)"] CPLX --> U["Unitary: QᴴQ = I"] U --> F["Fourier matrisi Fₙ (F)ⱼₖ = Wʲᵏ"] F --> FFT["⭐ FFT F₂ₙ = [I D; I -D][Fₙ 0; 0 Fₙ]P"] FFT --> COST["n² → ½ n log₂ n (~200× n=1024)"] COST --> ML["Konvolüsyon hızlandırma Unitary RNN Fourier features"] style FFT fill:#fff3e0,stroke:#e67e22,stroke-width:3px style ML fill:#fce4ec,stroke:#c2185b,stroke-width:2px ``` ::: {.callout-tip title="Builder Notu — FFT ML'in Sessiz Devi"} - **Konvolüsyon teoremi** → büyük çekirdek konvolüsyon FFT ile $O(n \log n)$; WaveNet, FNO, diffusion. - **Unitary RNN / ortogonal başlatma** — $|\lambda| = 1$ → gradyan ne patlar ne söner. - **Fourier features** — NeRF positional encoding, FNO PDE çözücüler. - **Divide-and-conquer** deseni → Strassen, FlashAttention bloklama. ::: ## Kompleks Uzunluk — $\mathbf{z}^H \mathbf{z}$ {#sec-uzunluk} $\mathbf{z}^T \mathbf{z}$ yanlış: $\mathbf{z} = (1, i)$ → $1 + i^2 = 0$ (saçma). **Doğrusu:** $$ \mathbf{z}^H \mathbf{z} = \bar{z}_1 z_1 + \cdots = \sum |z_i|^2 > 0 $$ $\mathbf{z} = (1, i)$ → $1 + 1 = 2$, uzunluk $\sqrt 2$. ## Hermitian Matris — $A^H = A$ {#sec-hermitian} $$ A = \begin{pmatrix} 2 & 3+i \\ 3-i & 5 \end{pmatrix} $$ - **Köşegen gerçel.** - **Köşegen-dışı eşlenik çiftler.** Spektral teorem aynen: **gerçel özdeğer + dik özvektör**. ## Unitary Matris — $Q^H Q = I$ {#sec-unitary} Ortogonalin kompleks karşılığı. $Q^{-1} = Q^H$. ## Fourier Matrisi $F_n$ {#sec-fourier} $$ (F_n)_{jk} = W^{jk}, \quad W = e^{2\pi i/n}, \quad W^n = 1 $$ **$F_4$ örneği** ($W = i$): $$ F_4 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} $$ ```{python} #| label: code-fourier #| code-fold: false import numpy as np n = 4 W = np.exp(2j * np.pi / n) F4 = np.array([[W**(j*k) for k in range(n)] for j in range(n)]) print("F4 =\n", np.round(F4, 4)) # Kolonlar Hermitian iç çarpımda dik print("\nF4ᴴ F4 / n =\n", np.round(F4.conj().T @ F4 / n, 4)) # = I ``` ## Ters Matris {#sec-ters} Kolonlar $\sqrt n$ uzunluğunda, Hermitian iç çarpımda dik → $\frac{1}{\sqrt n} F_n$ unitary: $$ F_n^{-1} = \frac{1}{n} F_n^H $$ Ters dönüşüm bedava. ## FFT Fikri — $F_{2n}$ ile $F_n$ {#sec-FFT-fikir} $(W_{2n})^2 = W_n$ → $F_{2n}$ iki $F_n$'e ayrıştırılabilir: $$ F_{2n} = \begin{pmatrix} I & D \\ I & -D \end{pmatrix} \begin{pmatrix} F_n & 0 \\ 0 & F_n \end{pmatrix} P $$ - **$P$:** çift-tek ayırma permütasyonu. - **Orta:** iki bağımsız $F_n$ (köşegen blok). - **$D = \text{diag}(1, W, W^2, \ldots, W^{n-1})$** — düzeltme. **Özyinelemeli:** her $F_n$ tekrar ikiye böl → 1-noktaya iner. ## $n^2 \to \frac{1}{2} n \log_2 n$ ⭐ {#sec-cost} $\log_2 n$ adım, her birinde $\sim n/2$ çarpma: $$ \text{FFT maliyeti} = \frac{1}{2} n \log_2 n $$ | $n$ | Naif ($n^2$) | FFT | |-----|-------------|------| | 1024 | $\sim 10^6$ | 5,120 | | Oran | — | **~200×** | > *"We've reduced the calculation by a factor of 200 just by factoring the matrix properly."* — Strang, 46:25 ## Bu Dersin Özeti {#sec-ozet} 1. **$\mathbf{z}^H \mathbf{z} = \sum |z_i|^2$**. 2. **Hermitian iç çarpım** $\mathbf{y}^H \mathbf{x}$. 3. **Hermitian** $A^H = A$ — gerçel köşegen + eşlenik çiftler. 4. **Unitary** $Q^H Q = I$. 5. **$F_n$**: $(F_n)_{jk} = W^{jk}$. 6. **$F_n^{-1} = \frac{1}{n} F_n^H$**. 7. **FFT ayrıştırması**. 8. **$\frac{1}{2} n \log_2 n$**. ::: {.callout-important title="Tek bir cümle"} Kompleks dünyada "transpoze + eşlenik" (**Hermitian**); **Fourier matrisi** $F_n$ kolonları unitary; **FFT** $F_{2n} = [I\,D / I\,-D][F_n / F_n]P$ özyinelemesi $n^2$'den $\frac{1}{2} n \log_2 n$'e iner — modern hesaplamanın temel hızlandırması. ::: ## Kontrol Soruları {#sec-sorular} ::: {.callout-note collapse="true" title="Soru 1: z = (1, i) uzunluğu? zᵀz neden yanlış?"} $\mathbf{z}^T \mathbf{z} = 1 - 1 = 0$ (yanlış). $\mathbf{z}^H \mathbf{z} = 2$, uzunluk $\sqrt 2$. ::: ::: {.callout-note collapse="true" title="Soru 2: Hermitian matrisin köşegeninde ne tür sayılar?"} **Gerçel** — kendi eşleniğine eşit olmalı. ::: ::: {.callout-note collapse="true" title="Soru 3: F₄'te W kuvvetleri?"} $W = i$. Kuvvetler: $i, -1, -i, 1$. Birim çember çeyrek turları. ::: ::: {.callout-note collapse="true" title="Soru 4: n = 1024 FFT vs naif?"} FFT: $5120$. Naif: $\sim 10^6$. Oran ~**200×**. ::: ## Egzersizler {#sec-egzersizler} **Egzersiz 1.** $\mathbf{z} = (2, 1+i, i)$ uzunluk. **Egzersiz 2.** $A = ((1, 2-i), (2+i, 3))$ Hermitian mi? **Egzersiz 3.** $F_2$ ($W = -1$) yaz. (Hadamard.) **Egzersiz 4.** *(Python)* `np.fft.fft` ile çarpım karşılaştır. **Egzersiz 5.** *İspatla:* Unitary $Q$ uzunluk korur ($\|Q\mathbf{z}\| = \|\mathbf{z}\|$). (İpucu: $\mathbf{z}^H Q^H Q \mathbf{z}$.) ## Sonraki Ders İçin Hazırlık {#sec-sonraki} **Ders 27: Pozitif Tanımlı Matrisler ve Minimumlar** - **Enerji testi:** $\mathbf{x}^T A \mathbf{x} > 0$. - Optimizasyon, eliptik geometri. ::: {.callout-warning title="Ders 27 öncesi"} - Egzersiz 5 (uzunluk koruma). - `fft` ile dene. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet} | Kavram | Tanım | |--------|-------| | **Kompleks uzunluk** | $\mathbf{z}^H \mathbf{z} = \sum |z_i|^2$ | | **Hermitian iç çarpım** | $\mathbf{y}^H \mathbf{x}$ | | **Hermitian matris** | $A^H = A$, gerçel köşegen | | **Unitary** | $Q^H Q = I$, $Q^{-1} = Q^H$ | | **Fourier matrisi** | $(F_n)_{jk} = W^{jk}$, $W^n = 1$ | | **$F_4$ $W$** | $i$ | | **Ters** | $F_n^{-1} = \frac{1}{n} F_n^H$ | | **FFT ayrışım** | $[I\,D / I\,-D][F_n / F_n]P$ | | **Maliyet** | $\frac{1}{2} n \log_2 n$ | ## ML Bağlantıları Özeti {#sec-ml-baglantilar} ::: {.callout-tip title="5 köprü"} 1. **FFT = konvolüsyon hızlandırma** → WaveNet, FNO, diffusion. 2. **Fourier features** → NeRF positional encoding, FNO. 3. **Unitary RNN / ortogonal başlatma** → Gradyan kararlılığı. 4. **Kompleks-değerli ağlar** → MRI, radar, ses; Wirtinger calculus. 5. **Divide-and-conquer** → Strassen matris çarpımı, FlashAttention bloklama. ::: ::: {.callout-important title="Tek bir şey alıp gideceksen"} "Transpoze + eşlenik" (Hermitian) — kompleks dünyanın kuralı. **FFT** $n^2 \to \frac{1}{2} n \log_2 n$ — modern hesaplamanın temel hızlandırması. :::

28 Kompleks Matrisler ve FFT

28.1 Bu Derste Ne Var?

28.2 Kompleks Uzunluk — \(\mathbf{z}^H \mathbf{z}\)

28.3 Hermitian Matris — \(A^H = A\)

28.4 Unitary Matris — \(Q^H Q = I\)

28.5 Fourier Matrisi \(F_n\)

28.6 Ters Matris

28.7 FFT Fikri — \(F_{2n}\) ile \(F_n\)

28.8 \(n^2 \to \frac{1}{2} n \log_2 n\) ⭐

28.9 Bu Dersin Özeti

28.10 Kontrol Soruları

28.11 Egzersizler

28.12 Sonraki Ders İçin Hazırlık

28.13 Anahtar Kavramlar (Cheat Sheet)

28.14 ML Bağlantıları Özeti