33 Uzaklık Matrisleri, Procrustes Problemi

Üçgen eşitsizliği testi, Frobenius normu ve tek SVD ile en iyi ortogonal hizalama

Bölüm bilgisi

Bu ders kısa bir coda: Ders 33’ün uzaklık-matrisi problemini geçerlilik testiyle kapatır, sonra Procrustes problemini (en iyi ortogonal hizalama) tek bir SVD ile çözer. Strang’in Ders 34 videosu (≈29 dk — bu blokun kısa dersi) ve OCW Lecture 34 temel alınmıştır. Okuma süresi ≈22 dk. Önkoşul Ders 33 (uzaklık/Gram matrisleri) ve Ders 6-8 (SVD/Eckart-Young/Frobenius normu).

33.1 Bu Derste Ne Var?

Ders iki parça. İlki Ders 33’ün uzaklık-matrisi probleminin codası: her uzaklık matrisi geçerli mi? İkincisi Procrustes problemi: iki vektör kümesini en iyi ortogonal dönüşümle (rotasyon) hizalama — çözümü şaşırtıcı sadelikte: $Q = UV^T$.

Beş sonuç:

Üçgen eşitsizliği testi: Bir uzaklık matrisi $D$ ancak üçgen eşitsizliğini sağlıyorsa geçerli konum verir. İhlal edilirse Gram matrisi $G$ PSD çıkmaz (negatif özdeğer) — konum bulunamaz (⟺ koşulu).
Procrustes problemi: İki vektör kümesi $X$ ve $Y$; ortogonal $Q$ ile $YQ$’yu $X$’e en yakın yap: $\min_{Q^T Q = I} \|YQ - X\|_F^2$.
Frobenius normu, üç ifade: $\|A\|_F^2 = \sum_{i,j} a_{ij}^2 = \text{tr}(A^T A) = \sum_i \sigma_i^2$.
$Q$ değişmezliği: ortogonal $Q$ ile çarpmak Frobenius normunu (ve tekil değerleri) değiştirmez: $\|QA\|_F = \|A\|_F$.
Çözüm: $Y^T X$’in SVD’sini al, $Y^T X = U\Sigma V^T$; en iyi $Q = UV^T$. İspat iz (trace) özellikleriyle gelir: $\text{tr}(CD) = \text{tr}(DC)$.

flowchart TD
    C["Ders 34: coda + Procrustes"]

    C --> A["ucgen esitsizligi testi:<br/>D gecerli &lt;=&gt; G PSD &lt;=&gt; ucgen saglanir"]
    C --> B["Procrustes: min |YQ - X|_F<br/>(Q ortogonal)"]

    A --> A1["ihlal -&gt; negatif ozdeger<br/>-&gt; konum YOK"]

    B --> B1["Frobenius uc ifade: girdiler<br/>= tr(A^T A) = sigma kareleri"]
    B --> B2["Q-degismezligi:<br/>|QA|_F = |A|_F"]
    B --> B3["iz hileleri:<br/>tr(CD) = tr(DC)"]
    B --> B4["COZUM: Y^T X = U Sigma V^T<br/>-&gt; Q = U V^T"]

    K1["D33 uzaklik / Gram"]
    K2["D6-7 SVD / polar"]
    K3["D8 Frobenius"]
    K4["D35 graf kumeleme (sonraki)"]
    K5["ICP / Kabsch / embedding hizalama"]

    K1 --> A
    K2 --> B4
    K3 --> B1
    B4 --> K4
    B4 --> K5

    classDef merkez fill:#1f4e79,stroke:#13243a,stroke-width:2px,color:#ffffff;
    classDef dal fill:#2e75b6,stroke:#1f4e79,stroke-width:1.5px,color:#ffffff;
    classDef vec fill:#ff8c42,stroke:#c25a16,stroke-width:1.5px,color:#1f2330;
    classDef teal fill:#2ca6a4,stroke:#1f6f6e,stroke-width:1.5px,color:#ffffff;

    class C merkez;
    class A,A1,B,B1,B2,B3,B4 dal;
    class K1,K2,K3 vec;
    class K4,K5 teal;

Şekil 33.1: Ders 34 kavram haritasi: D33 codasi + Procrustes. Dal A ucgen esitsizligi testi - D gecerli <=> G PSD <=> ucgen saglanir; ihlal -> negatif ozdeger -> konum YOK (10 boyut da kurtarmaz). Dal B Procrustes problemi - min |YQ - X|_F, Q ortogonal (uydu/sekil hizalama). Alt-dallar: Frobenius uc ifade (girdiler = tr(A^T A) = sigma kareleri); Q-degismezligi |QA|_F = |A|_F (sigma lar korunur); iz hileleri tr(CD) = tr(DC) (dikdortgende bile, sifir-disi ozdegerler ortak); COZUM Y^T X = U Sigma V^T -> Q = U V^T (tek SVD, iterasyon yok, kapali-form = global optimum). Koprular: D33 uzaklik/Gram, D6-7 SVD/polar, D8 Frobenius, D35 graf kumeleme (sonraki); ICP/Kabsch/embedding hizalama.

Şekil 33.1 dersin codalı iskeletini gösterir: merkezdeki Ders 34: coda + Procrustes düğümünden iki dal ayrılır. Dal A üçgen eşitsizliği testi — $D$ geçerli ⟺ $G$ PSD ⟺ üçgen sağlanır; ihlal → negatif özdeğer → konum YOK (10 boyut da kurtarmaz). Dal B Procrustes problemi — $\min \|YQ - X\|_F$, $Q$ ortogonal (uydu/şekil hizalama). Alt-dallar üç araç verir: Frobenius üç ifade (girdiler = $\text{tr}(A^T A)$ = $\sigma$ kareleri); Q-değişmezliği $\|QA\|_F = \|A\|_F$; iz hileleri $\text{tr}(CD) = \text{tr}(DC)$. Hepsi tek bir çözümde toplanır: $Y^T X = U\Sigma V^T \Rightarrow Q = UV^T$ (tek SVD, iterasyon yok). Köprü düğümleri D33 (uzaklık/Gram), D6-7 (SVD/polar), D8 (Frobenius), D35 graf kümeleme (sonraki) ve ICP/Kabsch/embedding hizalama önceki/sonraki bloklara bağlar.

Builder Notu — Geometri Sayılardan Çıkar

Procrustes = en iyi rotasyon, kapalı-form: iki nokta kümesini hizalamanın çözümü tek SVD. Optimizasyon gerekmez — lineer cebir doğrudan verir.
ML köprüsü: nokta-bulutu hizalama (ICP/Kabsch, moleküler RMSD), şekil analizi ve diller-arası word embedding hizalama hep ortogonal Procrustes çözer.
Frobenius + iz: veri biliminde matris “büyüklüğü” ölçüsü; iz hileleri ($\text{tr}(CD)=\text{tr}(DC)$) birçok türev/optimizasyon ispatını taşır.
Tarihsel not: Strang bu derste “derin öğrenme gerçekten çalışıyor mu?” sorusunu açtı — bir uzman e-postası görüşünü değiştirmiş; başarılı ağ yapıları deneyle ortaya çıkar, baştan verili değil (Pazartesi’ye bıraktı).
Geriye köprü: Ders 33 (uzaklık/Gram), Ders 6-7 (SVD/Eckart-Young), Ders 8 (Frobenius normu). Paralel: fast.ai embedding hizalama, NYU manifold.

Bu ders iki bağımsız sonucu yan yana koyar: bir uzaklık matrisinin geçerlilik testi (üçgen eşitsizliği ⟺ $G$ PSD) ile iki vektör kümesini hizalayan en iyi rotasyon. İkisini de okurken aynı SVD’nin farklı yüzlerini ara.

33.2 1. Üçgen Eşitsizliği: Ne Zaman Konum Bulunamaz?

Ders 33’te uzaklık matrisinden konumları kurtardık. Ama soru: her $D$ geçerli mi? Strang bir karşı-örnekle başlıyor:

“…by the triangle inequality, the distance from x1 to x3 could not be more than 2. And when we square it, it could not be more than 4. And here it’s 6.” — Strang, 0:00

Üç nokta; $d_{12}=1$, $d_{23}=1$ olsun. Üçgen eşitsizliği gereği $d_{13} \leq 2$, yani $d_{13}^2 \leq 4$. Ama $D$’de $d_{13}^2=6$ yazıyorsa — imkânsız. 10 boyuta çıkmak da kurtarmaz (üçgen eşitsizliği boyuttan bağımsızdır).

Ne ters gider? Gram matrisi $G = X^T X$, $D$’den türetilir ve PSD olmalıdır (çünkü her $X^T X$ PSD’dir). Üçgen eşitsizliği ihlal edilirse:

“…the matrix G that comes out of that equation will turn out not to be positive definite.” — Strang, 4:03

$G$ negatif özdeğer kazanır → PSD değil → karekök ($X$) yok. Güzel sonuç (Strang): $D$ geçerli konum verir ⟺ üçgen eşitsizliği sağlanır ⟺ $G$ PSD’dir.

Kod

import matplotlib.pyplot as plt
import numpy as np

fig, (axL, axR) = plt.subplots(1, 2, figsize=(10.5, 4.2))

# ---- Sol: imkansiz ucgen ----
x1 = np.array([0.0, 0.0]); x2 = np.array([1.0, 0.0])
axL.scatter([x1[0], x2[0]], [x1[1], x2[1]], s=100, color=COL_PRIMARY, zorder=5)
axL.annotate("x1", (x1[0], x1[1]), textcoords="offset points", xytext=(-12, -14),
             color=COL_TEXT, fontsize=11, fontweight="bold")
axL.annotate("x2", (x2[0], x2[1]), textcoords="offset points", xytext=(6, -14),
             color=COL_TEXT, fontsize=11, fontweight="bold")
# x1 merkezli yaricap sqrt(6) yay (turuncu kesik)
ac = np.linspace(0, np.pi, 200)
r1 = np.sqrt(6.0)
axL.plot(x1[0] + r1*np.cos(ac), x1[1] + r1*np.sin(ac), "--", color=COL_VEC3, linewidth=2,
         label="x1 çevresi yarıçap √6")
# x2 merkezli yaricap 1 yay (steel kesik)
r2 = 1.0
axL.plot(x2[0] + r2*np.cos(ac), x2[1] + r2*np.sin(ac), "--", color=COL_ACCENT, linewidth=2,
         label="x2 çevresi yarıçap 1")
axL.annotate("d13 = √6 ≈ 2.45 > d12 + d23 = 2\n→ böyle nokta YOK (10 boyut da kurtarmaz)",
             xy=(0.5, 1.7), ha="center", va="center", color=COL_TEXT, fontsize=9,
             bbox=dict(boxstyle="round,pad=0.35", fc=COL_BG, ec=COL_STEEL_300))
apply_style(axL)
axL.set_aspect("equal")
axL.set_xlim(-3.0, 4.0); axL.set_ylim(-0.8, 3.2)
axL.legend(loc="upper right", fontsize=8)
axL.set_title("İmkânsız üçgen: yaylar kesişmiyor", color=COL_TEXT, fontsize=11, fontweight="bold")

# ---- Sag: G ozdegerleri gecerli vs ihlalli ----
ev_valid = np.linalg.eigvalsh(gram_centered(D_VALID_345))
ev_bad = np.linalg.eigvalsh(gram_centered(D_STRANG_BAD))
pos_valid = np.array([0, 1, 2])
pos_bad = np.array([4, 5, 6])
axR.bar(pos_valid, ev_valid, color=COL_PRIMARY, width=0.8)
bad_colors = [COL_VEC3 if v < 0 else COL_ACCENT for v in ev_bad]
axR.bar(pos_bad, ev_bad, color=bad_colors, width=0.8)
axR.axhline(0, color="#888888", linewidth=1.0)
axR.annotate("min λ = −0.333 → PSD değil",
             xy=(5, np.min(ev_bad)), xytext=(2.0, np.min(ev_bad) - 4.5),
             color=COL_TEXT, fontsize=9,
             arrowprops=dict(arrowstyle="->", color=COL_VEC3),
             bbox=dict(boxstyle="round,pad=0.3", fc=COL_BG, ec=COL_STEEL_300))
axR.set_xticks([1, 5]); axR.set_xticklabels(["3-4-5 (geçerli)", "(1,1,6) ihlâllı"])
apply_style(axR)
axR.set_title("G özdeğerleri: geçerli vs ihlâllı", color=COL_TEXT, fontsize=12, fontweight="bold")

fig.suptitle("Üçgen eşitsizliği uzaklık matrisinin geçerlilik testi: ihlal G'yi PSD-dışına iter — D geçerli ⟺ G PSD",
             color=COL_TEXT, fontsize=11, fontweight="bold")
plt.tight_layout(rect=[0, 0, 1, 0.95])
plt.show()

Şekil 33.2: Üçgen eşitsizliği uzaklık matrisinin geçerlilik testidir: ihlal G’yi PSD-dışına iter — D geçerli ⟺ G PSD. Strang örneği D=(0,1,6/1,0,1/6,1,0) çift-merkezlenmiş G’nin en küçük özdeğerini −0.333’e iter (PSD değil, konum yok); 3-4-5 üçgeni geçerli (tüm özdeğerler ≥0).

Şekil 33.2 üçgen eşitsizliğinin geçerlilik testini iki yandan motor-tanıklı gösterir: solda imkânsız üçgen — $x_1$ ve $x_2$ arasındaki uzaklık 1, ama $D$’nin istediği $d_{13} = \sqrt{6} \approx 2.45$ için $x_1$ çevresinde yarıçap $\sqrt{6}$ yay (turuncu kesik) ile $x_2$ çevresinde yarıçap 1 yay (steel kesik) kesişmiyor — $d_{13} > d_{12} + d_{23} = 2$ olduğundan böyle bir nokta yoktur (10 boyut da kurtarmaz). Sağda iki $D$’nin çift-merkezlenmiş $G$ özdeğerleri yan yana: 3-4-5 üçgeni (navy, hepsi $\geq 0$) geçerli; Strang’ın bozuk örneği $(1,1,6)$ ise en küçük özdeğeri $-0.333$’e iter (turuncu bar, $\text{min }\lambda = -0.3333$) — PSD değil, konum yok. Negatif özdeğer ihlalin doğrudan imzasıdır.

Builder Notu — Geçersiz Uzaklığın İmzası

“Üçgen eşitsizliği = uzaklık matrisinin geçerlilik testi” temiz bir karakterizasyon. ML köprüsü: bir benzerlik/uzaklık matrisinin gerçek bir gömmeden gelip gelmediğini PSD testiyle anlarsın — kernel yöntemlerinde “kernel geçerli mi” (Mercer koşulu) tam bu PSD kontrolüdür. Gürültülü ölçümlerde $G$’nin küçük negatif özdeğerlerini sıfırlayıp en yakın PSD’ye yansıtırsın (Ders 7 Eckart-Young ile akraba).

33.3 2. Procrustes Problemi: En İyi Ortogonal Hizalama

İkinci problem — adı Yunan mitinden gelir; Procrustes misafirini yatağına uydurmak için gerer ya da keserdi:

“…Procrustes adjusted the length of the visitor to fit the bed.” — Strang, 8:06

Problem: iki vektör kümen var — $X = (x_1,\dots,x_n)$ ve $Y = (y_1,\dots,y_n)$. Örnek: uydu konumlarının iki farklı hesabı; biri diğerinden kısmen döndürülmüş, üstüne yuvarlama hatası var. En iyi ortogonal $Q$’yu bul ki $YQ$, $X$’e olabildiğince yakın olsun:

“…over all orthogonal Q’s I want to minimize YQ minus X in the Frobenius norm.” — Strang, 12:07

\[\min_{Q^T Q = I} \|YQ - X\|_F^2\]

Eğer $X$ ve $Y$ ortonormal tabanlar olsaydı tam eşitlik elde edilirdi ($Q$ ile biri diğerine tam dönerdi); değiller, bu yüzden “en iyi”yi ararız. Bu, en küçük kareler’in ortogonal-kısıtlı halidir.

Kod

X, Y, R = make_procrustes_pair(noise=0.08, seed=7)

fig, ax = plt.subplots(figsize=(7.5, 4.6))
for i in range(X.shape[0]):
    ax.plot([X[i, 0], Y[i, 0]], [X[i, 1], Y[i, 1]], color="#999999", lw=1.0, alpha=0.5, zorder=1)
ax.scatter(X[:, 0], X[:, 1], s=70, color=COL_PRIMARY, label="X (hedef)", zorder=3, edgecolors="white", linewidths=0.6)
ax.scatter(Y[:, 0], Y[:, 1], s=70, color=COL_VEC3, label="Y (dönmüş + gürültülü)", zorder=3, edgecolors="white", linewidths=0.6)
ax.annotate("en iyi ortogonal Q? (uydu konumları örneği)", xy=(0.5, 0.02), xycoords="axes fraction",
            ha="center", va="bottom", fontsize=10, color=COL_TEXT,
            bbox=dict(boxstyle="round,pad=0.3", fc=COL_BG, ec=COL_STEEL_300))
ax.legend(loc="upper left", framealpha=0.9)
apply_style(ax)
ax.set_aspect("equal")
ax.set_title("Procrustes problemi: Y yi X e en iyi döndüren ortogonal Q yu bul — min |YQ - X|_F",
             color=COL_TEXT, fontsize=11, fontweight="bold")
plt.show()

Şekil 33.3: Procrustes problemi: iki nokta bulutu — X (hedef, navy) ve Y (X’in döndürülmüş + gürültülü hali, turuncu). Eşleşen noktalar ince gri çizgilerle bağlı. Soru: Y’yi X’e en iyi oturtan ortogonal Q nedir? (uydu konumları örneği) — min |YQ - X|_F.

Şekil 33.3 problemi somutlaştırır: navy noktalar hedef kümesi $X$, turuncu noktalar $X$’in döndürülmüş ve hafif gürültülü hali $Y$ (motorda $\text{noise}=0.08$, gerçek rotasyon $\theta = 0.9$). Eşleşen noktalar ince gri çizgilerle bağlı — her çizgi $Y$’nin bir noktasını $X$’teki karşılığına bağlar, hizasızlığı görünür kılar. Soru tam ortada: $Y$’yi $X$’e en iyi oturtan ortogonal $Q$ nedir? Uydu konumları örneği bunun pratik kalbidir — iki farklı hesap aynı geometriyi taşır, yalnız bir rotasyon (ve gürültü) farkıyla. Aradığımız $\min \|YQ - X\|_F$’i çözen $Q$.

Builder Notu — Yatak ile Misafir

“Procrustes = kısıtlı en küçük kareler (Q ortogonal)” pratik bir hizalama problemi. ML köprüsü: nokta-bulutu kaydı (point cloud registration), şekil eşleme ve diller-arası kelime gömme hizalaması ($X$=İngilizce, $Y$=Türkçe embedding; $Q$ diller arası köprü) hep bunu çözer. Kabsch algoritması (moleküler yapı RMSD) ve ICP’nin (iterative closest point) çekirdeği ortogonal Procrustes’tir.

33.4 3. Frobenius Normu: Üç İfade

Procrustes’i çözmek için Frobenius normunu iyi tanımak gerekir. Üç eşdeğer ifadesi var:

“…three nice expressions for the Frobenius norm.” — Strang, 16:12

\[\|A\|_F^2 = \sum_{i,j} a_{ij}^2 = \text{tr}(A^T A) = \text{tr}(AA^T) = \sum_i \sigma_i^2\]

Girdiler: matrisi uzun bir vektör gibi gör, tüm $a_{ij}^2$’leri topla.
İz (trace): $A^T A$ (veya $AA^T$) köşegen toplamı = tüm sütunların kare uzunlukları toplamı.
Tekil değerler: $\sigma_i^2$ toplamı — çünkü $\sigma_i^2$, $A^T A$’nın özdeğerleridir ve iz = özdeğerlerin toplamıdır.

İlk ifade yazması hantal; iz ve tekil-değer biçimleri çok daha kullanışlıdır (özellikle ispatlarda).

Kod

fig, (axL, axR) = plt.subplots(1, 2, figsize=(10, 4))

# Sol: Egz2 — A=[[3,0],[0,4]]
A2 = np.array([[3., 0], [0, 4]])
a, b, c = fro_three_ways(A2)
labels = ["girdiler toplami", "tr(A^T A)", "sigma kareleri"]
vals = [a, b, c]
bars = axL.bar(labels, vals, color=COL_PRIMARY)
for rect, v in zip(bars, vals):
    axL.text(rect.get_x() + rect.get_width() / 2, v, "25", ha="center", va="bottom",
             color=COL_TEXT, fontweight="bold")
axL.set_title("A=[[3,0],[0,4]]: uc yol = 25")
axL.set_ylim(0, max(vals) * 1.18)
apply_style(axL)

# Sag: rastgele 4x3
rng = np.random.default_rng(34)
Ar = rng.uniform(-2, 2, (4, 3))
a2, b2, c2 = fro_three_ways(Ar)
vals2 = [a2, b2, c2]
bars2 = axR.bar(labels, vals2, color=COL_PRIMARY)
for rect, v in zip(bars2, vals2):
    axR.text(rect.get_x() + rect.get_width() / 2, v, "{:.3f}".format(v), ha="center", va="bottom",
             color=COL_TEXT, fontweight="bold")
axR.set_title("rastgele 4x3 te de birebir (defect < 1e-10)")
axR.set_ylim(0, max(vals2) * 1.18)
apply_style(axR)

fig.suptitle("Frobenius normunun uc dili ayni sayiyi verir: girdiler = iz = tekil-deger kareleri — ispatlarda iz/sigma formu kullanilir")
plt.show()

Şekil 33.4: Frobenius normunun üç dili aynı sayıyı verir: girdiler toplamı = iz = tekil-değer kareleri. Sol — A=[[3,0],[0,4]] için üçü de 25; sağ — rastgele 4×3 matriste de defect < 1e-10. İspatlarda iz/sigma formu kullanılır.

Şekil 33.4 üç ifadenin birebir aynı sayıyı verdiğini motor-tanıklı gösterir: solda Egzersiz 2’nin matrisi $A=[[3,0],[0,4]]$ için üç yol da 25 çıkar — girdiler toplamı ($3^2 + 4^2$), $\text{tr}(A^T A)$ ve $\sum \sigma_i^2$ ($\sigma = (4,3)$); üç bar tıpatıp aynı yükseklikte. Sağda rastgele bir $4\times3$ matris için üç yol yine birebir eşittir (defect $< 10^{-10}$) — eşitlik özel bir matrise değil, normun tanımına bağlı. İlk ifade (girdiler) hesaplaması hantal kalır; iz ve tekil-değer biçimleri ispatlarda kullanılan formdur, çünkü $\text{tr}$ ve $\sigma$ cebirsel manipülasyona açıktır.

Builder Notu — Aynı Büyüklüğün Üç Dili

“Frobenius normu = √(Σσᵢ²) = √tr(AᵀA)” — üç dil aynı sayıyı verir. ML köprüsü: ağırlık matrisi büyüklüğü (L2/weight decay aslında Frobenius normunun karesidir), gradyan normu izleme ve düşük-rank yaklaşım hatası (Eckart-Young: atılan $\sigma$’ların kareleri) hep Frobenius’tur. PyTorch torch.norm(A, 'fro').

33.5 4. Q Değişmezliği: Ortogonal Çarpım Normu Korur

Procrustes’in anahtarı: ortogonal $Q$ ile çarpmak Frobenius normunu değiştirmez.

“…the length of Q times any vector squared is the same as the vector squared.” — Strang, 18:12

\[\|QA\|_F = \|A\|_F\]

İki kanıt: (1) $QA$’nın her sütunu $Q$ ile çarpılır; $Q$ vektör uzunluğunu korur ($\|Qv\|=\|v\|$), dolayısıyla sütun-sütun kare toplam değişmez. (2) SVD ile: $A = U\Sigma V^T$ ise $QA = (QU)\Sigma V^T$ — yalnız ilk ortogonal faktör değişir, $\Sigma$ (tekil değerler) aynı kalır:

“…QA will have the SVD QU sigma V transpose. …I didn’t change the sigmas.” — Strang, 18:12

Frobenius normu $\sigma$’lara bağlı olduğundan $Q$ onu değiştiremez. (Aynısı diğer taraf için de geçerli: $AQ'$ de tekil değerleri korur.)

Kod

A3 = np.array([[1., 2], [3, 4]])
Q90 = np.array([[0., -1], [1, 0]])

fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(10, 4))

# Sol: A ve QA tekil değerleri bar yan-yana (AYNI değerler)
s0 = np.linalg.svd(A3, compute_uv=False)
s1 = np.linalg.svd(Q90 @ A3, compute_uv=False)
x = np.arange(len(s0))
ax0.bar(x - 0.18, s0, width=0.34, color=COL_PRIMARY, label="A nin sigma lari")
ax0.bar(x + 0.18, s1, width=0.34, color=COL_VEC3, label="QA nin sigma lari")
ax0.set_xticks(x); ax0.set_xticklabels(["sigma 1", "sigma 2"])
ax0.set_ylabel("tekil deger")
ax0.legend(loc="upper right", fontsize=9)
ax0.annotate("|A|_F^2 = |QA|_F^2 = 30", xy=(0.5, 0.5), xycoords="axes fraction",
             ha="center", va="center", fontsize=10, color=COL_TEXT,
             bbox=dict(boxstyle="round", fc=COL_BG, ec=COL_STEEL_300))
ax0.set_title("tekil degerler korunur", color=COL_TEXT, fontsize=12, fontweight="bold")
apply_style(ax0)

# Sağ: birim çember + A kolonları (navy oklar) + QA kolonları (turuncu kesik oklar)
th = np.linspace(0, 2 * np.pi, 200)
ax1.plot(np.cos(th), np.sin(th), color=COL_STEEL_300, lw=0.8)
QA = Q90 @ A3
labels_a = ["a1", "a2"]; labels_qa = ["Qa1", "Qa2"]
for j in range(2):
    ax1.annotate("", xy=(A3[0, j], A3[1, j]), xytext=(0, 0),
                 arrowprops=dict(arrowstyle="->", color=COL_PRIMARY, lw=2))
    ax1.text(A3[0, j] * 1.08, A3[1, j] * 1.08, labels_a[j], color=COL_PRIMARY,
             fontsize=11, fontweight="bold")
    ax1.annotate("", xy=(QA[0, j], QA[1, j]), xytext=(0, 0),
                 arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=2, linestyle="--"))
    ax1.text(QA[0, j] * 1.08, QA[1, j] * 1.08, labels_qa[j], color=COL_VEC3,
             fontsize=11, fontweight="bold")
ax1.set_title("Q yalniz dondurur, uzunluk degismez", color=COL_TEXT, fontsize=12, fontweight="bold")
apply_style(ax1)
ax1.set_aspect("equal")
lim = 4.6
ax1.set_xlim(-lim, lim); ax1.set_ylim(-lim, lim)

fig.suptitle("Ortogonal carpim normu bozmaz: QA = (QU) Sigma V^T — sigma lar ayni kalir, Frobenius sigma lara bagli",
             fontsize=11, color=COL_TEXT)
fig.tight_layout()
plt.show()

Şekil 33.5: Ortogonal çarpım normu bozmaz: A=[[1,2],[3,4]] ve 90° rotasyon Q için A ile QA’nın tekil değerleri birebir aynı (sol), dolayısıyla ‖A‖²_F = ‖QA‖²_F = 30; Q yalnızca kolonları döndürür, uzunluklarını değiştirmez (sağ).

Şekil 33.5 Q-değişmezliğini iki yandan gösterir: solda Egzersiz 3’ün matrisi $A=[[1,2],[3,4]]$ ve $90°$ rotasyon $Q$ için $A$ ile $QA$’nın tekil değerleri birebir aynı (navy/turuncu barlar üst üste; tekil değer farkı 8.9e-16), dolayısıyla $\|A\|_F^2 = \|QA\|_F^2 = 30$ (defect 0.0). Sağda birim çember üzerinde $A$’nın kolonları (navy oklar) ve $QA$’nın kolonları (turuncu kesik oklar) — $Q$ her kolonu $90°$ döndürür ama uzunluğunu aynen korur; oklar farklı yöne bakar, eşit uzundur. İki yan aynı mesajı söyler: $QA = (QU)\Sigma V^T$ ayrışımında yalnız ortogonal faktör değişir, $\sigma$’lar sabit kalır, Frobenius normu $\sigma$’lara bağlı olduğundan değişmez.

Builder Notu — Döndürmek Normu Bozmaz

“Ortogonal çarpım tekil değerleri ve Frobenius normunu korur” — SVD’nin temel simetrisi. ML köprüsü: ortogonal/üniter dönüşümler enerjiyi (bilgiyi) korur; bu yüzden ortogonal başlatma (orthogonal init), normalleştirici akışlar (normalizing flows) ve dönüşüme-değişmez kayıplar bu özelliğe yaslanır. Procrustes’te bu özellik, problemi bir iz (trace) maksimizasyonuna indirgememizi sağlar.

33.6 5. İz (Trace) Hileleri

Çözüm ize dayanır, o yüzden birkaç iz özdeşliği gerekir. İz = köşegen toplamı = özdeğerlerin toplamı.

“…the trace of A transpose B is equal to the trace of B transpose A.” — Strang, 20:14

\[\text{tr}(A^T B) = \text{tr}(B^T A) = \text{tr}(BA^T)\]

Çünkü transpoz köşegeni değiştirmez (iz, transpoz altında sabittir). Dahası, döngüsel özellik — çarpım sırasını çevirebilirsin:

\[\text{tr}(CD) = \text{tr}(DC)\]

Neden? $CD$ ile $DC$ aynı sıfırdan-farklı özdeğerlere sahiptir (dikdörtgen olsalar bile fazladan sıfır özdeğerler ize katkı yapmaz), iz = özdeğer toplamı olduğundan eşittirler.

“…How are the eigenvalues of CD related to the eigenvalues of DC? They’re the same.” — Strang, 22:14

Kod

rng = np.random.default_rng(34)
_ = rng.uniform(-2, 2, (4, 3))          # verify ile aynı rng akışı (önce 4x3)
C5 = rng.uniform(-2, 2, (3, 5))          # sonra C5 (3x5)
D5 = rng.uniform(-2, 2, (5, 3))          # sonra D5 (5x3)

lam_cd = np.linalg.eigvals(C5 @ D5)      # 3 özdeğer (3x3)
lam_dc = np.linalg.eigvals(D5 @ C5)      # 5 özdeğer (5x5): 3 ortak + 2 sıfır

defect = trace_cyclic_defect(C5, D5)

fig, ax = plt.subplots(figsize=(7.5, 4.2))
apply_style(ax)
ax.axhline(0, color=COL_STEEL_300, linewidth=0.8, zorder=0)
ax.axvline(0, color=COL_STEEL_300, linewidth=0.8, zorder=0)
ax.scatter(lam_cd.real, lam_cd.imag, color=COL_PRIMARY, s=120, zorder=3,
           label="lambda(CD) — 3x3")
ax.scatter(lam_dc.real, lam_dc.imag, facecolors="none", edgecolors=COL_VEC3,
           s=200, linewidths=2.0, zorder=4, label="lambda(DC) — 5x5")

ax.set_xlim(-4.0, 10.5); ax.set_ylim(-1.6, 1.9)

# DC'nin orijindeki iki ekstra sıfırı
ax.annotate("DC nin ekstra sifirlari (ize katki yok)", xy=(0, 0),
            xytext=(1.2, 1.25), fontsize=8.5, color=COL_TEXT,
            arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.2))
ax.annotate(f"tr(CD) = tr(DC) (defect {defect:.1f})", xy=(0.04, 0.05),
            xycoords="axes fraction", fontsize=9, color=COL_TEXT)

ax.legend(fontsize=8.5, loc="upper right")
ax.set_xlabel("Re"); ax.set_ylabel("Im")
ax.set_title("Dongusel iz: CD (3x3) ile DC (5x5) ayni sifir-disi ozdegerleri tasir — dikdortgende bile",
             color=COL_TEXT, fontsize=10, fontweight="bold")

plt.show()

Şekil 33.6: Döngüsel iz: CD (3×3) ile DC (5×5) aynı sıfır-dışı özdeğerleri taşır — dikdörtgende bile. λ(CD) = {9.07, −2.31, −2.68}; DC bu üçünü aynen taşır + orijinde 2 ekstra sıfır (ize katkı yok). tr(CD) = tr(DC), defect 0.0.

Şekil 33.6 döngüsel iz özelliğini dikdörtgen matrislerde bile motor-tanıklı doğrular: $C$ bir $3\times5$, $D$ bir $5\times3$ matris olsun. $\lambda(CD)$ (3 navy nokta, $3\times3$) karmaşık düzlemde işaretlenir; $\lambda(DC)$ (5 turuncu halka, $5\times5$) bu üç özdeğeri aynen taşır — üç turuncu halka navy noktaların tam üstüne oturur — artı orijinde 2 ekstra sıfır özdeğer, ki bunlar ize katkı yapmaz. Sonuç: $\text{tr}(CD) = \text{tr}(DC)$, defect 0.0. İz = özdeğer toplamı olduğundan, sıfır-dışı özdeğerlerin ortaklığı izlerin eşitliğini doğrudan verir; çarpım sırasını çevirmek izi değiştirmez — Procrustes ispatının taşıyıcı kuralı.

Builder Notu — Köşegen Toplamının Hileleri

“İz döngüseldir: tr(CD)=tr(DC)” hesaplamada altın kuraldır. ML köprüsü: matris türevleri ($\partial\,\text{tr}(AX)/\partial X = A^T$), Frobenius normu = $\text{tr}(A^T A)$ ve birçok kayıp/regularizasyon ize çevrilir; iz-döngüsel hilesi ifadeleri optimize edilebilir biçime sokar. Bu, “matris kalkülüsü”nün (Ders 15-16) günlük aletidir.

33.7 6. Çözüm: Q = UVᵀ

Frobenius normunu açıp $Q$ değişmezliğini ve iz hilelerini kullanınca problem, bir izi maksimize etmeye iner. Cevap şaşırtıcı sadelikte:

“…Compute Y transpose X. Compute its SVD, and use the orthogonal matrices from the SVD.” — Strang, 26:15

\[Y^T X = U\Sigma V^T \quad\Longrightarrow\quad Q_{\text{opt}} = U V^T\]

Yani: verilen $X$, $Y$ için $Y^T X$ matrisini kur (iki kümenin tüm iç-çarpımları), SVD’sini al, ortogonal faktörleri çarp. $Q = UV^T$ en iyi ortogonal hizalamadır.

“…the best Q is— Da dun da duh. …It is UV transpose.” — Strang, 26:15

$\Sigma$ (tekil değerler) düşer; geriye yalnız ortogonal $U$ ve $V$ kalır — çarpımları da ortogonaldir (iki ortogonalin çarpımı). Eğer $Y$ zaten $X$’e tam dönüyorsa $Y^T X$ ortogonal çıkar ve $UV^T$ tam o dönüşü verir.

Kod

import matplotlib.pyplot as plt
import numpy as np

Xn, Yn, Rn = make_procrustes_pair(noise=0.08, seed=7)
Qn = procrustes_q(Xn, Yn)
err_svd = np.linalg.norm(Yn @ Qn - Xn)

fig, axes = plt.subplots(1, 3, figsize=(12, 4.2))

# Sol: hizalama ÖNCESİ
ax = axes[0]
ax.scatter(Xn[:, 0], Xn[:, 1], c=COL_PRIMARY, s=60, label="X (hedef)")
ax.scatter(Yn[:, 0], Yn[:, 1], c=COL_VEC3, s=60, label="Y (dönmüş)")
ax.set_title("önce: ham fark 4.612", color=COL_TEXT, fontsize=11, fontweight="bold")
ax.legend(fontsize=8)
apply_style(ax); ax.set_aspect("equal")

# Orta: açı taraması
ax = axes[1]
thetas = np.linspace(0, 2*np.pi, 3600)
errs = angle_sweep_error(Xn, Yn, thetas)
ax.plot(thetas, errs, color=COL_PRIMARY, lw=1.8)
th_q = np.arctan2(Qn[1, 0], Qn[0, 0]) % (2*np.pi)
ax.scatter([th_q], [err_svd], c=COL_VEC3, marker="*", s=250, zorder=3)
ax.annotate("3600 aday: hiçbiri\nSVD'den iyi değil",
            xy=(th_q, err_svd), xytext=(th_q + 1.4, err_svd + 1.6),
            fontsize=8, color=COL_TEXT,
            arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.2))
ax.set_xlabel("theta (radyan)"); ax.set_ylabel("|Y Q(theta) - X|_F")
ax.set_title("SVD çözümü TAM minimumda (theta = 0.9061)", color=COL_TEXT, fontsize=10, fontweight="bold")
apply_style(ax)

# Sağ: hizalama SONRASI
ax = axes[2]
YQ = Yn @ Qn
ax.scatter(Xn[:, 0], Xn[:, 1], c=COL_PRIMARY, s=60, label="X (hedef)")
ax.scatter(YQ[:, 0], YQ[:, 1], c=COL_VEC3, s=25, label="Y·Q (hizalı)")
ax.set_title("sonra: hata 4.612 -> 0.347", color=COL_TEXT, fontsize=11, fontweight="bold")
ax.legend(fontsize=8)
apply_style(ax); ax.set_aspect("equal")

fig.suptitle("Procrustes çözümü Q = UVᵀ: tek SVD, iterasyon yok — açı taraması kapalı-formun global optimum olduğunu doğruluyor",
             color=COL_TEXT, fontsize=10.5, fontweight="bold")
fig.tight_layout()
plt.show()

Şekil 33.7: Procrustes çözümü Q = UVᵀ: tek SVD, iterasyon yok. Sol panel hizalama öncesi ham farkı (‖Y − X‖ = 4.612) gösterir; orta panel 3600 açı adayını tarar ve SVD çözümünün (turuncu yıldız, theta = 0.9061) TAM minimumda oturduğunu — hiçbir Q(theta) ondan iyi değil — kanıtlar; sağ panel hizalama sonrası X ile Y·Q’nun üst üste düştüğünü (hata 4.612 → 0.347) gösterir. Açı taraması kapalı-formun global optimum olduğunu doğrular.

Şekil 33.7 dersin flagship kanıtıdır: kapalı-form çözüm $Q = UV^T$ gerçekten global optimumu verir. Solda hizalama öncesi $X$ (navy) ve $Y$ (turuncu) üst üste — ham fark $|Y - X| = $ 4.612. Ortada açı taraması: $3600$ farklı $\theta$ için $\|YQ(\theta) - X\|_F$ çizilir (navy eğri); SVD çözümünün açısı $= $ 0.9061 turuncu yıldızla işaretli ve eğrinin tam minimumunda oturur — $3600$ adayın hiçbiri SVD çözümünden iyi değil. Bu, kapalı-formun iterasyonsuz biçimde global optimum olduğunun doğrudan tanığıdır (brute-force tarama ile kapalı-form çakışır). Sağda hizalama sonrası $X$ (navy) ile $Y\cdot Q$ (küçük turuncu) neredeyse üst üste — hata $4.612 $ 0.347’ye iner (kalan, eklenen gürültünün payı). Tek bir SVD, hiçbir optimizasyon döngüsü olmadan, açı-uzayını tarayan bir aramanın bulduğu optimumu verir.

Builder Notu — Tek SVD ile En İyi Dönüş

“En iyi ortogonal Q = UVᵀ ($Y^T X$’in SVD’sinden)” kapalı-form bir mücevher. ML köprüsü: bu formül ortogonal Procrustes’in standart çözümüdür — şekil hizalama, embedding hizalama (örn. çok-dilli kelime vektörleri, MUSE) ve poz tahmini hep bunu kullanır. SVD’nin “en yakın ortogonal matrisi verme” gücüyle (polar ayrışım, Ders 6) aynı kökten gelir.

33.8 Bu Dersin Özeti

Üçgen eşitsizliği: $D$ geçerli konum verir ⟺ üçgen eşitsizliği sağlanır ⟺ $G=X^T X$ PSD’dir (ihlalde $G$ negatif özdeğer kazanır, $X$ bulunamaz).
Procrustes problemi: ortogonal $Q$ üzerinden $\min \|YQ-X\|_F^2$ — iki vektör kümesini en iyi rotasyonla hizala.
Frobenius normu: $\|A\|_F^2 = \sum a_{ij}^2 = \text{tr}(A^T A) = \text{tr}(AA^T) = \sum \sigma_i^2$ (üç eşdeğer ifade).
Q değişmezliği: $\|QA\|_F = \|A\|_F$ (ortogonal çarpım tekil değerleri ve Frobenius normunu korur).
İz hileleri: $\text{tr}(A^T B)=\text{tr}(B^T A)$, $\text{tr}(CD)=\text{tr}(DC)$ (döngüsel; $\lambda(CD)=\lambda(DC)$ sıfırdan-farklı özdeğerler).
Çözüm: $Y^T X=U\Sigma V^T \Rightarrow Q=UV^T$ — en iyi ortogonal hizalama, tek bir SVD ile.

Tek Bir Cümle

Bir uzaklık matrisi ancak üçgen eşitsizliğini sağlarsa konuma çevrilebilir (yoksa $G=X^T X$ PSD olmaz); Procrustes problemi ise iki vektör kümesini en iyi hizalayan ortogonal matrisi tek bir SVD ile bulur — $Y^T X=U\Sigma V^T \Rightarrow Q=UV^T$.

33.9 Kontrol Soruları

Soru 1 — Üçgen eşitsizliği ihlal edilirse ne olur; bu G’yi nasıl etkiler

Üçgen eşitsizliği (örn. $d_{13} \leq d_{12}+d_{23}$) ihlal edilirse, $D$’den türetilen Gram matrisi $G = X^T X$ pozitif yarı-tanımlı çıkmaz — negatif özdeğer kazanır. PSD olmayan bir matrisin $X^T X$ biçiminde karekökü yoktur, dolayısıyla bu uzaklıkları sağlayan konumlar bulunamaz. Tam karakterizasyon: $D$ geçerli konum verir ⟺ üçgen eşitsizliği sağlanır ⟺ $G$ PSD’dir.

Soru 2 — Procrustes problemi nedir; neden genelde tam eşitlik olmaz

İki vektör kümesi $X$ ve $Y$ verili; amaç ortogonal $Q$ ile $\min_Q \|YQ - X\|_F^2$’yi çözmek ($Y$’yi $X$’e en iyi döndürmek). Tam eşitlik ancak $X$ ve $Y$ her ikisi de ortonormal tabansa ve biri diğerinin tam rotasyonuysa olur. Pratikte iki küme yuvarlama hatası/gürültü içerir ya da tam ortonormal değildir, bu yüzden “tam” değil “en iyi” hizalamayı ararız.

Soru 3 — Ortogonal Q neden Frobenius normunu değiştirmez

İki nedenle. (1) $Q$ her vektörün uzunluğunu korur ($\|Qv\|=\|v\|$); Frobenius normu sütunların kare uzunlukları toplamı olduğundan $QA$ ile $A$ aynı normda. (2) SVD ile: $A=U\Sigma V^T$ ise $QA=(QU)\Sigma V^T$ — yalnız ilk ortogonal faktör değişir, tekil değerler $\Sigma$ aynı kalır. Frobenius normu $\sqrt{\sum \sigma_i^2}$ olduğundan değişmez.

Soru 4 — Procrustes çözümü nedir; nasıl hesaplanır

İki kümenin iç-çarpım matrisi $Y^T X$’i kur, SVD’sini al: $Y^T X = U\Sigma V^T$. En iyi ortogonal matris $Q = UV^T$’dir. $\Sigma$ (tekil değerler) çözümden düşer; yalnız ortogonal faktörler $U$ ve $V$ kullanılır. Bu kapalı-form çözüm optimizasyon iterasyonu gerektirmez — tek bir SVD yeterlidir.

33.10 Egzersizler

Üçgen testi. Üç nokta için uzaklıklar $d_{12}=1$, $d_{23}=1$, $d_{13}=3$ (kareler 1, 1, 9). Üçgen eşitsizliği sağlanıyor mu? Bu $D$’den geçerli konumlar bulunabilir mi — Gram matrisi $G$ PSD olur mu (sezgisel açıkla)? (Motor tanığı: $d_{13}=3 > d_{12}+d_{23}=2$ → İHLAL; çift-merkezlenmiş $G$’nin en küçük özdeğeri −0.8333 → PSD değil, konum yok. Sınır durumu $d_{13}^2=4$ (tam eşitlik): min $\lambda \approx 0$ — üç nokta bir çizgiye çöker, doğrusal dizilim.)
Frobenius üç yol. $A = [[3,0],[0,4]]$. $\|A\|_F^2$’i üç yolla hesapla: (a) girdilerin kareleri toplamı, (b) $\text{tr}(A^T A)$, (c) $\sum \sigma_i^2$ (bu köşegen matriste $\sigma$’lar nedir?). Üçü de eşit mi? (Motor tanığı: girdiler $= (A^T A) = _i^2 = $ 25; $\sigma = (4, 3)$.)
Q değişmezliği. $A = [[1,2],[3,4]]$, $Q = [[0,-1],[1,0]]$ ($90°$ rotasyon). $\|A\|_F^2$ ve $\|QA\|_F^2$’i hesapla; eşit olduklarını göster. (Motor tanığı: $|A|_F^2 = |QA|_F^2 = $ 30 (defect 0.0); tekil değerler birebir korunur (fark 8.9e-16).)
Procrustes. $X = [[1,0],[0,1]]$ (birim), $Y = [[0,1],[-1,0]]$ ($90°$ dönmüş). $Y^T X$’i kur, SVD’sinden $Q=UV^T$’yi bul; $Q$’nun $Y$’yi $X$’e götürdüğünü ($YQ \approx X$) doğrula. (Motor tanığı: $Q=UV^T$ ortogonal; $Y$ ortogonal olduğundan $YQ = X$ TAM eşitlik.)
(Ders 35 habercisi) Bir sosyal ağı (graf) iki kümeye ayırmak istiyorsun. Hangi matris ve hangi özvektör işe yarar? Bir tahmin yaz — Ders 35 “graflarda kümeler bulmak”ı (graf Laplacian’ı, Fiedler vektörü, spektral kümeleme) işliyor.

33.11 Sonraki Ders İçin Hazırlık

Ders 35: Graflarda Kümeler Bulmak. Sinyal/CNN/graf bloğunun graf kısmı: bir grafı iki (veya k) kümeye ayırma (graph partitioning/clustering). Araç graf Laplacian’ı ($L = D - A$) ve onun ikinci en küçük özvektörü (Fiedler vektörü) — spektral kümeleme. Lineer cebir, ağ yapısını kümelere çevirir; Ders 19’un maxmin/özvektör fikriyle akraba.

Hazırlık

Bu dersin Egzersiz 5’inin sorduğu soruyu zihninde tut: bir grafı iki kümeye ayırmak için hangi matris ve hangi özvektör işe yarar? Ders 35 graf Laplacian’ını ($L = D - A$) ve onun ikinci en küçük özvektörünü (Fiedler vektörü) işler — spektral kümeleme. Bu derste gördüğümüz “SVD/özdeğerlerden geometri çıkarma” fikri orada graf yapısına taşınır: özvektör, düğümleri iki kümeye en doğal biçimde böler.

33.12 Anahtar Kavramlar (Cheat Sheet)

Kavram	Formül / Fikir	Strang (dk)
Üçgen eşitsizliği	$D$ geçerli ⟺ $G=X^T X$ PSD; ihlalde negatif özdeğer	0m00
Procrustes	$\min_Q \\|YQ-X\\|_F^2$ ($Q$ ortogonal)	12m07
Frobenius normu	$\\|A\\|_F^2 = \sum a_{ij}^2 = \text{tr}(A^T A) = \sum \sigma_i^2$	16m12
Q değişmezliği	$\\|QA\\|_F = \\|A\\|_F$ ($\sigma$ korunur)	18m12
İz döngüsel	$\text{tr}(CD) = \text{tr}(DC)$; $\lambda(CD)=\lambda(DC)$	22m14
Procrustes çözümü	$Y^T X = U\Sigma V^T \Rightarrow Q = UV^T$	26m15

33.13 ML Bağlantıları Özeti

Üçgen eşitsizliği / PSD: geçerli kernel/uzaklık testi (Mercer koşulu); gürültülü $G$’yi en yakın PSD’ye yansıtma (Eckart-Young).
Procrustes: nokta-bulutu kaydı (ICP, Kabsch/RMSD), şekil hizalama, çok-dilli kelime gömme hizalama (MUSE), poz/oryantasyon tahmini.
Frobenius + iz: L2/weight decay (= $\|W\|_F^2$), gradyan normu izleme, düşük-rank yaklaşım hatası; PyTorch torch.norm(·,'fro').
Q değişmezliği: ortogonal başlatma, normalleştirici akışlar, enerji koruyan dönüşümler bu özelliğe dayanır.
Çözüm Q=UVᵀ: SVD’nin “en yakın ortogonal matrisi verme” gücü (polar ayrışım, Ders 6) ile aynı kök.
Geriye köprü: Ders 33 (uzaklık/Gram), Ders 6-7 (SVD/Eckart-Young/polar), Ders 8 (Frobenius), Ders 15-16 (matris kalkülüsü/iz). Paralel: fast.ai embedding hizalama, NYU manifold öğrenme.

Kapanış

“…the best Q is— …It is UV transpose.” — Strang, 26:15

Procrustes problemi “iki şekli en iyi nasıl üst üste bindiririm” sorusuna SVD ile tek-satırlık yanıt verir; üçgen eşitsizliği codası ise geometrinin (uzaklıkların) ne zaman tutarlı olduğunu söyler — ikisi birlikte PSD ve SVD’nin ham sayılardan geometri çıkarma gücünü gösterir.

--- title: "Uzaklık Matrisleri, Procrustes Problemi" subtitle: "Üçgen eşitsizliği testi, Frobenius normu ve tek SVD ile en iyi ortogonal hizalama" --- ::: {.callout-note title="Bölüm bilgisi"} Bu ders kısa bir **coda**: Ders 33'ün uzaklık-matrisi problemini geçerlilik testiyle kapatır, sonra Procrustes problemini (en iyi ortogonal hizalama) tek bir SVD ile çözer. Strang'in [Ders 34 videosu](https://www.youtube.com/watch?v=0Qws8BuK3RQ) (≈29 dk — bu blokun kısa dersi) ve [OCW Lecture 34](https://ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/resources/lecture-34-distance-matrices-procrustes-problem-first-project/) temel alınmıştır. Okuma süresi ≈22 dk. Önkoşul Ders 33 (uzaklık/Gram matrisleri) ve Ders 6-8 (SVD/Eckart-Young/Frobenius normu). ::: ```{python} #| echo: false """ _engine34.py — MIT 18.065 Ders 34 (Üçgen Eşitsizliği Codası + Procrustes Q=UVᵀ) motor + viz. Zincir: D geçerli ⟺ G PSD (üçgen ihlali → negatif özdeğer) → Frobenius üç ifade → Q-değişmezliği → iz hileleri tr(CD)=tr(DC) → Procrustes çözümü Q = UVᵀ (+ açı-tarama optimallik tanığı). Setup hücresi = cat. Figür testi `from _engine34 import *`. matplotlib.use("Agg") burada YOK. """ import numpy as np import matplotlib.pyplot as plt from matplotlib.colors import LinearSegmentedColormap COL_PRIMARY = "#1f4e79"; COL_ACCENT = "#2e75b6"; COL_TEXT = "#13243a" COL_BG = "#eaf1f8"; COL_STEEL_300 = "#aac4dd"; COL_SKY_400 = "#6fa8dc" COL_WHITE = "#ffffff" COL_VEC1 = "#1f4e79"; COL_VEC2 = "#2e75b6"; COL_VEC3 = "#e67e22" COL_TEAL = "#17a2b8"; COL_PURPLE = "#6f42c1" NAVY_CMAP = LinearSegmentedColormap.from_list("strang_navy", ["#ffffff", "#cfe0f0", "#6fa8dc", "#2e75b6", "#1f4e79"]) DIVERGE = LinearSegmentedColormap.from_list("div", [COL_VEC3, "#ffffff", COL_PRIMARY]) def apply_style(ax): ax.set_facecolor(COL_WHITE); ax.grid(True, alpha=0.25, color=COL_STEEL_300, linewidth=0.8) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) ax.tick_params(colors=COL_TEXT); ax.title.set_color(COL_TEXT) ax.xaxis.label.set_color(COL_TEXT); ax.yaxis.label.set_color(COL_TEXT) return ax def heatmap(ax, M, title=None, cmap=None, annotate=True, fmt="{:.2g}", vmin=None, vmax=None, fontsize=11, text_thresh=None): M = np.asarray(M, dtype=float) if cmap is None: cmap = NAVY_CMAP if vmin is None: vmin = float(np.min(M)) if vmax is None: vmax = float(np.max(M)) if abs(vmax - vmin) < 1e-12: vmax = vmin + 1.0 ax.imshow(M, cmap=cmap, vmin=vmin, vmax=vmax, aspect="equal"); nr, nc = M.shape if text_thresh is None: text_thresh = vmin + 0.62*(vmax-vmin) if annotate and nr*nc <= 36: for i in range(nr): for j in range(nc): v = M[i, j] ax.text(j, i, fmt.format(v), ha="center", va="center", color=COL_WHITE if v >= text_thresh else COL_TEXT, fontsize=fontsize, fontweight="bold") ax.set_xticks(range(nc)); ax.set_yticks(range(nr)); ax.set_xticklabels([]); ax.set_yticklabels([]); ax.tick_params(length=0) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) if title: ax.set_title(title, color=COL_TEXT, fontsize=12, fontweight="bold") # ============ (1) ÜÇGEN EŞİTSİZLİĞİ ⟺ G PSD ============ def gram_centered(D): """Çift-merkezleme (centroid orijinde): G = −½·J·D·J, J = I − 11ᵀ/n. D33 özdeşliğinin d-köşegensiz hali — geçersiz D'nin PSD-ihlalini test eder.""" D = np.asarray(D, float); n = D.shape[0] J = np.eye(n) - np.ones((n, n)) / n return -0.5 * J @ D @ J def min_gram_eig(D): """G'nin en küçük özdeğeri — negatifse D geçerli konum VERMEZ (üçgen ihlali tanığı).""" return float(np.min(np.linalg.eigvalsh(gram_centered(D)))) D_STRANG_BAD = np.array([[0.0, 1, 6], [1, 0, 1], [6, 1, 0]]) # Strang açılış örneği: d13²=6 > 4 D_VALID_345 = np.array([[0.0, 9, 16], [9, 0, 25], [16, 25, 0]]) # 3-4-5 üçgeni (D33 Egz4) D_EXERCISE1 = np.array([[0.0, 1, 9], [1, 0, 1], [9, 1, 0]]) # Egz1: d13=3 > 1+1 İHLAL # ============ (3) FROBENIUS ÜÇ İFADE ============ def fro_three_ways(A): """‖A‖²_F üç yoldan: Σaᵢⱼ², tr(AᵀA), Σσᵢ² — üçü BİREBİR aynı olmalı.""" A = np.asarray(A, float) by_entries = float(np.sum(A ** 2)) by_trace = float(np.trace(A.T @ A)) by_sigma = float(np.sum(np.linalg.svd(A, compute_uv=False) ** 2)) return by_entries, by_trace, by_sigma # ============ (4-5) Q-DEĞİŞMEZLİĞİ + İZ HİLELERİ ============ def rot2(theta): """2×2 rotasyon matrisi.""" c, s = np.cos(theta), np.sin(theta) return np.array([[c, -s], [s, c]]) def q_invariance_defect(A, Q): """| ‖QA‖²_F − ‖A‖²_F | + tekil değer farkı (ikisi de ~0 olmalı).""" A = np.asarray(A, float) n1 = float(np.sum((Q @ A) ** 2)); n0 = float(np.sum(A ** 2)) s0 = np.linalg.svd(A, compute_uv=False); s1 = np.linalg.svd(Q @ A, compute_uv=False) return abs(n1 - n0), float(np.max(np.abs(np.sort(s1) - np.sort(s0)))) def trace_cyclic_defect(C, Dm): """|tr(CD) − tr(DC)| — dikdörtgenlerde bile sıfır (döngüsel iz).""" return abs(float(np.trace(C @ Dm)) - float(np.trace(Dm @ C))) def nonzero_eigs(M, tol=1e-9): """Sıfırdan-farklı özdeğerler (λ(CD) = λ(DC) tanığı için), büyüklüğe göre sıralı.""" lam = np.linalg.eigvals(M) lam = lam[np.abs(lam) > tol] return np.sort_complex(lam) # ============ (6) PROCRUSTES: Q = UVᵀ ============ def procrustes_q(X, Y): """En iyi ortogonal hizalama: YᵀX = UΣVᵀ → Q = UVᵀ (min ‖YQ − X‖_F). X, Y satırları nokta (n×d).""" U, S, Vt = np.linalg.svd(np.asarray(Y, float).T @ np.asarray(X, float)) return U @ Vt def make_procrustes_pair(n=10, theta=0.9, noise=0.0, seed=34): """X rastgele bulut; Y = X·Rᵀ (+gürültü) — gerçek rotasyon R bilinir (kurtarma tanığı).""" rng = np.random.default_rng(seed) X = rng.uniform(-2, 2, (n, 2)) R = rot2(theta) Y = X @ R.T + (rng.normal(0, noise, (n, 2)) if noise > 0 else 0.0) return X, Y, R def angle_sweep_error(X, Y, thetas): """Açı taraması: her θ için ‖Y·Q(θ) − X‖_F — SVD çözümünün TAM minimumda oturduğunun tanığı.""" return np.array([float(np.linalg.norm(Y @ rot2(t) - X)) for t in thetas]) ``` ## Bu Derste Ne Var? {#sec-bu-derste-d34} Ders **iki parça**. İlki Ders 33'ün uzaklık-matrisi probleminin **codası**: her uzaklık matrisi geçerli mi? İkincisi **Procrustes problemi**: iki vektör kümesini en iyi ortogonal dönüşümle (rotasyon) hizalama — çözümü şaşırtıcı sadelikte: $Q = UV^T$. Beş sonuç: 1. **Üçgen eşitsizliği testi:** Bir uzaklık matrisi $D$ ancak üçgen eşitsizliğini sağlıyorsa geçerli konum verir. İhlal edilirse Gram matrisi $G$ **PSD çıkmaz** (negatif özdeğer) — konum bulunamaz (⟺ koşulu). 2. **Procrustes problemi:** İki vektör kümesi $X$ ve $Y$; ortogonal $Q$ ile $YQ$'yu $X$'e en yakın yap: $\min_{Q^T Q = I} \|YQ - X\|_F^2$. 3. **Frobenius normu, üç ifade:** $\|A\|_F^2 = \sum_{i,j} a_{ij}^2 = \text{tr}(A^T A) = \sum_i \sigma_i^2$. 4. $Q$ **değişmezliği:** ortogonal $Q$ ile çarpmak Frobenius normunu (ve tekil değerleri) **değiştirmez**: $\|QA\|_F = \|A\|_F$. 5. **Çözüm:** $Y^T X$'in SVD'sini al, $Y^T X = U\Sigma V^T$; en iyi $Q = UV^T$. İspat iz (trace) özellikleriyle gelir: $\text{tr}(CD) = \text{tr}(DC)$. ```{mermaid} %%| label: fig-kavram-haritasi-l34 %%| fig-cap: "Ders 34 kavram haritasi: D33 codasi + Procrustes. Dal A ucgen esitsizligi testi - D gecerli <=> G PSD <=> ucgen saglanir; ihlal -> negatif ozdeger -> konum YOK (10 boyut da kurtarmaz). Dal B Procrustes problemi - min |YQ - X|_F, Q ortogonal (uydu/sekil hizalama). Alt-dallar: Frobenius uc ifade (girdiler = tr(A^T A) = sigma kareleri); Q-degismezligi |QA|_F = |A|_F (sigma lar korunur); iz hileleri tr(CD) = tr(DC) (dikdortgende bile, sifir-disi ozdegerler ortak); COZUM Y^T X = U Sigma V^T -> Q = U V^T (tek SVD, iterasyon yok, kapali-form = global optimum). Koprular: D33 uzaklik/Gram, D6-7 SVD/polar, D8 Frobenius, D35 graf kumeleme (sonraki); ICP/Kabsch/embedding hizalama." %%| echo: false flowchart TD C["Ders 34: coda + Procrustes"] C --> A["ucgen esitsizligi testi: D gecerli <=> G PSD <=> ucgen saglanir"] C --> B["Procrustes: min |YQ - X|_F (Q ortogonal)"] A --> A1["ihlal -> negatif ozdeger -> konum YOK"] B --> B1["Frobenius uc ifade: girdiler = tr(A^T A) = sigma kareleri"] B --> B2["Q-degismezligi: |QA|_F = |A|_F"] B --> B3["iz hileleri: tr(CD) = tr(DC)"] B --> B4["COZUM: Y^T X = U Sigma V^T -> Q = U V^T"] K1["D33 uzaklik / Gram"] K2["D6-7 SVD / polar"] K3["D8 Frobenius"] K4["D35 graf kumeleme (sonraki)"] K5["ICP / Kabsch / embedding hizalama"] K1 --> A K2 --> B4 K3 --> B1 B4 --> K4 B4 --> K5 classDef merkez fill:#1f4e79,stroke:#13243a,stroke-width:2px,color:#ffffff; classDef dal fill:#2e75b6,stroke:#1f4e79,stroke-width:1.5px,color:#ffffff; classDef vec fill:#ff8c42,stroke:#c25a16,stroke-width:1.5px,color:#1f2330; classDef teal fill:#2ca6a4,stroke:#1f6f6e,stroke-width:1.5px,color:#ffffff; class C merkez; class A,A1,B,B1,B2,B3,B4 dal; class K1,K2,K3 vec; class K4,K5 teal; ``` @fig-kavram-haritasi-l34 dersin codalı iskeletini gösterir: merkezdeki **Ders 34: coda + Procrustes** düğümünden iki dal ayrılır. Dal A üçgen eşitsizliği testi — $D$ geçerli ⟺ $G$ PSD ⟺ üçgen sağlanır; ihlal → negatif özdeğer → konum YOK (10 boyut da kurtarmaz). Dal B Procrustes problemi — $\min \|YQ - X\|_F$, $Q$ ortogonal (uydu/şekil hizalama). Alt-dallar üç araç verir: Frobenius üç ifade (girdiler = $\text{tr}(A^T A)$ = $\sigma$ kareleri); Q-değişmezliği $\|QA\|_F = \|A\|_F$; iz hileleri $\text{tr}(CD) = \text{tr}(DC)$. Hepsi tek bir çözümde toplanır: $Y^T X = U\Sigma V^T \Rightarrow Q = UV^T$ (tek SVD, iterasyon yok). Köprü düğümleri D33 (uzaklık/Gram), D6-7 (SVD/polar), D8 (Frobenius), D35 graf kümeleme (sonraki) ve ICP/Kabsch/embedding hizalama önceki/sonraki bloklara bağlar. ::: {.callout-tip title="Builder Notu — Geometri Sayılardan Çıkar"} - **Procrustes = en iyi rotasyon, kapalı-form:** iki nokta kümesini hizalamanın çözümü tek SVD. Optimizasyon gerekmez — lineer cebir doğrudan verir. - **ML köprüsü:** nokta-bulutu hizalama (ICP/Kabsch, moleküler RMSD), şekil analizi ve diller-arası word embedding hizalama hep ortogonal Procrustes çözer. - **Frobenius + iz:** veri biliminde matris "büyüklüğü" ölçüsü; iz hileleri ($\text{tr}(CD)=\text{tr}(DC)$) birçok türev/optimizasyon ispatını taşır. - **Tarihsel not:** Strang bu derste "derin öğrenme gerçekten çalışıyor mu?" sorusunu açtı — bir uzman e-postası görüşünü değiştirmiş; başarılı ağ yapıları deneyle ortaya çıkar, baştan verili değil (Pazartesi'ye bıraktı). - **Geriye köprü:** Ders 33 (uzaklık/Gram), Ders 6-7 (SVD/Eckart-Young), Ders 8 (Frobenius normu). Paralel: fast.ai embedding hizalama, NYU manifold. Bu ders iki bağımsız sonucu yan yana koyar: bir uzaklık matrisinin geçerlilik testi (üçgen eşitsizliği ⟺ $G$ PSD) ile iki vektör kümesini hizalayan en iyi rotasyon. İkisini de okurken aynı SVD'nin farklı yüzlerini ara. ::: ## 1. Üçgen Eşitsizliği: Ne Zaman Konum Bulunamaz? {#sec-ucgen-d34} Ders 33'te uzaklık matrisinden konumları kurtardık. Ama soru: her $D$ geçerli mi? Strang bir karşı-örnekle başlıyor: > *"...by the triangle inequality, the distance from x1 to x3 could not be more than 2. And when we square it, it could not be more than 4. And here it's 6." — Strang, 0:00* Üç nokta; $d_{12}=1$, $d_{23}=1$ olsun. Üçgen eşitsizliği gereği $d_{13} \leq 2$, yani $d_{13}^2 \leq 4$. Ama $D$'de $d_{13}^2=6$ yazıyorsa — imkânsız. 10 boyuta çıkmak da kurtarmaz (üçgen eşitsizliği boyuttan bağımsızdır). Ne ters gider? Gram matrisi $G = X^T X$, $D$'den türetilir ve **PSD olmalıdır** (çünkü her $X^T X$ PSD'dir). Üçgen eşitsizliği ihlal edilirse: > *"...the matrix G that comes out of that equation will turn out not to be positive definite." — Strang, 4:03* $G$ negatif özdeğer kazanır → PSD değil → karekök ($X$) yok. Güzel sonuç (Strang): $D$ **geçerli konum verir ⟺ üçgen eşitsizliği sağlanır ⟺** $G$ **PSD'dir.** ```{python} #| label: fig-ucgen-psd #| fig-cap: "Üçgen eşitsizliği uzaklık matrisinin geçerlilik testidir: ihlal G'yi PSD-dışına iter — D geçerli ⟺ G PSD. Strang örneği D=(0,1,6/1,0,1/6,1,0) çift-merkezlenmiş G'nin en küçük özdeğerini −0.333'e iter (PSD değil, konum yok); 3-4-5 üçgeni geçerli (tüm özdeğerler ≥0)." #| fig-width: 10.5 #| fig-height: 4.2 #| code-fold: true import matplotlib.pyplot as plt import numpy as np fig, (axL, axR) = plt.subplots(1, 2, figsize=(10.5, 4.2)) # ---- Sol: imkansiz ucgen ---- x1 = np.array([0.0, 0.0]); x2 = np.array([1.0, 0.0]) axL.scatter([x1[0], x2[0]], [x1[1], x2[1]], s=100, color=COL_PRIMARY, zorder=5) axL.annotate("x1", (x1[0], x1[1]), textcoords="offset points", xytext=(-12, -14), color=COL_TEXT, fontsize=11, fontweight="bold") axL.annotate("x2", (x2[0], x2[1]), textcoords="offset points", xytext=(6, -14), color=COL_TEXT, fontsize=11, fontweight="bold") # x1 merkezli yaricap sqrt(6) yay (turuncu kesik) ac = np.linspace(0, np.pi, 200) r1 = np.sqrt(6.0) axL.plot(x1[0] + r1*np.cos(ac), x1[1] + r1*np.sin(ac), "--", color=COL_VEC3, linewidth=2, label="x1 çevresi yarıçap √6") # x2 merkezli yaricap 1 yay (steel kesik) r2 = 1.0 axL.plot(x2[0] + r2*np.cos(ac), x2[1] + r2*np.sin(ac), "--", color=COL_ACCENT, linewidth=2, label="x2 çevresi yarıçap 1") axL.annotate("d13 = √6 ≈ 2.45 > d12 + d23 = 2\n→ böyle nokta YOK (10 boyut da kurtarmaz)", xy=(0.5, 1.7), ha="center", va="center", color=COL_TEXT, fontsize=9, bbox=dict(boxstyle="round,pad=0.35", fc=COL_BG, ec=COL_STEEL_300)) apply_style(axL) axL.set_aspect("equal") axL.set_xlim(-3.0, 4.0); axL.set_ylim(-0.8, 3.2) axL.legend(loc="upper right", fontsize=8) axL.set_title("İmkânsız üçgen: yaylar kesişmiyor", color=COL_TEXT, fontsize=11, fontweight="bold") # ---- Sag: G ozdegerleri gecerli vs ihlalli ---- ev_valid = np.linalg.eigvalsh(gram_centered(D_VALID_345)) ev_bad = np.linalg.eigvalsh(gram_centered(D_STRANG_BAD)) pos_valid = np.array([0, 1, 2]) pos_bad = np.array([4, 5, 6]) axR.bar(pos_valid, ev_valid, color=COL_PRIMARY, width=0.8) bad_colors = [COL_VEC3 if v < 0 else COL_ACCENT for v in ev_bad] axR.bar(pos_bad, ev_bad, color=bad_colors, width=0.8) axR.axhline(0, color="#888888", linewidth=1.0) axR.annotate("min λ = −0.333 → PSD değil", xy=(5, np.min(ev_bad)), xytext=(2.0, np.min(ev_bad) - 4.5), color=COL_TEXT, fontsize=9, arrowprops=dict(arrowstyle="->", color=COL_VEC3), bbox=dict(boxstyle="round,pad=0.3", fc=COL_BG, ec=COL_STEEL_300)) axR.set_xticks([1, 5]); axR.set_xticklabels(["3-4-5 (geçerli)", "(1,1,6) ihlâllı"]) apply_style(axR) axR.set_title("G özdeğerleri: geçerli vs ihlâllı", color=COL_TEXT, fontsize=12, fontweight="bold") fig.suptitle("Üçgen eşitsizliği uzaklık matrisinin geçerlilik testi: ihlal G'yi PSD-dışına iter — D geçerli ⟺ G PSD", color=COL_TEXT, fontsize=11, fontweight="bold") plt.tight_layout(rect=[0, 0, 1, 0.95]) plt.show() ``` @fig-ucgen-psd üçgen eşitsizliğinin geçerlilik testini iki yandan motor-tanıklı gösterir: solda imkânsız üçgen — $x_1$ ve $x_2$ arasındaki uzaklık 1, ama $D$'nin istediği $d_{13} = \sqrt{6} \approx 2.45$ için $x_1$ çevresinde yarıçap $\sqrt{6}$ yay (turuncu kesik) ile $x_2$ çevresinde yarıçap 1 yay (steel kesik) **kesişmiyor** — $d_{13} > d_{12} + d_{23} = 2$ olduğundan böyle bir nokta yoktur (10 boyut da kurtarmaz). Sağda iki $D$'nin çift-merkezlenmiş $G$ özdeğerleri yan yana: 3-4-5 üçgeni (navy, hepsi $\geq 0$) geçerli; Strang'ın bozuk örneği $(1,1,6)$ ise en küçük özdeğeri $-0.333$'e iter (turuncu bar, $\text{min }\lambda = -0.3333$) — PSD değil, konum yok. Negatif özdeğer ihlalin doğrudan imzasıdır. ::: {.callout-tip title="Builder Notu — Geçersiz Uzaklığın İmzası"} "Üçgen eşitsizliği = uzaklık matrisinin geçerlilik testi" temiz bir karakterizasyon. ML köprüsü: bir benzerlik/uzaklık matrisinin gerçek bir gömmeden gelip gelmediğini PSD testiyle anlarsın — kernel yöntemlerinde "kernel geçerli mi" (Mercer koşulu) tam bu PSD kontrolüdür. Gürültülü ölçümlerde $G$'nin küçük negatif özdeğerlerini sıfırlayıp en yakın PSD'ye yansıtırsın (Ders 7 Eckart-Young ile akraba). ::: ## 2. Procrustes Problemi: En İyi Ortogonal Hizalama {#sec-procrustes-problem} İkinci problem — adı Yunan mitinden gelir; Procrustes misafirini yatağına uydurmak için gerer ya da keserdi: > *"...Procrustes adjusted the length of the visitor to fit the bed." — Strang, 8:06* Problem: iki vektör kümen var — $X = (x_1,\dots,x_n)$ ve $Y = (y_1,\dots,y_n)$. Örnek: uydu konumlarının iki farklı hesabı; biri diğerinden kısmen döndürülmüş, üstüne yuvarlama hatası var. En iyi **ortogonal** $Q$'yu bul ki $YQ$, $X$'e olabildiğince yakın olsun: > *"...over all orthogonal Q's I want to minimize YQ minus X in the Frobenius norm." — Strang, 12:07* $$\min_{Q^T Q = I} \|YQ - X\|_F^2$$ Eğer $X$ ve $Y$ ortonormal tabanlar olsaydı tam eşitlik elde edilirdi ($Q$ ile biri diğerine tam dönerdi); değiller, bu yüzden "en iyi"yi ararız. Bu, en küçük kareler'in ortogonal-kısıtlı halidir. ```{python} #| label: fig-procrustes-problem #| fig-cap: "Procrustes problemi: iki nokta bulutu — X (hedef, navy) ve Y (X'in döndürülmüş + gürültülü hali, turuncu). Eşleşen noktalar ince gri çizgilerle bağlı. Soru: Y'yi X'e en iyi oturtan ortogonal Q nedir? (uydu konumları örneği) — min |YQ - X|_F." #| fig-width: 7.5 #| fig-height: 4.6 #| code-fold: true X, Y, R = make_procrustes_pair(noise=0.08, seed=7) fig, ax = plt.subplots(figsize=(7.5, 4.6)) for i in range(X.shape[0]): ax.plot([X[i, 0], Y[i, 0]], [X[i, 1], Y[i, 1]], color="#999999", lw=1.0, alpha=0.5, zorder=1) ax.scatter(X[:, 0], X[:, 1], s=70, color=COL_PRIMARY, label="X (hedef)", zorder=3, edgecolors="white", linewidths=0.6) ax.scatter(Y[:, 0], Y[:, 1], s=70, color=COL_VEC3, label="Y (dönmüş + gürültülü)", zorder=3, edgecolors="white", linewidths=0.6) ax.annotate("en iyi ortogonal Q? (uydu konumları örneği)", xy=(0.5, 0.02), xycoords="axes fraction", ha="center", va="bottom", fontsize=10, color=COL_TEXT, bbox=dict(boxstyle="round,pad=0.3", fc=COL_BG, ec=COL_STEEL_300)) ax.legend(loc="upper left", framealpha=0.9) apply_style(ax) ax.set_aspect("equal") ax.set_title("Procrustes problemi: Y yi X e en iyi döndüren ortogonal Q yu bul — min |YQ - X|_F", color=COL_TEXT, fontsize=11, fontweight="bold") plt.show() ``` @fig-procrustes-problem problemi somutlaştırır: navy noktalar hedef kümesi $X$, turuncu noktalar $X$'in döndürülmüş ve hafif gürültülü hali $Y$ (motorda $\text{noise}=0.08$, gerçek rotasyon $\theta = 0.9$). Eşleşen noktalar ince gri çizgilerle bağlı — her çizgi $Y$'nin bir noktasını $X$'teki karşılığına bağlar, hizasızlığı görünür kılar. Soru tam ortada: $Y$'yi $X$'e en iyi oturtan ortogonal $Q$ nedir? Uydu konumları örneği bunun pratik kalbidir — iki farklı hesap aynı geometriyi taşır, yalnız bir rotasyon (ve gürültü) farkıyla. Aradığımız $\min \|YQ - X\|_F$'i çözen $Q$. ::: {.callout-tip title="Builder Notu — Yatak ile Misafir"} "Procrustes = kısıtlı en küçük kareler (Q ortogonal)" pratik bir hizalama problemi. ML köprüsü: nokta-bulutu kaydı (point cloud registration), şekil eşleme ve diller-arası kelime gömme hizalaması ($X$=İngilizce, $Y$=Türkçe embedding; $Q$ diller arası köprü) hep bunu çözer. Kabsch algoritması (moleküler yapı RMSD) ve ICP'nin (iterative closest point) çekirdeği ortogonal Procrustes'tir. ::: ## 3. Frobenius Normu: Üç İfade {#sec-frobenius-d34} Procrustes'i çözmek için Frobenius normunu iyi tanımak gerekir. Üç eşdeğer ifadesi var: > *"...three nice expressions for the Frobenius norm." — Strang, 16:12* $$\|A\|_F^2 = \sum_{i,j} a_{ij}^2 = \text{tr}(A^T A) = \text{tr}(AA^T) = \sum_i \sigma_i^2$$ - **Girdiler:** matrisi uzun bir vektör gibi gör, tüm $a_{ij}^2$'leri topla. - **İz (trace):** $A^T A$ (veya $AA^T$) köşegen toplamı = tüm sütunların kare uzunlukları toplamı. - **Tekil değerler:** $\sigma_i^2$ toplamı — çünkü $\sigma_i^2$, $A^T A$'nın özdeğerleridir ve iz = özdeğerlerin toplamıdır. İlk ifade yazması hantal; iz ve tekil-değer biçimleri çok daha kullanışlıdır (özellikle ispatlarda). ```{python} #| label: fig-frobenius #| fig-cap: "Frobenius normunun üç dili aynı sayıyı verir: girdiler toplamı = iz = tekil-değer kareleri. Sol — A=[[3,0],[0,4]] için üçü de 25; sağ — rastgele 4×3 matriste de defect < 1e-10. İspatlarda iz/sigma formu kullanılır." #| fig-width: 10 #| fig-height: 4 #| code-fold: true fig, (axL, axR) = plt.subplots(1, 2, figsize=(10, 4)) # Sol: Egz2 — A=[[3,0],[0,4]] A2 = np.array([[3., 0], [0, 4]]) a, b, c = fro_three_ways(A2) labels = ["girdiler toplami", "tr(A^T A)", "sigma kareleri"] vals = [a, b, c] bars = axL.bar(labels, vals, color=COL_PRIMARY) for rect, v in zip(bars, vals): axL.text(rect.get_x() + rect.get_width() / 2, v, "25", ha="center", va="bottom", color=COL_TEXT, fontweight="bold") axL.set_title("A=[[3,0],[0,4]]: uc yol = 25") axL.set_ylim(0, max(vals) * 1.18) apply_style(axL) # Sag: rastgele 4x3 rng = np.random.default_rng(34) Ar = rng.uniform(-2, 2, (4, 3)) a2, b2, c2 = fro_three_ways(Ar) vals2 = [a2, b2, c2] bars2 = axR.bar(labels, vals2, color=COL_PRIMARY) for rect, v in zip(bars2, vals2): axR.text(rect.get_x() + rect.get_width() / 2, v, "{:.3f}".format(v), ha="center", va="bottom", color=COL_TEXT, fontweight="bold") axR.set_title("rastgele 4x3 te de birebir (defect < 1e-10)") axR.set_ylim(0, max(vals2) * 1.18) apply_style(axR) fig.suptitle("Frobenius normunun uc dili ayni sayiyi verir: girdiler = iz = tekil-deger kareleri — ispatlarda iz/sigma formu kullanilir") plt.show() ``` @fig-frobenius üç ifadenin birebir aynı sayıyı verdiğini motor-tanıklı gösterir: solda Egzersiz 2'nin matrisi $A=[[3,0],[0,4]]$ için üç yol da **25** çıkar — girdiler toplamı ($3^2 + 4^2$), $\text{tr}(A^T A)$ ve $\sum \sigma_i^2$ ($\sigma = (4,3)$); üç bar tıpatıp aynı yükseklikte. Sağda rastgele bir $4\times3$ matris için üç yol yine birebir eşittir (defect $< 10^{-10}$) — eşitlik özel bir matrise değil, normun tanımına bağlı. İlk ifade (girdiler) hesaplaması hantal kalır; iz ve tekil-değer biçimleri ispatlarda kullanılan formdur, çünkü $\text{tr}$ ve $\sigma$ cebirsel manipülasyona açıktır. ::: {.callout-tip title="Builder Notu — Aynı Büyüklüğün Üç Dili"} "Frobenius normu = √(Σσᵢ²) = √tr(AᵀA)" — üç dil aynı sayıyı verir. ML köprüsü: ağırlık matrisi büyüklüğü (L2/weight decay aslında Frobenius normunun karesidir), gradyan normu izleme ve düşük-rank yaklaşım hatası (Eckart-Young: atılan $\sigma$'ların kareleri) hep Frobenius'tur. PyTorch `torch.norm(A, 'fro')`. ::: ## 4. Q Değişmezliği: Ortogonal Çarpım Normu Korur {#sec-q-degismezligi} Procrustes'in anahtarı: ortogonal $Q$ ile çarpmak Frobenius normunu değiştirmez. > *"...the length of Q times any vector squared is the same as the vector squared." — Strang, 18:12* $$\|QA\|_F = \|A\|_F$$ İki kanıt: (1) $QA$'nın her sütunu $Q$ ile çarpılır; $Q$ vektör uzunluğunu korur ($\|Qv\|=\|v\|$), dolayısıyla sütun-sütun kare toplam değişmez. (2) SVD ile: $A = U\Sigma V^T$ ise $QA = (QU)\Sigma V^T$ — yalnız ilk ortogonal faktör değişir, $\Sigma$ (tekil değerler) aynı kalır: > *"...QA will have the SVD QU sigma V transpose. ...I didn't change the sigmas." — Strang, 18:12* Frobenius normu $\sigma$'lara bağlı olduğundan $Q$ onu değiştiremez. (Aynısı diğer taraf için de geçerli: $AQ'$ de tekil değerleri korur.) ```{python} #| label: fig-q-degismezligi #| fig-cap: "Ortogonal çarpım normu bozmaz: A=[[1,2],[3,4]] ve 90° rotasyon Q için A ile QA'nın tekil değerleri birebir aynı (sol), dolayısıyla ‖A‖²_F = ‖QA‖²_F = 30; Q yalnızca kolonları döndürür, uzunluklarını değiştirmez (sağ)." #| fig-width: 10 #| fig-height: 4 #| code-fold: true A3 = np.array([[1., 2], [3, 4]]) Q90 = np.array([[0., -1], [1, 0]]) fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(10, 4)) # Sol: A ve QA tekil değerleri bar yan-yana (AYNI değerler) s0 = np.linalg.svd(A3, compute_uv=False) s1 = np.linalg.svd(Q90 @ A3, compute_uv=False) x = np.arange(len(s0)) ax0.bar(x - 0.18, s0, width=0.34, color=COL_PRIMARY, label="A nin sigma lari") ax0.bar(x + 0.18, s1, width=0.34, color=COL_VEC3, label="QA nin sigma lari") ax0.set_xticks(x); ax0.set_xticklabels(["sigma 1", "sigma 2"]) ax0.set_ylabel("tekil deger") ax0.legend(loc="upper right", fontsize=9) ax0.annotate("|A|_F^2 = |QA|_F^2 = 30", xy=(0.5, 0.5), xycoords="axes fraction", ha="center", va="center", fontsize=10, color=COL_TEXT, bbox=dict(boxstyle="round", fc=COL_BG, ec=COL_STEEL_300)) ax0.set_title("tekil degerler korunur", color=COL_TEXT, fontsize=12, fontweight="bold") apply_style(ax0) # Sağ: birim çember + A kolonları (navy oklar) + QA kolonları (turuncu kesik oklar) th = np.linspace(0, 2 * np.pi, 200) ax1.plot(np.cos(th), np.sin(th), color=COL_STEEL_300, lw=0.8) QA = Q90 @ A3 labels_a = ["a1", "a2"]; labels_qa = ["Qa1", "Qa2"] for j in range(2): ax1.annotate("", xy=(A3[0, j], A3[1, j]), xytext=(0, 0), arrowprops=dict(arrowstyle="->", color=COL_PRIMARY, lw=2)) ax1.text(A3[0, j] * 1.08, A3[1, j] * 1.08, labels_a[j], color=COL_PRIMARY, fontsize=11, fontweight="bold") ax1.annotate("", xy=(QA[0, j], QA[1, j]), xytext=(0, 0), arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=2, linestyle="--")) ax1.text(QA[0, j] * 1.08, QA[1, j] * 1.08, labels_qa[j], color=COL_VEC3, fontsize=11, fontweight="bold") ax1.set_title("Q yalniz dondurur, uzunluk degismez", color=COL_TEXT, fontsize=12, fontweight="bold") apply_style(ax1) ax1.set_aspect("equal") lim = 4.6 ax1.set_xlim(-lim, lim); ax1.set_ylim(-lim, lim) fig.suptitle("Ortogonal carpim normu bozmaz: QA = (QU) Sigma V^T — sigma lar ayni kalir, Frobenius sigma lara bagli", fontsize=11, color=COL_TEXT) fig.tight_layout() plt.show() ``` @fig-q-degismezligi Q-değişmezliğini iki yandan gösterir: solda Egzersiz 3'ün matrisi $A=[[1,2],[3,4]]$ ve $90°$ rotasyon $Q$ için $A$ ile $QA$'nın tekil değerleri **birebir aynı** (navy/turuncu barlar üst üste; tekil değer farkı **8.9e-16**), dolayısıyla $\|A\|_F^2 = \|QA\|_F^2 = 30$ (defect **0.0**). Sağda birim çember üzerinde $A$'nın kolonları (navy oklar) ve $QA$'nın kolonları (turuncu kesik oklar) — $Q$ her kolonu $90°$ döndürür ama **uzunluğunu aynen korur**; oklar farklı yöne bakar, eşit uzundur. İki yan aynı mesajı söyler: $QA = (QU)\Sigma V^T$ ayrışımında yalnız ortogonal faktör değişir, $\sigma$'lar sabit kalır, Frobenius normu $\sigma$'lara bağlı olduğundan değişmez. ::: {.callout-tip title="Builder Notu — Döndürmek Normu Bozmaz"} "Ortogonal çarpım tekil değerleri ve Frobenius normunu korur" — SVD'nin temel simetrisi. ML köprüsü: ortogonal/üniter dönüşümler enerjiyi (bilgiyi) korur; bu yüzden ortogonal başlatma (orthogonal init), normalleştirici akışlar (normalizing flows) ve dönüşüme-değişmez kayıplar bu özelliğe yaslanır. Procrustes'te bu özellik, problemi bir iz (trace) maksimizasyonuna indirgememizi sağlar. ::: ## 5. İz (Trace) Hileleri {#sec-iz-dongusel} Çözüm ize dayanır, o yüzden birkaç iz özdeşliği gerekir. İz = köşegen toplamı = özdeğerlerin toplamı. > *"...the trace of A transpose B is equal to the trace of B transpose A." — Strang, 20:14* $$\text{tr}(A^T B) = \text{tr}(B^T A) = \text{tr}(BA^T)$$ Çünkü transpoz köşegeni değiştirmez (iz, transpoz altında sabittir). Dahası, **döngüsel özellik** — çarpım sırasını çevirebilirsin: $$\text{tr}(CD) = \text{tr}(DC)$$ Neden? $CD$ ile $DC$ aynı sıfırdan-farklı özdeğerlere sahiptir (dikdörtgen olsalar bile fazladan sıfır özdeğerler ize katkı yapmaz), iz = özdeğer toplamı olduğundan eşittirler. > *"...How are the eigenvalues of CD related to the eigenvalues of DC? They're the same." — Strang, 22:14* ```{python} #| label: fig-iz-dongusel #| fig-cap: "Döngüsel iz: CD (3×3) ile DC (5×5) aynı sıfır-dışı özdeğerleri taşır — dikdörtgende bile. λ(CD) = {9.07, −2.31, −2.68}; DC bu üçünü aynen taşır + orijinde 2 ekstra sıfır (ize katkı yok). tr(CD) = tr(DC), defect 0.0." #| fig-width: 7.5 #| fig-height: 4.2 #| code-fold: true rng = np.random.default_rng(34) _ = rng.uniform(-2, 2, (4, 3)) # verify ile aynı rng akışı (önce 4x3) C5 = rng.uniform(-2, 2, (3, 5)) # sonra C5 (3x5) D5 = rng.uniform(-2, 2, (5, 3)) # sonra D5 (5x3) lam_cd = np.linalg.eigvals(C5 @ D5) # 3 özdeğer (3x3) lam_dc = np.linalg.eigvals(D5 @ C5) # 5 özdeğer (5x5): 3 ortak + 2 sıfır defect = trace_cyclic_defect(C5, D5) fig, ax = plt.subplots(figsize=(7.5, 4.2)) apply_style(ax) ax.axhline(0, color=COL_STEEL_300, linewidth=0.8, zorder=0) ax.axvline(0, color=COL_STEEL_300, linewidth=0.8, zorder=0) ax.scatter(lam_cd.real, lam_cd.imag, color=COL_PRIMARY, s=120, zorder=3, label="lambda(CD) — 3x3") ax.scatter(lam_dc.real, lam_dc.imag, facecolors="none", edgecolors=COL_VEC3, s=200, linewidths=2.0, zorder=4, label="lambda(DC) — 5x5") ax.set_xlim(-4.0, 10.5); ax.set_ylim(-1.6, 1.9) # DC'nin orijindeki iki ekstra sıfırı ax.annotate("DC nin ekstra sifirlari (ize katki yok)", xy=(0, 0), xytext=(1.2, 1.25), fontsize=8.5, color=COL_TEXT, arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.2)) ax.annotate(f"tr(CD) = tr(DC) (defect {defect:.1f})", xy=(0.04, 0.05), xycoords="axes fraction", fontsize=9, color=COL_TEXT) ax.legend(fontsize=8.5, loc="upper right") ax.set_xlabel("Re"); ax.set_ylabel("Im") ax.set_title("Dongusel iz: CD (3x3) ile DC (5x5) ayni sifir-disi ozdegerleri tasir — dikdortgende bile", color=COL_TEXT, fontsize=10, fontweight="bold") plt.show() ``` @fig-iz-dongusel döngüsel iz özelliğini dikdörtgen matrislerde bile motor-tanıklı doğrular: $C$ bir $3\times5$, $D$ bir $5\times3$ matris olsun. $\lambda(CD)$ (3 navy nokta, $3\times3$) karmaşık düzlemde işaretlenir; $\lambda(DC)$ (5 turuncu halka, $5\times5$) bu üç özdeğeri **aynen** taşır — üç turuncu halka navy noktaların tam üstüne oturur — artı orijinde **2 ekstra sıfır** özdeğer, ki bunlar ize katkı yapmaz. Sonuç: $\text{tr}(CD) = \text{tr}(DC)$, defect **0.0**. İz = özdeğer toplamı olduğundan, sıfır-dışı özdeğerlerin ortaklığı izlerin eşitliğini doğrudan verir; çarpım sırasını çevirmek izi değiştirmez — Procrustes ispatının taşıyıcı kuralı. ::: {.callout-tip title="Builder Notu — Köşegen Toplamının Hileleri"} "İz döngüseldir: tr(CD)=tr(DC)" hesaplamada altın kuraldır. ML köprüsü: matris türevleri ($\partial\,\text{tr}(AX)/\partial X = A^T$), Frobenius normu = $\text{tr}(A^T A)$ ve birçok kayıp/regularizasyon ize çevrilir; iz-döngüsel hilesi ifadeleri optimize edilebilir biçime sokar. Bu, "matris kalkülüsü"nün (Ders 15-16) günlük aletidir. ::: ## 6. Çözüm: Q = UVᵀ {#sec-procrustes-cozum} Frobenius normunu açıp $Q$ değişmezliğini ve iz hilelerini kullanınca problem, bir izi maksimize etmeye iner. Cevap şaşırtıcı sadelikte: > *"...Compute Y transpose X. Compute its SVD, and use the orthogonal matrices from the SVD." — Strang, 26:15* $$Y^T X = U\Sigma V^T \quad\Longrightarrow\quad Q_{\text{opt}} = U V^T$$ Yani: verilen $X$, $Y$ için $Y^T X$ matrisini kur (iki kümenin tüm iç-çarpımları), SVD'sini al, ortogonal faktörleri çarp. $Q = UV^T$ en iyi ortogonal hizalamadır. > *"...the best Q is— Da dun da duh. ...It is UV transpose." — Strang, 26:15* $\Sigma$ (tekil değerler) düşer; geriye yalnız ortogonal $U$ ve $V$ kalır — çarpımları da ortogonaldir (iki ortogonalin çarpımı). Eğer $Y$ zaten $X$'e tam dönüyorsa $Y^T X$ ortogonal çıkar ve $UV^T$ tam o dönüşü verir. ```{python} #| label: fig-procrustes-cozum #| fig-cap: "Procrustes çözümü Q = UVᵀ: tek SVD, iterasyon yok. Sol panel hizalama öncesi ham farkı (‖Y − X‖ = 4.612) gösterir; orta panel 3600 açı adayını tarar ve SVD çözümünün (turuncu yıldız, theta = 0.9061) TAM minimumda oturduğunu — hiçbir Q(theta) ondan iyi değil — kanıtlar; sağ panel hizalama sonrası X ile Y·Q'nun üst üste düştüğünü (hata 4.612 → 0.347) gösterir. Açı taraması kapalı-formun global optimum olduğunu doğrular." #| fig-width: 12 #| fig-height: 4.2 #| code-fold: true import matplotlib.pyplot as plt import numpy as np Xn, Yn, Rn = make_procrustes_pair(noise=0.08, seed=7) Qn = procrustes_q(Xn, Yn) err_svd = np.linalg.norm(Yn @ Qn - Xn) fig, axes = plt.subplots(1, 3, figsize=(12, 4.2)) # Sol: hizalama ÖNCESİ ax = axes[0] ax.scatter(Xn[:, 0], Xn[:, 1], c=COL_PRIMARY, s=60, label="X (hedef)") ax.scatter(Yn[:, 0], Yn[:, 1], c=COL_VEC3, s=60, label="Y (dönmüş)") ax.set_title("önce: ham fark 4.612", color=COL_TEXT, fontsize=11, fontweight="bold") ax.legend(fontsize=8) apply_style(ax); ax.set_aspect("equal") # Orta: açı taraması ax = axes[1] thetas = np.linspace(0, 2*np.pi, 3600) errs = angle_sweep_error(Xn, Yn, thetas) ax.plot(thetas, errs, color=COL_PRIMARY, lw=1.8) th_q = np.arctan2(Qn[1, 0], Qn[0, 0]) % (2*np.pi) ax.scatter([th_q], [err_svd], c=COL_VEC3, marker="*", s=250, zorder=3) ax.annotate("3600 aday: hiçbiri\nSVD'den iyi değil", xy=(th_q, err_svd), xytext=(th_q + 1.4, err_svd + 1.6), fontsize=8, color=COL_TEXT, arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.2)) ax.set_xlabel("theta (radyan)"); ax.set_ylabel("|Y Q(theta) - X|_F") ax.set_title("SVD çözümü TAM minimumda (theta = 0.9061)", color=COL_TEXT, fontsize=10, fontweight="bold") apply_style(ax) # Sağ: hizalama SONRASI ax = axes[2] YQ = Yn @ Qn ax.scatter(Xn[:, 0], Xn[:, 1], c=COL_PRIMARY, s=60, label="X (hedef)") ax.scatter(YQ[:, 0], YQ[:, 1], c=COL_VEC3, s=25, label="Y·Q (hizalı)") ax.set_title("sonra: hata 4.612 -> 0.347", color=COL_TEXT, fontsize=11, fontweight="bold") ax.legend(fontsize=8) apply_style(ax); ax.set_aspect("equal") fig.suptitle("Procrustes çözümü Q = UVᵀ: tek SVD, iterasyon yok — açı taraması kapalı-formun global optimum olduğunu doğruluyor", color=COL_TEXT, fontsize=10.5, fontweight="bold") fig.tight_layout() plt.show() ``` @fig-procrustes-cozum dersin **flagship** kanıtıdır: kapalı-form çözüm $Q = UV^T$ gerçekten global optimumu verir. Solda hizalama öncesi $X$ (navy) ve $Y$ (turuncu) üst üste — ham fark $\|Y - X\| = $ **4.612**. Ortada açı taraması: $3600$ farklı $\theta$ için $\|YQ(\theta) - X\|_F$ çizilir (navy eğri); SVD çözümünün açısı $\theta = $ **0.9061** turuncu yıldızla işaretli ve eğrinin **tam minimumunda** oturur — $3600$ adayın hiçbiri SVD çözümünden iyi değil. Bu, kapalı-formun iterasyonsuz biçimde global optimum olduğunun doğrudan tanığıdır (brute-force tarama ile kapalı-form çakışır). Sağda hizalama sonrası $X$ (navy) ile $Y\cdot Q$ (küçük turuncu) neredeyse üst üste — hata $4.612 \to $ **0.347**'ye iner (kalan, eklenen gürültünün payı). Tek bir SVD, hiçbir optimizasyon döngüsü olmadan, açı-uzayını tarayan bir aramanın bulduğu optimumu verir. ::: {.callout-tip title="Builder Notu — Tek SVD ile En İyi Dönüş"} "En iyi ortogonal Q = UVᵀ ($Y^T X$'in SVD'sinden)" kapalı-form bir mücevher. ML köprüsü: bu formül ortogonal Procrustes'in standart çözümüdür — şekil hizalama, embedding hizalama (örn. çok-dilli kelime vektörleri, MUSE) ve poz tahmini hep bunu kullanır. SVD'nin "en yakın ortogonal matrisi verme" gücüyle (polar ayrışım, Ders 6) aynı kökten gelir. ::: ## Bu Dersin Özeti {#sec-ozet-d34} - **Üçgen eşitsizliği:** $D$ geçerli konum verir ⟺ üçgen eşitsizliği sağlanır ⟺ $G=X^T X$ PSD'dir (ihlalde $G$ negatif özdeğer kazanır, $X$ bulunamaz). - **Procrustes problemi:** ortogonal $Q$ üzerinden $\min \|YQ-X\|_F^2$ — iki vektör kümesini en iyi rotasyonla hizala. - **Frobenius normu:** $\|A\|_F^2 = \sum a_{ij}^2 = \text{tr}(A^T A) = \text{tr}(AA^T) = \sum \sigma_i^2$ (üç eşdeğer ifade). - **Q değişmezliği:** $\|QA\|_F = \|A\|_F$ (ortogonal çarpım tekil değerleri ve Frobenius normunu korur). - **İz hileleri:** $\text{tr}(A^T B)=\text{tr}(B^T A)$, $\text{tr}(CD)=\text{tr}(DC)$ (döngüsel; $\lambda(CD)=\lambda(DC)$ sıfırdan-farklı özdeğerler). - **Çözüm:** $Y^T X=U\Sigma V^T \Rightarrow Q=UV^T$ — en iyi ortogonal hizalama, tek bir SVD ile. ::: {.callout-important title="Tek Bir Cümle"} Bir uzaklık matrisi ancak üçgen eşitsizliğini sağlarsa konuma çevrilebilir (yoksa $G=X^T X$ PSD olmaz); Procrustes problemi ise iki vektör kümesini en iyi hizalayan ortogonal matrisi tek bir SVD ile bulur — $Y^T X=U\Sigma V^T \Rightarrow Q=UV^T$. ::: ## Kontrol Soruları {#sec-sorular-d34} ::: {.callout-note collapse="true" title="Soru 1 — Üçgen eşitsizliği ihlal edilirse ne olur; bu G'yi nasıl etkiler"} Üçgen eşitsizliği (örn. $d_{13} \leq d_{12}+d_{23}$) ihlal edilirse, $D$'den türetilen Gram matrisi $G = X^T X$ **pozitif yarı-tanımlı çıkmaz** — negatif özdeğer kazanır. PSD olmayan bir matrisin $X^T X$ biçiminde karekökü yoktur, dolayısıyla bu uzaklıkları sağlayan konumlar bulunamaz. Tam karakterizasyon: $D$ geçerli konum verir ⟺ üçgen eşitsizliği sağlanır ⟺ $G$ PSD'dir. ::: ::: {.callout-note collapse="true" title="Soru 2 — Procrustes problemi nedir; neden genelde tam eşitlik olmaz"} İki vektör kümesi $X$ ve $Y$ verili; amaç ortogonal $Q$ ile $\min_Q \|YQ - X\|_F^2$'yi çözmek ($Y$'yi $X$'e en iyi döndürmek). Tam eşitlik ancak $X$ ve $Y$ her ikisi de ortonormal tabansa ve biri diğerinin tam rotasyonuysa olur. Pratikte iki küme yuvarlama hatası/gürültü içerir ya da tam ortonormal değildir, bu yüzden "tam" değil "en iyi" hizalamayı ararız. ::: ::: {.callout-note collapse="true" title="Soru 3 — Ortogonal Q neden Frobenius normunu değiştirmez"} İki nedenle. (1) $Q$ her vektörün uzunluğunu korur ($\|Qv\|=\|v\|$); Frobenius normu sütunların kare uzunlukları toplamı olduğundan $QA$ ile $A$ aynı normda. (2) SVD ile: $A=U\Sigma V^T$ ise $QA=(QU)\Sigma V^T$ — yalnız ilk ortogonal faktör değişir, tekil değerler $\Sigma$ aynı kalır. Frobenius normu $\sqrt{\sum \sigma_i^2}$ olduğundan değişmez. ::: ::: {.callout-note collapse="true" title="Soru 4 — Procrustes çözümü nedir; nasıl hesaplanır"} İki kümenin iç-çarpım matrisi $Y^T X$'i kur, SVD'sini al: $Y^T X = U\Sigma V^T$. En iyi ortogonal matris $Q = UV^T$'dir. $\Sigma$ (tekil değerler) çözümden düşer; yalnız ortogonal faktörler $U$ ve $V$ kullanılır. Bu kapalı-form çözüm optimizasyon iterasyonu gerektirmez — tek bir SVD yeterlidir. ::: ## Egzersizler {#sec-egzersizler-d34} 1. **Üçgen testi.** Üç nokta için uzaklıklar $d_{12}=1$, $d_{23}=1$, $d_{13}=3$ (kareler 1, 1, 9). Üçgen eşitsizliği sağlanıyor mu? Bu $D$'den geçerli konumlar bulunabilir mi — Gram matrisi $G$ PSD olur mu (sezgisel açıkla)? (Motor tanığı: $d_{13}=3 > d_{12}+d_{23}=2$ → İHLAL; çift-merkezlenmiş $G$'nin en küçük özdeğeri **−0.8333** → PSD değil, konum yok. Sınır durumu $d_{13}^2=4$ (tam eşitlik): min $\lambda \approx 0$ — üç nokta bir çizgiye çöker, doğrusal dizilim.) 2. **Frobenius üç yol.** $A = [[3,0],[0,4]]$. $\|A\|_F^2$'i üç yolla hesapla: (a) girdilerin kareleri toplamı, (b) $\text{tr}(A^T A)$, (c) $\sum \sigma_i^2$ (bu köşegen matriste $\sigma$'lar nedir?). Üçü de eşit mi? (Motor tanığı: girdiler $= \text{tr}(A^T A) = \sum \sigma_i^2 = $ **25**; $\sigma = (4, 3)$.) 3. **Q değişmezliği.** $A = [[1,2],[3,4]]$, $Q = [[0,-1],[1,0]]$ ($90°$ rotasyon). $\|A\|_F^2$ ve $\|QA\|_F^2$'i hesapla; eşit olduklarını göster. (Motor tanığı: $\|A\|_F^2 = \|QA\|_F^2 = $ **30** (defect 0.0); tekil değerler birebir korunur (fark 8.9e-16).) 4. **Procrustes.** $X = [[1,0],[0,1]]$ (birim), $Y = [[0,1],[-1,0]]$ ($90°$ dönmüş). $Y^T X$'i kur, SVD'sinden $Q=UV^T$'yi bul; $Q$'nun $Y$'yi $X$'e götürdüğünü ($YQ \approx X$) doğrula. (Motor tanığı: $Q=UV^T$ ortogonal; $Y$ ortogonal olduğundan $YQ = X$ **TAM** eşitlik.) 5. **(Ders 35 habercisi)** Bir sosyal ağı (graf) iki kümeye ayırmak istiyorsun. Hangi matris ve hangi özvektör işe yarar? Bir tahmin yaz — Ders 35 "graflarda kümeler bulmak"ı (graf Laplacian'ı, Fiedler vektörü, spektral kümeleme) işliyor. ## Sonraki Ders İçin Hazırlık {#sec-sonraki-d34} **Ders 35: Graflarda Kümeler Bulmak.** Sinyal/CNN/graf bloğunun graf kısmı: bir grafı iki (veya k) kümeye ayırma (graph partitioning/clustering). Araç graf Laplacian'ı ($L = D - A$) ve onun ikinci en küçük özvektörü (Fiedler vektörü) — spektral kümeleme. Lineer cebir, ağ yapısını kümelere çevirir; Ders 19'un maxmin/özvektör fikriyle akraba. ::: {.callout-warning title="Hazırlık"} Bu dersin Egzersiz 5'inin sorduğu soruyu zihninde tut: bir grafı iki kümeye ayırmak için hangi matris ve hangi özvektör işe yarar? Ders 35 **graf Laplacian'ını** ($L = D - A$) ve onun ikinci en küçük özvektörünü (Fiedler vektörü) işler — spektral kümeleme. Bu derste gördüğümüz "SVD/özdeğerlerden geometri çıkarma" fikri orada graf yapısına taşınır: özvektör, düğümleri iki kümeye en doğal biçimde böler. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d34} | Kavram | Formül / Fikir | Strang (dk) | |--------|----------------|-------------| | Üçgen eşitsizliği | $D$ geçerli ⟺ $G=X^T X$ PSD; ihlalde negatif özdeğer | 0m00 | | **Procrustes** | $\min_Q \|YQ-X\|_F^2$ ($Q$ ortogonal) | 12m07 | | Frobenius normu | $\|A\|_F^2 = \sum a_{ij}^2 = \text{tr}(A^T A) = \sum \sigma_i^2$ | 16m12 | | Q değişmezliği | $\|QA\|_F = \|A\|_F$ ($\sigma$ korunur) | 18m12 | | İz döngüsel | $\text{tr}(CD) = \text{tr}(DC)$; $\lambda(CD)=\lambda(DC)$ | 22m14 | | Procrustes çözümü | $Y^T X = U\Sigma V^T \Rightarrow Q = UV^T$ | 26m15 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar-d34} - **Üçgen eşitsizliği / PSD:** geçerli kernel/uzaklık testi (Mercer koşulu); gürültülü $G$'yi en yakın PSD'ye yansıtma (Eckart-Young). - **Procrustes:** nokta-bulutu kaydı (ICP, Kabsch/RMSD), şekil hizalama, çok-dilli kelime gömme hizalama (MUSE), poz/oryantasyon tahmini. - **Frobenius + iz:** L2/weight decay (= $\|W\|_F^2$), gradyan normu izleme, düşük-rank yaklaşım hatası; PyTorch `torch.norm(·,'fro')`. - **Q değişmezliği:** ortogonal başlatma, normalleştirici akışlar, enerji koruyan dönüşümler bu özelliğe dayanır. - **Çözüm Q=UVᵀ:** SVD'nin "en yakın ortogonal matrisi verme" gücü (polar ayrışım, Ders 6) ile aynı kök. - **Geriye köprü:** Ders 33 (uzaklık/Gram), Ders 6-7 (SVD/Eckart-Young/polar), Ders 8 (Frobenius), Ders 15-16 (matris kalkülüsü/iz). Paralel: fast.ai embedding hizalama, NYU manifold öğrenme. ::: {.callout-important title="Kapanış"} > *"...the best Q is— ...It is UV transpose." — Strang, 26:15* Procrustes problemi "iki şekli en iyi nasıl üst üste bindiririm" sorusuna SVD ile tek-satırlık yanıt verir; üçgen eşitsizliği codası ise geometrinin (uzaklıkların) ne zaman tutarlı olduğunu söyler — ikisi birlikte PSD ve SVD'nin ham sayılardan geometri çıkarma gücünü gösterir. :::