15 A ve Tersinde Düşük-Rank Değişimler

Sherman-Morrison-Woodbury, recursive least squares, Kalman filtresi

Bölüm bilgisi

Video: MIT 18.065 — Low Rank Changes in A and Its Inverse · OCW: Lecture 14 · Okuma süresi: ≈35 dk · Eğitmen: Gilbert Strang · Önkoşul: Ders 13 (rastlantısal çarpım, rank-1 parçalar).

15.1 Bu Derste Ne Var?

Düşük-rank matrisler bölümü başlıyor. Bir matrise rank-1 (veya rank-k) bir değişim eklersen, tersini baştan hesaplamadan ucuza güncelleyebilirsin — Sherman-Morrison-Woodbury formülü.

Üç temel fikir:

Rank-1 değişim → rank-1 ters değişimi: $(I - uv^{T})^{-1} = I + \frac{uv^{T}}{1 - v^{T}u}$; $n \times n$ ters, $1 \times 1$ tersle hesaplanır.
Sherman-Morrison-Woodbury — rank-k genelleme: $n \times n$ ters, $k \times k$ tersle; $A + UV^{T}$ için genel formül.
Recursive least squares + Kalman filtresi — yeni ölçüm geldiğinde $A^{T}A$ rank-1 değişir; her şeyi yeniden hesaplama, güncelle.

Aşağıdaki kavram haritası bu dersin merkezindeki düşük-rank değişimden ana fikirlere uzanan dalları, ve ayrı bir düğüm olarak Kalman filtresinin tahmin et / ölç / düzelt döngüsünü gösterir (Şekil 15.1).

flowchart TD
    M["Düşük-rank değişim"] --> SM["(I − uvᵀ)⁻¹ = I + uvᵀ/(1 − vᵀu): n×n ters → 1×1 skaler"]
    M --> SMW["Sherman-Morrison-Woodbury: rank-k → n×n ters k×k'ya iner"]
    M --> GEN["(A + UVᵀ)⁻¹ genel formül"]
    M --> ATA["yeni ölçüm: AᵀA → AᵀA + vvᵀ (rank-1)"]
    M --> RLS["recursive least squares: baştan değil güncelle"]

    KAL["Kalman filtresi: tahmin et / ölç / düzelt"]

    style M fill:#1f4e79,color:#fff,stroke:#13243a,stroke-width:2px
    style KAL fill:#1f4e79,color:#fff,stroke:#13243a,stroke-width:2px
    style SM fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px
    style SMW fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px
    style GEN fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px
    style ATA fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px
    style RLS fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px

Şekil 15.1: Ders 14 kavram haritası: düşük-rank değişim merkezinden ana fikirlere dallar — (I − uvᵀ)⁻¹ = I + uvᵀ/(1 − vᵀu) ile n×n ters 1×1 skalere iner, Sherman-Morrison-Woodbury bunu rank-k’ya genelleyip n×n tersi k×k terse indirir, (A + UVᵀ)⁻¹ genel formülü A’nın küçük değişimini A⁻¹’in küçük değişimine bağlar, yeni ölçüm AᵀA → AᵀA + vvᵀ (rank-1) büyütür ve recursive least squares baştan hesaplamak yerine çözümü günceller; ayrı düğüm Kalman filtresi tahmin et / ölç / düzelt döngüsünü gösterir.

“today starts a new chapter about low-rank matrices.” — Strang, 0:27

Builder Notu — Bir Kez Kur Sonra Güncelle

SMW = online güncelleme: yeni veri geldikçe modeli sıfırdan eğitme; ters/çözümü rank-1 güncelle — recursive least squares, online öğrenme.
Kalman filtresi — dinamik least squares; kovaryans matrisi + durum denklemi; navigasyon, takip, sensör füzyonu.
$n \times n \to k \times k$ indirgeme — büyük tersi küçük tersle hesapla; Gauss süreçlerinde ve düşük-rank kovaryans güncellemelerinde kritik.
Rank-1 = $uv^{T}$ (kolon×satır) — Ders 1’in dış-çarpım görüşü; “küçük” demek sayılar küçük değil, rank küçük demek.

Tek cümle: $A$’ya düşük-rank bir değişim eklemek tersini de düşük-rank değiştirir; Sherman-Morrison-Woodbury bu güncellemeyi büyük tersi yeniden hesaplamadan verir — recursive least squares ve Kalman filtresinin temeli.

15.2 Düşük-Rank Matrisler (Yeni Bölüm)

Yeni bir bölüm: düşük-rank matrisler. İki tür: gerçekten düşük-rank ($uv^{T}$ gibi, rank 1) ve yaklaşık düşük-rank (tekil değerleri hızla düşen — Ders 17).

“today starts a new chapter about low-rank matrices.” — Strang, 0:27

Dikkat: “küçük” demek girdiler küçük demek değil — $uv^{T}$ tümü-milyonlar matrisi bile olabilir. Önemli olan rankın küçük olmasıdır. Bu derste soru: $A$’ya rank-1 bir değişim eklersem tersi nasıl değişir?

Aşağıdaki figür bu ayrımı görselleştirir: girdileri büyük olan bir $uv^{T}$ matrisinin yine de rankı 1’dir, çünkü tekil değerlerden sadece biri sıfırdan farklıdır (Şekil 15.2).

Kod

ub = np.array([100., 200., 50.]); vb = np.array([3., 1., 2.])
R1 = np.outer(ub, vb)
U, s, Vt = np.linalg.svd(R1)

fig, axs = plt.subplots(1, 2, figsize=(7, 3.4))
heatmap(axs[0], R1, "uv^T (girdiler büyük)", fmt="{:.0f}")
heatmap(axs[1], np.diag(s), "tekil değerler (sadece biri sıfırdan farklı)", fmt="{:.1f}")
fig.suptitle("Düşük-rank: uv^T girdileri büyük olabilir ama RANK = 1 (tek tekil değer sıfırdan farklı)",
             color=COL_TEXT, fontsize=11, fontweight="bold")
fig.tight_layout()
plt.show()

Şekil 15.2: Düşük-rank yapı: dış çarpım uvᵀ girdileri büyük olabilir, ama matrisin rankı 1’dir — tekil değerlerden sadece biri sıfırdan farklıdır.

Builder Notu — Rank Küçük Girdiler Değil

“Rank küçük, girdiler değil” ayrımı ML’de kritik: bir ağırlık matrisi büyük değerler içerse de düşük-rank olabilir (LoRA tam bunu kullanır — $\Delta W$ düşük-rank). Düşük-rank yapı, az parametreyle çok bilgi taşır.

15.3 Identity’nin Rank-1 Perturbasyonu

En basit durum: birim matrise rank-1 ekle, tersini bul. Ünlü formül (sinyal işlemede “matris ters çevirme formülü” de denir):

“I do a rank 1 perturbation. And I want to know, what’s the inverse?” — Strang, 3:00

\[(I - uv^{T})^{-1} = I + \frac{uv^{T}}{1 - v^{T}u}\]

$u$, $v$ kolon vektörler; $uv^{T}$ bir rank-1 matris (kolon×satır). Sağ tarafta $v^{T}u$ bir sayıdır ($1 \times 1$). Yani bu formül, $n \times n$ bir matrisin tersini $1 \times 1$ bir tersle (sayıyla bölme) verir.

“It’s computing an n by n inverse in terms of a 1 by 1 inverse.” — Strang, 6:12

Builder Notu — n×n’i Bölmeye İndir

$n \times n$ tersi $1 \times 1$’e indirgemek devasa tasarruf: $O(n^{3})$ yerine $O(n^{2})$. Gauss süreçleri, online regresyon ve Kalman filtreleri her yeni veri için bu formülle güncellenir — baştan ters almazlar.

15.4 Rank-1 Değişim → Rank-1 Ters

Formülün güzelliği: hem giriş ($I - uv^{T}$) hem çıkış ($I + uv^{T}/$sayı) rank-1 değişimdir. Genel kural:

“I change [a matrix] by rank 1, I change its inverse by rank 1.” — Strang, 5:20

Bir matrisi rank-1 değiştirirsen, tersi de tam olarak rank-1 değişir — hiç bariz değil ama formül bunu kanıtlar. Bu kural identity için doğru; birazdan herhangi bir $A$ için de geçerli olacak (Sherman-Morrison-Woodbury).

Builder Notu — Küçük Değişim Küçük Ters

“Rank-1 değişim → rank-1 ters değişimi” güvencesi, artımlı (incremental) algoritmaların temelidir: her güncelleme küçük (rank-1) olduğundan tersi de küçük güncellenir. Bu, milyonlarca güncelleme yapan online sistemlerde (öneri, takip) hesabı uygulanabilir kılar.

15.5 Formülü Doğrulama

İnanmıyorsan çarp: ($I - uv^{T}$) ile ($I + uv^{T}/(1-v^{T}u)$) çarpımı $I$ vermeli.

\[(I - uv^{T})\left(I + \frac{uv^{T}}{1 - v^{T}u}\right) = I + \frac{uv^{T}}{1 - v^{T}u} - uv^{T} - \frac{uv^{T}uv^{T}}{1 - v^{T}u}\]

Kilit nokta: $v^{T}u$ bir skaler, yani $uv^{T}uv^{T} = u(v^{T}u)v^{T} = (v^{T}u) \cdot uv^{T}$. Terimleri toplayınca $uv^{T}$ payı ($1 - v^{T}u$) ile sadeleşir ve geriye $I$ kalır. Skalerleri vektörlerin arasından çekip çıkarabilmek tüm ispatın anahtarı.

Aşağıdaki figür formülü sayısal olarak doğrular: $I - uv^{T}$ ile kapalı-form ters çarpılınca tam olarak birim matrisi çıkar — ortadaki $v^{T}u$ bir skaler olduğundan ters $1 \times 1$’e iner (Şekil 15.3).

Kod

u = np.array([1., 2., 0.])
v = np.array([0.5, 0., 1.])
M = np.eye(3) - np.outer(u, v)
inv = sherman_morrison_identity(u, v)

fig, axs = plt.subplots(1, 3, figsize=(10, 3.2))
heatmap(axs[0], M, "I - uv^T")
heatmap(axs[1], inv, "I + uv^T/(1 - v^T u)")
heatmap(axs[2], M @ inv, "(I - uv^T) carpi formul = I")
fig.suptitle("Formul dogrulama: (I - uv^T)(I + uv^T/(1 - v^T u)) = I; v^T u bir SKALER (1 x 1 ters)",
             color=COL_TEXT, fontsize=11, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.94])

plt.show()

Şekil 15.3: $(I - uv^{T})^{-1} = I + uv^{T}/(1 - v^{T}u)$ formülünün doğrulanması: soldaki $I - uv^{T}$ matrisi, ortadaki kapalı-form ters ile çarpılınca (sağda) tam olarak birim matrisi verir. Burada $v^{T}u$ bir SKALER olduğundan $n \times n$ ters problemi $1 \times 1$ tersine iner.

Builder Notu — Skaleri Dışarı Çek

“$v^{T}u$ skalerdir, dışarı çekebilirsin” hamlesi, Ders 1’in kolon×satır ($uv^{T}$) vs satır×kolon ($v^{T}u$) ayrımının doğrudan meyvesi. Dış-çarpım matris, iç-çarpım sayı — bu ayrımı içselleştirmek bu dersin tüm cebirini şeffaflaştırır.

15.6 Rank-k Genelleme: Sherman-Morrison-Woodbury

Şimdi $u$, $v$ yerine $n \times k$ matrisler $U$, $V$. ($I - UV^{T}$) bir rank-k değişim. Ters:

\[(I - UV^{T})^{-1} = I + U(I_{k} - V^{T}U)^{-1}V^{T}\]

Büyük fark: ortadaki ($I_{k} - V^{T}U$) artık $k \times k$ bir matris (sayı değil). Yani $n \times n$ bir tersi, $k \times k$ bir tersle hesaplıyoruz. $k$ küçükse (örn. $k=1, 2, 10$) bu devasa tasarruf. Bu, ünlü üç ismin formülü:

“…Sherman, Morrison, Woodbury…” — Strang, 14:03

Sherman ve Morrison rank-1 durumunu, Woodbury rank-k genellemesini verdi; literatürde üçü birlikte anılır.

Aşağıdaki flagship figür neden önemli olduğunu gösterir: tam ters $O(n^{3})$ ölçeklenirken SMW güncellemesi $O(n^{2}k)$ kalır; $n$ büyüdükçe iki maliyet eğrisi arasındaki uçurum açılır (Şekil 15.4).

Kod

# --- FLAGSHIP: tam ters O(n^3) vs SMW güncelleme O(n^2 k) maliyeti ---
nlist = np.array([10, 30, 100, 300, 1000])
full, smwc = cost_curve(nlist, k=1)

fig, ax = plt.subplots(figsize=(8, 4.6))
apply_style(ax)
ax.loglog(nlist, full, color=COL_VEC3, marker="s", ms=6, label="tam ters O(n³)")
ax.loglog(nlist, smwc, color=COL_PRIMARY, marker="o", ms=6, label="SMW güncelleme O(n²k), k=1")
ax.set_xlabel("matris boyutu n (log)")
ax.set_ylabel("işlem maliyeti (log)")
ax.legend()
ax.set_title(
    "Sherman-Morrison-Woodbury: n × n tersi k × k terse indirir →\n"
    "her güncelleme O(n³) yerine O(n²k)",
    color=COL_TEXT, fontsize=12, fontweight="bold",
)
plt.show()

Şekil 15.4: Sherman-Morrison-Woodbury maliyet karşılaştırması (log-log): tam matris tersi $O(n^{3})$ ölçeklenir (turuncu, eğim 3), düşük-rank SMW güncellemesi ise yalnızca $O(n^{2}k)$’dır (lacivert, $k=1$, eğim 2). $n$ büyüdükçe iki eğri arasındaki uçurum açılır — $n \times n$ matrisin tersini baştan hesaplamak yerine SMW güncellemenin maliyeti küçük $k \times k$ tersine iner. Bu, recursive least squares ve Kalman filtresinin neden her yeni ölçümde sıfırdan çözmeden güncelleyebildiğini açıklar.

Builder Notu — k×k’ya İndirge

SMW’nin ML’deki en büyük müşterisi Gauss süreçleri ve kernel yöntemleri: $n$ veri noktası için $n \times n$ kernel tersini, düşük-rank ($k$ bileşenli) bir yaklaşımla $k \times k$ terse indirger. Nyström yöntemi tam bu mantık. Büyük kovaryans matrislerini tersini almadan yönetmenin standart yolu.

15.7 Genel A için: (A + UVᵀ)⁻¹

Identity yerine herhangi bir tersinir $A$: $A$’ya rank-k bir değişim eklenince ters şöyle güncellenir:

\[(A + UV^{T})^{-1} = A^{-1} - A^{-1}U(I + V^{T}A^{-1}U)^{-1}V^{T}A^{-1}\]

$A^{-1}$’i bir kez hesaplamışsan (veya $A$’yla çözmek ucuzsa), her rank-k güncelleme için baştan ters almazsın: sadece $k \times k$ bir ters ekstra. İşte tüm pratik gücün kaynağı bu.

Builder Notu — Genel A’ya Geçiş

Bu formül online sistemlerin kalbi: $A^{-1}$ bir kez kurulur, sonra her yeni veri ($UV^{T}$) geldiğinde ters $O(n^{2}k)$ ile güncellenir — $O(n^{3})$ değil. Recommendation sistemleri, adaptive filtreler, recursive least squares ve Kalman filtresinin hepsi bu güncellemeyi döngü içinde milyonlarca kez çağırır.

15.8 Kullanım 1: Değişmiş Sistemi Çözmek

İlk pratik kullanım: ($A - uv^{T}$)$x = b$ denklemini, $A^{-1}$’i (veya $A$ ile çözmeyi) zaten biliyorken çöz. Yeni sistemi baştan kurmazsın:

\[x = (A - uv^{T})^{-1}b = A^{-1}b + \frac{A^{-1}u\,(v^{T}A^{-1}b)}{1 - v^{T}A^{-1}u}\]

İki “eski” çözüm yeter: $A$ ile $b$’yi çöz ($A^{-1}b$) ve $A$ ile $u$’yu çöz ($A^{-1}u$). Gerisi skalerle çarpma. Yani bir LU ayrıştırması elindeyse, rank-1 değişen sistemi neredeyse bedavaya çözersin.

Builder Notu — Eski Çözümü Kullan

“$A$’yı bir kez ayrıştır, sonra rank-1 değişimleri ucuza çöz” Phase 1 18.06 Ders 4’ün ($A=LU$) doğrudan devamı: LU pahalı ($O(n^{3})$) ama bir kez yapılır; her yeni sağ-taraf veya rank-1 perturbasyon $O(n^{2})$. Bu, simülasyon ve optimizasyonda matris tekrar tekrar küçük değişirken kullanılır.

15.9 Kullanım 2: Recursive Least Squares (Yeni Ölçüm)

En güzel kullanım: least squares yaparken yeni bir veri noktası gelir. Tüm $A^{T}A$’yı baştan kurup tersini almak yerine, çözümü güncelle:

“…a new measurement…” — Strang, 19:31

Yeni ölçüm = $A$’ya yeni bir satır eklemek. Bu, $A^{T}A$’yı rank-1 değiştirir (birazdan §9). SMW devreye girer ve eski çözümü düzeltme terimi ile güncelleriz. Buna recursive least squares denir:

“This is really recursive least squares.” — Strang, 28:22

Her yeni veride sıfırdan başlamazsın; mevcut tahmini yeni ölçümle düzeltirsin. Online öğrenmenin tam tanımı.

Aşağıdaki figür bunu canlandırır: satır satır gelen ölçümlerle RLS tahmini, baştan hesaplamadan rank-1 güncellemeyle gerçek çözüme yakınsar; hata logaritmik eksende hızla düşer (Şekil 15.5).

Kod

np.random.seed(0)
d = 3
xt = np.array([1.5, -2., 0.5])
rows = np.random.randn(60, d)
ys = rows @ xt + 0.01 * np.random.randn(60)
xrls, hist = recursive_least_squares(rows, ys, x_true=xt)

fig, ax = plt.subplots(figsize=(7.2, 4.2))
apply_style(ax)
ax.semilogy(range(1, len(hist) + 1), np.maximum(hist, 1e-12),
            color=COL_PRIMARY, marker="o", ms=3, label="||x_k - x_gerçek||")
ax.set_xlabel("ölçüm sayısı k")
ax.set_ylabel("tahmin hatası (log)")
ax.set_title("Recursive least squares: her yeni ölçümde tahmin gerçek çözüme yakınsar\n(baştan hesaplamadan güncelle)",
             color=COL_TEXT, fontsize=11, fontweight="bold")
ax.legend()

fig.tight_layout()
plt.show()

Şekil 15.5: Recursive least squares (RLS): satır satır gelen ölçümlerle tahmin, baştan hesaplamadan rank-1 güncellemeyle gerçek çözüme yakınsar. Hata logaritmik eksende hızla düşer.

Builder Notu — Yeni Ölçüm Geldi

Recursive least squares = SGD’nin atası. Modern ML’de her mini-batch ağırlığı günceller (eski ağırlık + düzeltme); RLS de her ölçümde tahmini günceller. Fark: RLS kapalı-form optimal düzeltme verir (ikinci dereceden bilgiyle), SGD birinci-derece adım atar. Adaptive filtreler (gürültü engelleme, eko iptali) hâlâ RLS kullanır.

15.10 AᵀA’da Rank-1 Değişim

Neden least squares’e yeni satır eklemek “rank-1 değişim”? $A$’nın altına yeni bir satır $v^{T}$ eklersen, normal denklemin matrisi $A^{T}A$ şöyle değişir:

\[A_{\text{new}}^{T}A_{\text{new}} = A^{T}A + vv^{T}\]

$vv^{T}$ bir rank-1 matris (kolon×satır, Ders 1). Yani yeni ölçüm, $A^{T}A$’yı tam olarak rank-1 büyütür:

“It’s a rank 1 change in A transpose A.” — Strang, 26:06

İşte SMW’nin neden least squares’in doğal ortağı olduğu buradan: $A^{T}A$ rank-1 değişiyor → tersi rank-1 güncelleniyor → çözüm ucuza düzeltiliyor.

Aşağıdaki figür güncellemeyi parçalarına ayırır: $A^{T}A$, eklenen $vv^{T}$ (rank-1) ve toplamları olan yeni $A^{T}A + vv^{T}$ (Şekil 15.6).

Kod

np.random.seed(0)
Ad = np.random.randn(5, 3)
vnew = np.array([1., 1., 0.5])
AtA, AtA_upd, _ = ata_rank1_update(Ad, vnew)

fig, axs = plt.subplots(1, 3, figsize=(10, 3.2))
heatmap(axs[0], AtA, "A^T A")
heatmap(axs[1], np.outer(vnew, vnew), "vv^T (rank-1)")
heatmap(axs[2], AtA_upd, "A^T A + vv^T (yeni olcum)")
fig.suptitle("Yeni olcum = A ya satir ekle -> A^T A rank-1 buyur (A^T A + vv^T) -> SMW ile cozum guncellenir")
fig.tight_layout()
plt.show()

Şekil 15.6: Yeni ölçüm = A’ya satır ekle → AᵀA rank-1 büyür (AᵀA + vvᵀ) → SMW ile çözüm güncellenir.

Builder Notu — AᵀA Rank-1 Büyür

$A^{T}A + vv^{T}$ güncellemesi Phase 1 18.06 Ders 16’nın (en küçük kareler, normal denklem $A^{T}A\hat{x} = A^{T}b$) dinamik versiyonu. Statik least squares tüm veriyi bir kerede görür; recursive versiyon veriyi akış (stream) olarak işler. Büyük veri / gerçek zamanlı sistemlerde veri belleğe sığmadığında tek seçenek budur.

15.11 Kalman Filtresi: Dinamik Least Squares

Recursive least squares’i bir adım ileri taşı: ölçülen şey de zamanla hareket ediyorsa (uçak uçuyor, fiyat değişiyor). İşte Kalman filtresi:

“…the Kalman filter…” — Strang, 27:58

Kalman filtresi iki şeyi birden yönetir: (1) yeni ölçümle tahmini düzeltmek (recursive least squares), (2) bir durum denklemi ile sistemin nasıl ilerlediğini öngörmek. İki ek malzeme: ölçümlerin güvenilirliğini tartan bir kovaryans matrisi ve durumun nasıl evrildiğini söyleyen dinamik denklem. Çekirdekte yine SMW: kovaryans matrisi her adımda düşük-rank güncellenir.

Aşağıdaki flagship figür çalışan bir Kalman filtresini gösterir: gürültülü ölçümlerden (gri) gerçek konumu (navy) takip eder (turuncu) — tahmin et / ölç / düzelt döngüsü (Şekil 15.7).

Kod

truth, meas, est = kalman_track(T=60, seed=2)
fig, ax = plt.subplots(figsize=(8, 4))
apply_style(ax)
ax.plot(truth, color=COL_PRIMARY, lw=2, label="gerçek konum")
ax.scatter(range(len(meas)), meas, color=COL_STEEL_300, s=14, alpha=0.7, label="gürültülü ölçüm")
ax.plot(est, color=COL_VEC3, lw=2, label="Kalman tahmini")
ax.set_xlabel("zaman adımı")
ax.set_ylabel("konum")
ax.set_title("Kalman filtresi: gürültülü ölçümlerden (gri) gerçek konumu (navy) takip eder (turuncu): tahmin et / ölç / düzelt", fontsize=10)
ax.legend()
plt.show()

Şekil 15.7: Kalman filtresi: gürültülü ölçümlerden (gri) gerçek konumu (navy) takip eder (turuncu) — tahmin et / ölç / düzelt.

Builder Notu — Tahmin Et Ölç Düzelt

Kalman filtresi GPS, otopilot, robot navigasyonu ve sensör füzyonunun temelidir — “tahmin et, ölç, düzelt” döngüsü. ML köprüsü: Kalman = Gauss varsayımı altında optimal Bayesçi güncelleme; derin öğrenmedeki belirsizlik tahmini (uncertainty estimation) ve durum-uzay modelleri (S4, Mamba) bu fikrin doğrudan torunları. SMW olmadan kovaryans güncellemesi her adımda $O(n^{3})$ olur — Kalman’ı gerçek zamanlı yapan tam da bu rank-k indirgemesidir.

15.12 Bu Dersin Özeti

Düşük-rank değişim → düşük-rank ters değişimi. $A$’yı rank-1 (rank-k) değiştirirsen tersi de rank-1 (rank-k) değişir.
Rank-1 formülü: $(I - uv^{T})^{-1} = I + uv^{T}/(1 - v^{T}u)$; $n \times n$ ters, $1 \times 1$ (skaler) tersle.
Sherman-Morrison-Woodbury: $(I - UV^{T})^{-1} = I + U(I_{k} - V^{T}U)^{-1}V^{T}$; $n \times n$ ters, $k \times k$ tersle. Genel $A$: $(A + UV^{T})^{-1} = A^{-1} - A^{-1}U(I + V^{T}A^{-1}U)^{-1}V^{T}A^{-1}$.
İspatın anahtarı: $v^{T}u$ skalerdir, vektörlerin arasından dışarı çekilir (iç-çarpım sayı, dış-çarpım matris — Ders 1).
Kullanım 1: rank-1 değişmiş sistemi ($A - uv^{T}$)$x = b$, $A$ çözümü elindeyken ucuza çöz.
Kullanım 2 (recursive least squares): yeni ölçüm $A^{T}A$’yı $vv^{T}$ ile rank-1 büyütür; çözümü baştan değil, düzeltme ile güncelle.
Kalman filtresi: dinamik least squares; durum denklemi + kovaryans matrisi; her adımda SMW ile düşük-rank güncelleme.

Tek Bir Cümle

$A$’ya düşük-rank bir değişim eklemek tersini de düşük-rank değiştirir; Sherman-Morrison-Woodbury bu güncellemeyi büyük tersi yeniden hesaplamadan verir ve recursive least squares ile Kalman filtresini gerçek zamanlı kılar.

15.13 Kontrol Soruları

Soru 1: Paydadaki 1 − vᵀu

$(I - uv^{T})^{-1}$ formülünde paydadaki $1 - v^{T}u$ neyi temsil eder ve neden bir sayıdır?

Cevap: $v^{T}u$ bir iç-çarpımdır (satır vektör × kolon vektör = $1 \times 1$), yani bir skalerdir. Payda $1 - v^{T}u$ bu skalerin 1’den farkı. Eğer $v^{T}u = 1$ olursa payda sıfır olur — bu durumda $I - uv^{T}$ tersinir değildir (tekildir). Formülün skaler payda ile çalışması, $n \times n$ tersi tek bir bölmeye indirgemenin tüm gücüdür.

Soru 2: SMW neye indirger

Sherman-Morrison-Woodbury $n \times n$ bir tersi neye indirger ve bu neden önemli?

Cevap: $n \times n$ tersi $k \times k$ bir terse indirger ($k$ = değişimin rankı). Önemli, çünkü $k$ genelde çok küçüktür (1, 2, birkaç on); $k \times k$ ters almak $O(k^{3})$, $n \times n$ ters almak $O(n^{3})$. $n = 10^{6}$, $k = 1$ ise fark astronomik. Online sistemler bu sayede her güncellemede baştan ters almaz.

Soru 3: Yeni ölçüm neden rank-1 değişim

Least squares’e yeni bir ölçüm eklemek neden $A^{T}A$’da rank-1 değişimdir?

Cevap: Yeni ölçüm = $A$’ya yeni bir satır $v^{T}$ eklemek. $A_{\text{new}} = [A; v^{T}]$ olunca $A_{\text{new}}^{T}A_{\text{new}} = A^{T}A + vv^{T}$ olur. $vv^{T}$ bir dış-çarpım (kolon × satır) olduğundan rank tam olarak 1’dir. Dolayısıyla normal denklem matrisi rank-1 büyür ve SMW ile çözüm ucuza güncellenir — recursive least squares.

Soru 4: Kalman’ın iki ek bileşeni

Kalman filtresini sıradan recursive least squares’ten ayıran iki ek bileşen nedir?

Cevap: (1) Bir durum denklemi — ölçülen sistemin zamanla nasıl evrildiğini (örn. hareket modeli) tanımlar; statik RLS’te durum sabittir, Kalman’da hareket eder. (2) Bir kovaryans matrisi — her ölçümün ve tahminin belirsizliğini/güvenilirliğini tartar, böylece güncelleme gürültülü ölçüme az, güvenilir ölçüme çok ağırlık verir. Çekirdek matematik yine SMW’dir.

15.14 Egzersizler

Cevapsız problemler. Çöz, sonra numpy ile kontrol et.

Egzersiz 1. Sayısal doğrulama. $u = [1, 2]^{T}$, $v = [1, 0]^{T}$ al. ($I - uv^{T}$) matrisini yaz, doğrudan tersini hesapla. Sonra formülle ($I + uv^{T}/(1-v^{T}u)$) hesapla ve aynı sonucu bulduğunu göster. $v^{T}u$ kaç çıktı?

Egzersiz 2. Tekillik sınırı. Hangi $v$ seçiminde $1 - v^{T}u = 0$ olur ($u$ sabit)? O durumda $I - uv^{T}$ matrisinin neden tersinir olmadığını, bir vektörü sıfıra götürdüğünü (çekirdek) göstererek açıkla.

Egzersiz 3. Çözümü güncelleme. $A = I$, $b = [3, 1]^{T}$, $u = [1, 0]^{T}$, $v = [0, 1]^{T}$. §7 formülüyle ($A - uv^{T}$)$x = b$ çözümünü, $A^{-1}b$’den başlayarak adım adım bul.

Egzersiz 4. AᵀA güncellemesi. $A$ $3 \times 2$ bir matris. Altına yeni satır $v^{T} = [1, 1]$ ekliyorsun. $A^{T}A + vv^{T}$’deki $vv^{T}$ matrisini açıkça yaz; rankının 1 olduğunu (tüm satırları orantılı) göster.

Egzersiz 5. (Ders 15 habercisi) Bu derste matris sabit kalıp rank-1 değişti. Ya matris bir $t$ parametresine bağlıysa, $A(t)$? Türevi $dA/dt$ ne anlama gelir, özdeğerleri $t$ değişince nasıl kayar? Bir tahmin yaz — Ders 15 bunu yanıtlıyor.

15.15 Sonraki Ders İçin Hazırlık

Ders 15: A(t) Matrisleri — Türev dA/dt ve Özdeğer Değişimi

Bu derste değişim ayrıktı (rank-1 sıçrama); Ders 15’te değişim sürekli olacak: matris bir parametreyle pürüzsüz değişirken özdeğerleri, tekil değerleri ve tersi nasıl türevlenir? Karpathy’nin backprop’unun matris versiyonuna ilk adım.

Ders 15 Öncesi Yapılacak

Bu dersin egzersizlerini çöz, özellikle Egzersiz 1’i (sayısal doğrulama) ve Egzersiz 4’ü ($A^{T}A + vv^{T}$).
Python’da bir matrise rank-1 ekleyip tersini doğrudan vs Sherman-Morrison ile hesapla, karşılaştır.
Ana cümleyi tekrar oku: “Düşük-rank değişim → düşük-rank ters değişimi; SMW $n \times n$ tersi $k \times k$ terse indirir.”

15.16 Anahtar Kavramlar (Cheat Sheet)

Kavram	Formül / Fikir	Strang (dk)
Yeni bölüm	Düşük-rank matrisler: rank küçük, girdiler değil	0m27
Rank-1 perturbasyon	$(I - uv^{T})^{-1} = I + uv^{T}/(1 - v^{T}u)$	3m00
Rank-1 → rank-1 ters	matris rank-1 değişir → tersi rank-1 değişir	5m20
n×n → 1×1	$v^{T}u$ skalerdir; büyük ters, bölmeye iner	6m12
Sherman-Morrison-Woodbury	$(I - UV^{T})^{-1} = I + U(I_{k} - V^{T}U)^{-1}V^{T}$; $n \times n \to k \times k$	14m03
Yeni ölçüm	least squares’e satır ekle → $A^{T}A$ rank-1 büyür	19m31
AᵀA rank-1 değişim	$A^{T}A + vv^{T}$ (kolon×satır dış-çarpım)	26m06
Kalman filtresi	dinamik least squares: durum denklemi + kovaryans	27m58
Recursive least squares	yeni veride sıfırdan değil, düzeltme ile güncelle	28m22

15.17 ML Bağlantıları Özeti

Online öğrenme / recursive least squares → veri akış halinde gelir, model her örnekte güncellenir; SGD’nin kapalı-form atası. Adaptive filtreler (eko/gürültü iptali) hâlâ RLS kullanır.
Kalman filtresi → GPS, otopilot, robot navigasyonu, sensör füzyonu; ML köprüsü = durum-uzay modelleri (S4, Mamba) ve Bayesçi belirsizlik tahmini.
Gauss süreçleri & kernel yöntemleri → $n \times n$ kernel tersini düşük-rank (Nyström) yaklaşımla $k \times k$ terse indirgemek tam SMW’dir.
Düşük-rank yapı → LoRA’nın $\Delta W$’si, düşük-rank kovaryans güncellemeleri; “rank küçük, girdiler değil” fikrinin üretim karşılığı.
$n \times n \to k \times k$ indirgeme → büyük tersi/çözümü küçük tersle güncelle; gerçek zamanlı sistemler.
$A^{T}A + vv^{T}$ → normal denklemin akış (stream) versiyonu; bellek sığmayan veride tek yol.
Geriye köprü → Ders 1 ($uv^{T}$ dış-çarpım), Phase 1 18.06 Ders 4 ($A=LU$ bir kez ayrıştır), normal denklem $A^{T}A\hat{x}=A^{T}b$.

Tek Şey

Eğer bu dersten tek bir şey alıp gidersen: $A$’ya düşük-rank bir değişim eklemek tersini de düşük-rank değiştirir — $(I - uv^{T})^{-1} = I + uv^{T}/(1 - v^{T}u)$ bir $n \times n$ tersi tek bir skaler bölmeye indirger, Sherman-Morrison-Woodbury ise bunu rank-k’ya ($n \times n$ ters → $k \times k$ ters) genelleştirir. Bu, yeni ölçüm geldiğinde $A^{T}A$’nın rank-1 büyümesini ($A^{T}A + vv^{T}$) ucuza güncelleyen recursive least squares ile her adımda kovaryansı düşük-rank güncelleyen Kalman filtresinin matematiksel temelidir — büyük matrisleri “bir kez kur, sonra ucuza güncelle” diliyle yönetmek.

--- title: "A ve Tersinde Düşük-Rank Değişimler" subtitle: "Sherman-Morrison-Woodbury, recursive least squares, Kalman filtresi" --- ::: {.callout-note title="Bölüm bilgisi"} **Video:** [MIT 18.065 — Low Rank Changes in A and Its Inverse](https://www.youtube.com/watch?v=XhSk_Lw2X_U) · **OCW:** Lecture 14 · **Okuma süresi:** ≈35 dk · **Eğitmen:** Gilbert Strang · **Önkoşul:** Ders 13 (rastlantısal çarpım, rank-1 parçalar). ::: ```{python} #| echo: false """ _engine14.py — MIT 18.065 Ders 14 (Düşük-Rank Değişimler, Sherman-Morrison-Woodbury) motor + viz. Setup hücresi = cat. Figür testi `from _engine14 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") # ---- Ders 14 motoru: düşük-rank değişimler / SMW ---- def sherman_morrison_identity(u, v): """(I − uvᵀ)⁻¹ = I + uvᵀ/(1 − vᵀu). u,v kolon vektör.""" u = np.asarray(u, dtype=float); v = np.asarray(v, dtype=float); n = len(u) denom = 1.0 - v @ u return np.eye(n) + np.outer(u, v) / denom def sherman_morrison(Ainv, u, v, sign=1.0): """(A + sign·uvᵀ)⁻¹ = A⁻¹ − sign·(A⁻¹u vᵀA⁻¹)/(1 + sign·vᵀA⁻¹u). Ainv = A⁻¹.""" Ainv = np.asarray(Ainv, dtype=float); u = np.asarray(u, dtype=float); v = np.asarray(v, dtype=float) Au = Ainv @ u; vA = v @ Ainv denom = 1.0 + sign * (v @ Au) return Ainv - sign * np.outer(Au, vA) / denom def smw(Ainv, U, V, sign=1.0): """(A + sign·UVᵀ)⁻¹ = A⁻¹ − sign·A⁻¹U (I + sign·VᵀA⁻¹U)⁻¹ VᵀA⁻¹. Rank-k.""" Ainv = np.asarray(Ainv, dtype=float); U = np.asarray(U, dtype=float); V = np.asarray(V, dtype=float) k = U.shape[1] AU = Ainv @ U; VA = V.T @ Ainv mid = np.eye(k) + sign * (V.T @ AU) return Ainv - sign * AU @ np.linalg.solve(mid, VA) def solve_updated_system(Ainv, b, u, v): """(A − uvᵀ)x = b çözümü A⁻¹b ve A⁻¹u ile (§7).""" Ainv = np.asarray(Ainv, dtype=float); b = np.asarray(b, dtype=float) u = np.asarray(u, dtype=float); v = np.asarray(v, dtype=float) Aib = Ainv @ b; Aiu = Ainv @ u return Aib + Aiu * (v @ Aib) / (1.0 - v @ Aiu) def ata_rank1_update(A, vnew): """Yeni ölçüm: A'ya satır vnewᵀ eklenir → AᵀA → AᵀA + vnew vnewᵀ (rank-1).""" A = np.asarray(A, dtype=float); vnew = np.asarray(vnew, dtype=float) AtA = A.T @ A A_new = np.vstack([A, vnew]) return AtA, AtA + np.outer(vnew, vnew), A_new.T @ A_new def cost_curve(n_list, k=1): """Maliyet karşılaştırma: tam ters O(n³) vs SMW güncelleme O(n²k).""" n = np.asarray(n_list, dtype=float) return n**3, n**2 * k def recursive_least_squares(rows, ys, x_true=None, lam=1e-3): """Satır satır gelen ölçümlerle RLS; her adımda tahmin (x_k) ve hata izi.""" rows = np.asarray(rows, dtype=float); ys = np.asarray(ys, dtype=float) d = rows.shape[1] P = np.eye(d) / lam # (AᵀA)⁻¹ başlangıç (büyük belirsizlik) x = np.zeros(d); hist = [] for k in range(len(ys)): a = rows[k]; y = ys[k] Pa = P @ a g = Pa / (1.0 + a @ Pa) # kazanç (SMW rank-1) x = x + g * (y - a @ x) # düzeltme P = P - np.outer(g, Pa) # P güncelle (rank-1) hist.append(np.linalg.norm(x - x_true) if x_true is not None else x.copy()) return x, np.array(hist) def kalman_track(T=50, dt=1.0, q=0.01, r=4.0, seed=0): """1D sabit-hız Kalman takibi (skaler ölçüm H=[1,0]). Gerçek durum, gürültülü ölçüm, Kalman tahmini döner.""" rng = np.random.default_rng(seed) F = np.array([[1.0, dt], [0.0, 1.0]]) Q = q * np.array([[dt**3/3, dt**2/2], [dt**2/2, dt]]) x = np.array([0.0, 1.0]) # gerçek (pozisyon, hız) xt = np.array([0.0, 0.0]); P = np.eye(2) # tahmin truth = []; meas = []; est = [] for _ in range(T): x = F @ x + rng.multivariate_normal([0, 0], Q) z = x[0] + rng.normal(0, np.sqrt(r)) # H@x = x[0] # predict xt = F @ xt; P = F @ P @ F.T + Q # update (skaler: K = P Hᵀ / (H P Hᵀ + R), H=[1,0]) S = P[0, 0] + r K = P[:, 0] / S # P Hᵀ / S, shape (2,) xt = xt + K * (z - xt[0]) P = P - np.outer(K, P[0, :]) # (I − K H) P truth.append(float(x[0])); meas.append(float(z)); est.append(float(xt[0])) return np.array(truth), np.array(meas), np.array(est) ``` ## Bu Derste Ne Var? {#sec-bu-derste-d14} Düşük-rank matrisler bölümü başlıyor. Bir matrise rank-1 (veya rank-k) bir değişim eklersen, tersini baştan hesaplamadan **ucuza güncelleyebilirsin** — Sherman-Morrison-Woodbury formülü. Üç temel fikir: 1. **Rank-1 değişim → rank-1 ters değişimi:** $(I - uv^{T})^{-1} = I + \frac{uv^{T}}{1 - v^{T}u}$; $n \times n$ ters, $1 \times 1$ tersle hesaplanır. 2. **Sherman-Morrison-Woodbury** — rank-k genelleme: $n \times n$ ters, $k \times k$ tersle; $A + UV^{T}$ için genel formül. 3. **Recursive least squares + Kalman filtresi** — yeni ölçüm geldiğinde $A^{T}A$ rank-1 değişir; her şeyi yeniden hesaplama, güncelle. Aşağıdaki kavram haritası bu dersin merkezindeki düşük-rank değişimden ana fikirlere uzanan dalları, ve ayrı bir düğüm olarak Kalman filtresinin tahmin et / ölç / düzelt döngüsünü gösterir (@fig-kavram-haritasi-l14). ```{mermaid} %%| label: fig-kavram-haritasi-l14 %%| fig-cap: "Ders 14 kavram haritası: düşük-rank değişim merkezinden ana fikirlere dallar — (I − uvᵀ)⁻¹ = I + uvᵀ/(1 − vᵀu) ile n×n ters 1×1 skalere iner, Sherman-Morrison-Woodbury bunu rank-k'ya genelleyip n×n tersi k×k terse indirir, (A + UVᵀ)⁻¹ genel formülü A'nın küçük değişimini A⁻¹'in küçük değişimine bağlar, yeni ölçüm AᵀA → AᵀA + vvᵀ (rank-1) büyütür ve recursive least squares baştan hesaplamak yerine çözümü günceller; ayrı düğüm Kalman filtresi tahmin et / ölç / düzelt döngüsünü gösterir." %%| echo: false flowchart TD M["Düşük-rank değişim"] --> SM["(I − uvᵀ)⁻¹ = I + uvᵀ/(1 − vᵀu): n×n ters → 1×1 skaler"] M --> SMW["Sherman-Morrison-Woodbury: rank-k → n×n ters k×k'ya iner"] M --> GEN["(A + UVᵀ)⁻¹ genel formül"] M --> ATA["yeni ölçüm: AᵀA → AᵀA + vvᵀ (rank-1)"] M --> RLS["recursive least squares: baştan değil güncelle"] KAL["Kalman filtresi: tahmin et / ölç / düzelt"] style M fill:#1f4e79,color:#fff,stroke:#13243a,stroke-width:2px style KAL fill:#1f4e79,color:#fff,stroke:#13243a,stroke-width:2px style SM fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px style SMW fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px style GEN fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px style ATA fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px style RLS fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px ``` > *"today starts a new chapter about low-rank matrices."* — Strang, 0:27 ::: {.callout-tip title="Builder Notu — Bir Kez Kur Sonra Güncelle"} - **SMW = online güncelleme:** yeni veri geldikçe modeli sıfırdan eğitme; ters/çözümü rank-1 güncelle — recursive least squares, online öğrenme. - **Kalman filtresi** — dinamik least squares; kovaryans matrisi + durum denklemi; navigasyon, takip, sensör füzyonu. - **$n \times n \to k \times k$ indirgeme** — büyük tersi küçük tersle hesapla; Gauss süreçlerinde ve düşük-rank kovaryans güncellemelerinde kritik. - **Rank-1 = $uv^{T}$ (kolon×satır)** — Ders 1'in dış-çarpım görüşü; "küçük" demek sayılar küçük değil, rank küçük demek. Tek cümle: $A$'ya düşük-rank bir değişim eklemek tersini de düşük-rank değiştirir; Sherman-Morrison-Woodbury bu güncellemeyi büyük tersi yeniden hesaplamadan verir — recursive least squares ve Kalman filtresinin temeli. ::: ## Düşük-Rank Matrisler (Yeni Bölüm) {#sec-yeni-bolum} Yeni bir bölüm: düşük-rank matrisler. İki tür: **gerçekten** düşük-rank ($uv^{T}$ gibi, rank 1) ve **yaklaşık** düşük-rank (tekil değerleri hızla düşen — Ders 17). > *"today starts a new chapter about low-rank matrices."* — Strang, 0:27 Dikkat: "küçük" demek girdiler küçük demek değil — $uv^{T}$ tümü-milyonlar matrisi bile olabilir. Önemli olan **rankın** küçük olmasıdır. Bu derste soru: $A$'ya rank-1 bir değişim eklersem tersi nasıl değişir? Aşağıdaki figür bu ayrımı görselleştirir: girdileri büyük olan bir $uv^{T}$ matrisinin yine de rankı 1'dir, çünkü tekil değerlerden sadece biri sıfırdan farklıdır (@fig-rank1-yapi). ```{python} #| label: fig-rank1-yapi #| fig-cap: "Düşük-rank yapı: dış çarpım uvᵀ girdileri büyük olabilir, ama matrisin rankı 1'dir — tekil değerlerden sadece biri sıfırdan farklıdır." #| fig-width: 7 #| fig-height: 3.4 #| code-fold: true ub = np.array([100., 200., 50.]); vb = np.array([3., 1., 2.]) R1 = np.outer(ub, vb) U, s, Vt = np.linalg.svd(R1) fig, axs = plt.subplots(1, 2, figsize=(7, 3.4)) heatmap(axs[0], R1, "uv^T (girdiler büyük)", fmt="{:.0f}") heatmap(axs[1], np.diag(s), "tekil değerler (sadece biri sıfırdan farklı)", fmt="{:.1f}") fig.suptitle("Düşük-rank: uv^T girdileri büyük olabilir ama RANK = 1 (tek tekil değer sıfırdan farklı)", color=COL_TEXT, fontsize=11, fontweight="bold") fig.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — Rank Küçük Girdiler Değil"} "Rank küçük, girdiler değil" ayrımı ML'de kritik: bir ağırlık matrisi büyük değerler içerse de düşük-rank olabilir (LoRA tam bunu kullanır — $\Delta W$ düşük-rank). Düşük-rank yapı, az parametreyle çok bilgi taşır. ::: ## Identity'nin Rank-1 Perturbasyonu {#sec-identity-pertur} En basit durum: birim matrise rank-1 ekle, tersini bul. Ünlü formül (sinyal işlemede "matris ters çevirme formülü" de denir): > *"I do a rank 1 perturbation. And I want to know, what's the inverse?"* — Strang, 3:00 $$(I - uv^{T})^{-1} = I + \frac{uv^{T}}{1 - v^{T}u}$$ $u$, $v$ kolon vektörler; $uv^{T}$ bir rank-1 matris (kolon×satır). Sağ tarafta $v^{T}u$ bir **sayıdır** ($1 \times 1$). Yani bu formül, $n \times n$ bir matrisin tersini $1 \times 1$ bir tersle (sayıyla bölme) verir. > *"It's computing an n by n inverse in terms of a 1 by 1 inverse."* — Strang, 6:12 ::: {.callout-tip title="Builder Notu — n×n'i Bölmeye İndir"} $n \times n$ tersi $1 \times 1$'e indirgemek devasa tasarruf: $O(n^{3})$ yerine $O(n^{2})$. Gauss süreçleri, online regresyon ve Kalman filtreleri her yeni veri için bu formülle güncellenir — baştan ters almazlar. ::: ## Rank-1 Değişim → Rank-1 Ters {#sec-rank1-ters} Formülün güzelliği: hem giriş ($I - uv^{T}$) hem çıkış ($I + uv^{T}/$sayı) rank-1 değişimdir. Genel kural: > *"I change [a matrix] by rank 1, I change its inverse by rank 1."* — Strang, 5:20 Bir matrisi rank-1 değiştirirsen, tersi de tam olarak rank-1 değişir — hiç bariz değil ama formül bunu kanıtlar. Bu kural identity için doğru; birazdan herhangi bir $A$ için de geçerli olacak (Sherman-Morrison-Woodbury). ::: {.callout-tip title="Builder Notu — Küçük Değişim Küçük Ters"} "Rank-1 değişim → rank-1 ters değişimi" güvencesi, artımlı (incremental) algoritmaların temelidir: her güncelleme küçük (rank-1) olduğundan tersi de küçük güncellenir. Bu, milyonlarca güncelleme yapan online sistemlerde (öneri, takip) hesabı uygulanabilir kılar. ::: ## Formülü Doğrulama {#sec-formul-dogrulama} İnanmıyorsan çarp: ($I - uv^{T}$) ile ($I + uv^{T}/(1-v^{T}u)$) çarpımı $I$ vermeli. $$(I - uv^{T})\left(I + \frac{uv^{T}}{1 - v^{T}u}\right) = I + \frac{uv^{T}}{1 - v^{T}u} - uv^{T} - \frac{uv^{T}uv^{T}}{1 - v^{T}u}$$ Kilit nokta: $v^{T}u$ bir skaler, yani $uv^{T}uv^{T} = u(v^{T}u)v^{T} = (v^{T}u) \cdot uv^{T}$. Terimleri toplayınca $uv^{T}$ payı ($1 - v^{T}u$) ile sadeleşir ve geriye $I$ kalır. Skalerleri vektörlerin arasından çekip çıkarabilmek tüm ispatın anahtarı. Aşağıdaki figür formülü sayısal olarak doğrular: $I - uv^{T}$ ile kapalı-form ters çarpılınca tam olarak birim matrisi çıkar — ortadaki $v^{T}u$ bir skaler olduğundan ters $1 \times 1$'e iner (@fig-formul-dogrulama). ```{python} #| label: fig-formul-dogrulama #| fig-cap: "$(I - uv^{T})^{-1} = I + uv^{T}/(1 - v^{T}u)$ formülünün doğrulanması: soldaki $I - uv^{T}$ matrisi, ortadaki kapalı-form ters ile çarpılınca (sağda) tam olarak birim matrisi verir. Burada $v^{T}u$ bir SKALER olduğundan $n \\times n$ ters problemi $1 \\times 1$ tersine iner." #| fig-width: 10 #| fig-height: 3.2 #| code-fold: true u = np.array([1., 2., 0.]) v = np.array([0.5, 0., 1.]) M = np.eye(3) - np.outer(u, v) inv = sherman_morrison_identity(u, v) fig, axs = plt.subplots(1, 3, figsize=(10, 3.2)) heatmap(axs[0], M, "I - uv^T") heatmap(axs[1], inv, "I + uv^T/(1 - v^T u)") heatmap(axs[2], M @ inv, "(I - uv^T) carpi formul = I") fig.suptitle("Formul dogrulama: (I - uv^T)(I + uv^T/(1 - v^T u)) = I; v^T u bir SKALER (1 x 1 ters)", color=COL_TEXT, fontsize=11, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.94]) plt.show() ``` ::: {.callout-tip title="Builder Notu — Skaleri Dışarı Çek"} "$v^{T}u$ skalerdir, dışarı çekebilirsin" hamlesi, Ders 1'in kolon×satır ($uv^{T}$) vs satır×kolon ($v^{T}u$) ayrımının doğrudan meyvesi. Dış-çarpım matris, iç-çarpım sayı — bu ayrımı içselleştirmek bu dersin tüm cebirini şeffaflaştırır. ::: ## Rank-k Genelleme: Sherman-Morrison-Woodbury {#sec-rank-k} Şimdi $u$, $v$ yerine $n \times k$ matrisler $U$, $V$. ($I - UV^{T}$) bir rank-k değişim. Ters: $$(I - UV^{T})^{-1} = I + U(I_{k} - V^{T}U)^{-1}V^{T}$$ Büyük fark: ortadaki ($I_{k} - V^{T}U$) artık **$k \times k$** bir matris (sayı değil). Yani $n \times n$ bir tersi, $k \times k$ bir tersle hesaplıyoruz. $k$ küçükse (örn. $k=1, 2, 10$) bu devasa tasarruf. Bu, ünlü üç ismin formülü: > *"...Sherman, Morrison, Woodbury..."* — Strang, 14:03 Sherman ve Morrison rank-1 durumunu, Woodbury rank-k genellemesini verdi; literatürde üçü birlikte anılır. Aşağıdaki flagship figür neden önemli olduğunu gösterir: tam ters $O(n^{3})$ ölçeklenirken SMW güncellemesi $O(n^{2}k)$ kalır; $n$ büyüdükçe iki maliyet eğrisi arasındaki uçurum açılır (@fig-nxn-kxk). ```{python} #| label: fig-nxn-kxk #| fig-cap: "Sherman-Morrison-Woodbury maliyet karşılaştırması (log-log): tam matris tersi $O(n^{3})$ ölçeklenir (turuncu, eğim 3), düşük-rank SMW güncellemesi ise yalnızca $O(n^{2}k)$'dır (lacivert, $k=1$, eğim 2). $n$ büyüdükçe iki eğri arasındaki uçurum açılır — $n \\times n$ matrisin tersini baştan hesaplamak yerine SMW güncellemenin maliyeti küçük $k \\times k$ tersine iner. Bu, recursive least squares ve Kalman filtresinin neden her yeni ölçümde sıfırdan çözmeden güncelleyebildiğini açıklar." #| fig-width: 8 #| fig-height: 4.6 #| code-fold: true # --- FLAGSHIP: tam ters O(n^3) vs SMW güncelleme O(n^2 k) maliyeti --- nlist = np.array([10, 30, 100, 300, 1000]) full, smwc = cost_curve(nlist, k=1) fig, ax = plt.subplots(figsize=(8, 4.6)) apply_style(ax) ax.loglog(nlist, full, color=COL_VEC3, marker="s", ms=6, label="tam ters O(n³)") ax.loglog(nlist, smwc, color=COL_PRIMARY, marker="o", ms=6, label="SMW güncelleme O(n²k), k=1") ax.set_xlabel("matris boyutu n (log)") ax.set_ylabel("işlem maliyeti (log)") ax.legend() ax.set_title( "Sherman-Morrison-Woodbury: n × n tersi k × k terse indirir →\n" "her güncelleme O(n³) yerine O(n²k)", color=COL_TEXT, fontsize=12, fontweight="bold", ) plt.show() ``` ::: {.callout-tip title="Builder Notu — k×k'ya İndirge"} SMW'nin ML'deki en büyük müşterisi Gauss süreçleri ve kernel yöntemleri: $n$ veri noktası için $n \times n$ kernel tersini, düşük-rank ($k$ bileşenli) bir yaklaşımla $k \times k$ terse indirger. Nyström yöntemi tam bu mantık. Büyük kovaryans matrislerini tersini almadan yönetmenin standart yolu. ::: ## Genel A için: (A + UVᵀ)⁻¹ {#sec-genel-a} Identity yerine herhangi bir tersinir $A$: $A$'ya rank-k bir değişim eklenince ters şöyle güncellenir: $$(A + UV^{T})^{-1} = A^{-1} - A^{-1}U(I + V^{T}A^{-1}U)^{-1}V^{T}A^{-1}$$ $A^{-1}$'i bir kez hesaplamışsan (veya $A$'yla çözmek ucuzsa), her rank-k güncelleme için baştan ters almazsın: sadece $k \times k$ bir ters ekstra. İşte tüm pratik gücün kaynağı bu. ::: {.callout-tip title="Builder Notu — Genel A'ya Geçiş"} Bu formül online sistemlerin kalbi: $A^{-1}$ bir kez kurulur, sonra her yeni veri ($UV^{T}$) geldiğinde ters $O(n^{2}k)$ ile güncellenir — $O(n^{3})$ değil. Recommendation sistemleri, adaptive filtreler, recursive least squares ve Kalman filtresinin hepsi bu güncellemeyi döngü içinde milyonlarca kez çağırır. ::: ## Kullanım 1: Değişmiş Sistemi Çözmek {#sec-kullanim1} İlk pratik kullanım: ($A - uv^{T}$)$x = b$ denklemini, $A^{-1}$'i (veya $A$ ile çözmeyi) zaten biliyorken çöz. Yeni sistemi baştan kurmazsın: $$x = (A - uv^{T})^{-1}b = A^{-1}b + \frac{A^{-1}u\,(v^{T}A^{-1}b)}{1 - v^{T}A^{-1}u}$$ İki "eski" çözüm yeter: $A$ ile $b$'yi çöz ($A^{-1}b$) ve $A$ ile $u$'yu çöz ($A^{-1}u$). Gerisi skalerle çarpma. Yani bir LU ayrıştırması elindeyse, rank-1 değişen sistemi neredeyse bedavaya çözersin. ::: {.callout-tip title="Builder Notu — Eski Çözümü Kullan"} "$A$'yı bir kez ayrıştır, sonra rank-1 değişimleri ucuza çöz" Phase 1 18.06 Ders 4'ün ($A=LU$) doğrudan devamı: LU pahalı ($O(n^{3})$) ama bir kez yapılır; her yeni sağ-taraf veya rank-1 perturbasyon $O(n^{2})$. Bu, simülasyon ve optimizasyonda matris tekrar tekrar küçük değişirken kullanılır. ::: ## Kullanım 2: Recursive Least Squares (Yeni Ölçüm) {#sec-kullanim2} En güzel kullanım: least squares yaparken **yeni bir veri noktası** gelir. Tüm $A^{T}A$'yı baştan kurup tersini almak yerine, çözümü güncelle: > *"...a new measurement..."* — Strang, 19:31 Yeni ölçüm = $A$'ya yeni bir satır eklemek. Bu, $A^{T}A$'yı rank-1 değiştirir (birazdan §9). SMW devreye girer ve eski çözümü düzeltme terimi ile güncelleriz. Buna **recursive least squares** denir: > *"This is really recursive least squares."* — Strang, 28:22 Her yeni veride sıfırdan başlamazsın; mevcut tahmini yeni ölçümle düzeltirsin. Online öğrenmenin tam tanımı. Aşağıdaki figür bunu canlandırır: satır satır gelen ölçümlerle RLS tahmini, baştan hesaplamadan rank-1 güncellemeyle gerçek çözüme yakınsar; hata logaritmik eksende hızla düşer (@fig-recursive-ls). ```{python} #| label: fig-recursive-ls #| fig-cap: "Recursive least squares (RLS): satır satır gelen ölçümlerle tahmin, baştan hesaplamadan rank-1 güncellemeyle gerçek çözüme yakınsar. Hata logaritmik eksende hızla düşer." #| fig-width: 7.2 #| fig-height: 4.2 #| code-fold: true np.random.seed(0) d = 3 xt = np.array([1.5, -2., 0.5]) rows = np.random.randn(60, d) ys = rows @ xt + 0.01 * np.random.randn(60) xrls, hist = recursive_least_squares(rows, ys, x_true=xt) fig, ax = plt.subplots(figsize=(7.2, 4.2)) apply_style(ax) ax.semilogy(range(1, len(hist) + 1), np.maximum(hist, 1e-12), color=COL_PRIMARY, marker="o", ms=3, label="||x_k - x_gerçek||") ax.set_xlabel("ölçüm sayısı k") ax.set_ylabel("tahmin hatası (log)") ax.set_title("Recursive least squares: her yeni ölçümde tahmin gerçek çözüme yakınsar\n(baştan hesaplamadan güncelle)", color=COL_TEXT, fontsize=11, fontweight="bold") ax.legend() fig.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — Yeni Ölçüm Geldi"} Recursive least squares = SGD'nin atası. Modern ML'de her mini-batch ağırlığı günceller (eski ağırlık + düzeltme); RLS de her ölçümde tahmini günceller. Fark: RLS kapalı-form optimal düzeltme verir (ikinci dereceden bilgiyle), SGD birinci-derece adım atar. Adaptive filtreler (gürültü engelleme, eko iptali) hâlâ RLS kullanır. ::: ## AᵀA'da Rank-1 Değişim {#sec-ata-rank1} Neden least squares'e yeni satır eklemek "rank-1 değişim"? $A$'nın altına yeni bir satır $v^{T}$ eklersen, normal denklemin matrisi $A^{T}A$ şöyle değişir: $$A_{\text{new}}^{T}A_{\text{new}} = A^{T}A + vv^{T}$$ $vv^{T}$ bir rank-1 matris (kolon×satır, Ders 1). Yani yeni ölçüm, $A^{T}A$'yı tam olarak rank-1 büyütür: > *"It's a rank 1 change in A transpose A."* — Strang, 26:06 İşte SMW'nin neden least squares'in doğal ortağı olduğu buradan: $A^{T}A$ rank-1 değişiyor → tersi rank-1 güncelleniyor → çözüm ucuza düzeltiliyor. Aşağıdaki figür güncellemeyi parçalarına ayırır: $A^{T}A$, eklenen $vv^{T}$ (rank-1) ve toplamları olan yeni $A^{T}A + vv^{T}$ (@fig-ata-rank1). ```{python} #| label: fig-ata-rank1 #| fig-cap: "Yeni ölçüm = A'ya satır ekle → AᵀA rank-1 büyür (AᵀA + vvᵀ) → SMW ile çözüm güncellenir." #| fig-width: 10 #| fig-height: 3.2 #| code-fold: true np.random.seed(0) Ad = np.random.randn(5, 3) vnew = np.array([1., 1., 0.5]) AtA, AtA_upd, _ = ata_rank1_update(Ad, vnew) fig, axs = plt.subplots(1, 3, figsize=(10, 3.2)) heatmap(axs[0], AtA, "A^T A") heatmap(axs[1], np.outer(vnew, vnew), "vv^T (rank-1)") heatmap(axs[2], AtA_upd, "A^T A + vv^T (yeni olcum)") fig.suptitle("Yeni olcum = A ya satir ekle -> A^T A rank-1 buyur (A^T A + vv^T) -> SMW ile cozum guncellenir") fig.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — AᵀA Rank-1 Büyür"} $A^{T}A + vv^{T}$ güncellemesi Phase 1 18.06 Ders 16'nın (en küçük kareler, normal denklem $A^{T}A\hat{x} = A^{T}b$) dinamik versiyonu. Statik least squares tüm veriyi bir kerede görür; recursive versiyon veriyi akış (stream) olarak işler. Büyük veri / gerçek zamanlı sistemlerde veri belleğe sığmadığında tek seçenek budur. ::: ## Kalman Filtresi: Dinamik Least Squares {#sec-kalman} Recursive least squares'i bir adım ileri taşı: ölçülen şey de zamanla **hareket ediyorsa** (uçak uçuyor, fiyat değişiyor). İşte Kalman filtresi: > *"...the Kalman filter..."* — Strang, 27:58 Kalman filtresi iki şeyi birden yönetir: (1) yeni ölçümle tahmini düzeltmek (recursive least squares), (2) bir **durum denklemi** ile sistemin nasıl ilerlediğini öngörmek. İki ek malzeme: ölçümlerin güvenilirliğini tartan bir **kovaryans matrisi** ve durumun nasıl evrildiğini söyleyen dinamik denklem. Çekirdekte yine SMW: kovaryans matrisi her adımda düşük-rank güncellenir. Aşağıdaki flagship figür çalışan bir Kalman filtresini gösterir: gürültülü ölçümlerden (gri) gerçek konumu (navy) takip eder (turuncu) — tahmin et / ölç / düzelt döngüsü (@fig-kalman). ```{python} #| label: fig-kalman #| fig-cap: "Kalman filtresi: gürültülü ölçümlerden (gri) gerçek konumu (navy) takip eder (turuncu) — tahmin et / ölç / düzelt." #| fig-width: 8 #| fig-height: 4 #| code-fold: true truth, meas, est = kalman_track(T=60, seed=2) fig, ax = plt.subplots(figsize=(8, 4)) apply_style(ax) ax.plot(truth, color=COL_PRIMARY, lw=2, label="gerçek konum") ax.scatter(range(len(meas)), meas, color=COL_STEEL_300, s=14, alpha=0.7, label="gürültülü ölçüm") ax.plot(est, color=COL_VEC3, lw=2, label="Kalman tahmini") ax.set_xlabel("zaman adımı") ax.set_ylabel("konum") ax.set_title("Kalman filtresi: gürültülü ölçümlerden (gri) gerçek konumu (navy) takip eder (turuncu): tahmin et / ölç / düzelt", fontsize=10) ax.legend() plt.show() ``` ::: {.callout-tip title="Builder Notu — Tahmin Et Ölç Düzelt"} Kalman filtresi GPS, otopilot, robot navigasyonu ve sensör füzyonunun temelidir — "tahmin et, ölç, düzelt" döngüsü. ML köprüsü: Kalman = Gauss varsayımı altında optimal Bayesçi güncelleme; derin öğrenmedeki belirsizlik tahmini (uncertainty estimation) ve durum-uzay modelleri (S4, Mamba) bu fikrin doğrudan torunları. SMW olmadan kovaryans güncellemesi her adımda $O(n^{3})$ olur — Kalman'ı gerçek zamanlı yapan tam da bu rank-k indirgemesidir. ::: ## Bu Dersin Özeti {#sec-ozet-d14} 1. **Düşük-rank değişim → düşük-rank ters değişimi.** $A$'yı rank-1 (rank-k) değiştirirsen tersi de rank-1 (rank-k) değişir. 2. **Rank-1 formülü:** $(I - uv^{T})^{-1} = I + uv^{T}/(1 - v^{T}u)$; $n \times n$ ters, $1 \times 1$ (skaler) tersle. 3. **Sherman-Morrison-Woodbury:** $(I - UV^{T})^{-1} = I + U(I_{k} - V^{T}U)^{-1}V^{T}$; $n \times n$ ters, $k \times k$ tersle. Genel $A$: $(A + UV^{T})^{-1} = A^{-1} - A^{-1}U(I + V^{T}A^{-1}U)^{-1}V^{T}A^{-1}$. 4. **İspatın anahtarı:** $v^{T}u$ skalerdir, vektörlerin arasından dışarı çekilir (iç-çarpım sayı, dış-çarpım matris — Ders 1). 5. **Kullanım 1:** rank-1 değişmiş sistemi ($A - uv^{T}$)$x = b$, $A$ çözümü elindeyken ucuza çöz. 6. **Kullanım 2 (recursive least squares):** yeni ölçüm $A^{T}A$'yı $vv^{T}$ ile rank-1 büyütür; çözümü baştan değil, düzeltme ile güncelle. 7. **Kalman filtresi:** dinamik least squares; durum denklemi + kovaryans matrisi; her adımda SMW ile düşük-rank güncelleme. ::: {.callout-important title="Tek Bir Cümle"} $A$'ya düşük-rank bir değişim eklemek tersini de düşük-rank değiştirir; Sherman-Morrison-Woodbury bu güncellemeyi büyük tersi yeniden hesaplamadan verir ve recursive least squares ile Kalman filtresini gerçek zamanlı kılar. ::: ## Kontrol Soruları {#sec-sorular-d14} ::: {.callout-note title="Soru 1: Paydadaki 1 − vᵀu" collapse="true"} $(I - uv^{T})^{-1}$ formülünde paydadaki $1 - v^{T}u$ neyi temsil eder ve neden bir sayıdır? **Cevap:** $v^{T}u$ bir iç-çarpımdır (satır vektör × kolon vektör = $1 \times 1$), yani bir **skalerdir**. Payda $1 - v^{T}u$ bu skalerin 1'den farkı. Eğer $v^{T}u = 1$ olursa payda sıfır olur — bu durumda $I - uv^{T}$ tersinir değildir (tekildir). Formülün skaler payda ile çalışması, $n \times n$ tersi tek bir bölmeye indirgemenin tüm gücüdür. ::: ::: {.callout-note title="Soru 2: SMW neye indirger" collapse="true"} Sherman-Morrison-Woodbury $n \times n$ bir tersi neye indirger ve bu neden önemli? **Cevap:** $n \times n$ tersi **$k \times k$** bir terse indirger ($k$ = değişimin rankı). Önemli, çünkü $k$ genelde çok küçüktür (1, 2, birkaç on); $k \times k$ ters almak $O(k^{3})$, $n \times n$ ters almak $O(n^{3})$. $n = 10^{6}$, $k = 1$ ise fark astronomik. Online sistemler bu sayede her güncellemede baştan ters almaz. ::: ::: {.callout-note title="Soru 3: Yeni ölçüm neden rank-1 değişim" collapse="true"} Least squares'e yeni bir ölçüm eklemek neden $A^{T}A$'da rank-1 değişimdir? **Cevap:** Yeni ölçüm = $A$'ya yeni bir satır $v^{T}$ eklemek. $A_{\text{new}} = [A; v^{T}]$ olunca $A_{\text{new}}^{T}A_{\text{new}} = A^{T}A + vv^{T}$ olur. $vv^{T}$ bir dış-çarpım (kolon × satır) olduğundan rank tam olarak 1'dir. Dolayısıyla normal denklem matrisi rank-1 büyür ve SMW ile çözüm ucuza güncellenir — recursive least squares. ::: ::: {.callout-note title="Soru 4: Kalman'ın iki ek bileşeni" collapse="true"} Kalman filtresini sıradan recursive least squares'ten ayıran iki ek bileşen nedir? **Cevap:** (1) Bir **durum denklemi** — ölçülen sistemin zamanla nasıl evrildiğini (örn. hareket modeli) tanımlar; statik RLS'te durum sabittir, Kalman'da hareket eder. (2) Bir **kovaryans matrisi** — her ölçümün ve tahminin belirsizliğini/güvenilirliğini tartar, böylece güncelleme gürültülü ölçüme az, güvenilir ölçüme çok ağırlık verir. Çekirdek matematik yine SMW'dir. ::: ## Egzersizler {#sec-egzersizler-d14} Cevapsız problemler. Çöz, sonra `numpy` ile kontrol et. **Egzersiz 1. Sayısal doğrulama.** $u = [1, 2]^{T}$, $v = [1, 0]^{T}$ al. ($I - uv^{T}$) matrisini yaz, doğrudan tersini hesapla. Sonra formülle ($I + uv^{T}/(1-v^{T}u)$) hesapla ve aynı sonucu bulduğunu göster. $v^{T}u$ kaç çıktı? **Egzersiz 2. Tekillik sınırı.** Hangi $v$ seçiminde $1 - v^{T}u = 0$ olur ($u$ sabit)? O durumda $I - uv^{T}$ matrisinin neden tersinir olmadığını, bir vektörü sıfıra götürdüğünü (çekirdek) göstererek açıkla. **Egzersiz 3. Çözümü güncelleme.** $A = I$, $b = [3, 1]^{T}$, $u = [1, 0]^{T}$, $v = [0, 1]^{T}$. §7 formülüyle ($A - uv^{T}$)$x = b$ çözümünü, $A^{-1}b$'den başlayarak adım adım bul. **Egzersiz 4. AᵀA güncellemesi.** $A$ $3 \times 2$ bir matris. Altına yeni satır $v^{T} = [1, 1]$ ekliyorsun. $A^{T}A + vv^{T}$'deki $vv^{T}$ matrisini açıkça yaz; rankının 1 olduğunu (tüm satırları orantılı) göster. **Egzersiz 5. (Ders 15 habercisi)** Bu derste matris **sabit** kalıp rank-1 değişti. Ya matris bir $t$ parametresine bağlıysa, $A(t)$? Türevi $dA/dt$ ne anlama gelir, özdeğerleri $t$ değişince nasıl kayar? Bir tahmin yaz — Ders 15 bunu yanıtlıyor. ## Sonraki Ders İçin Hazırlık {#sec-sonraki-d14} **Ders 15: A(t) Matrisleri — Türev dA/dt ve Özdeğer Değişimi** Bu derste değişim ayrıktı (rank-1 sıçrama); Ders 15'te değişim **sürekli** olacak: matris bir parametreyle pürüzsüz değişirken özdeğerleri, tekil değerleri ve tersi nasıl türevlenir? Karpathy'nin backprop'unun matris versiyonuna ilk adım. ::: {.callout-warning title="Ders 15 Öncesi Yapılacak"} - Bu dersin egzersizlerini çöz, özellikle Egzersiz 1'i (sayısal doğrulama) ve Egzersiz 4'ü ($A^{T}A + vv^{T}$). - Python'da bir matrise rank-1 ekleyip tersini doğrudan vs Sherman-Morrison ile hesapla, karşılaştır. - Ana cümleyi tekrar oku: "Düşük-rank değişim → düşük-rank ters değişimi; SMW $n \times n$ tersi $k \times k$ terse indirir." ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d14} | Kavram | Formül / Fikir | Strang (dk) | |--------|----------------|-------------| | **Yeni bölüm** | Düşük-rank matrisler: rank küçük, girdiler değil | 0m27 | | **Rank-1 perturbasyon** | $(I - uv^{T})^{-1} = I + uv^{T}/(1 - v^{T}u)$ | 3m00 | | **Rank-1 → rank-1 ters** | matris rank-1 değişir → tersi rank-1 değişir | 5m20 | | **n×n → 1×1** | $v^{T}u$ skalerdir; büyük ters, bölmeye iner | 6m12 | | **Sherman-Morrison-Woodbury** | $(I - UV^{T})^{-1} = I + U(I_{k} - V^{T}U)^{-1}V^{T}$; $n \times n \to k \times k$ | 14m03 | | **Yeni ölçüm** | least squares'e satır ekle → $A^{T}A$ rank-1 büyür | 19m31 | | **AᵀA rank-1 değişim** | $A^{T}A + vv^{T}$ (kolon×satır dış-çarpım) | 26m06 | | **Kalman filtresi** | dinamik least squares: durum denklemi + kovaryans | 27m58 | | **Recursive least squares** | yeni veride sıfırdan değil, düzeltme ile güncelle | 28m22 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar-d14} 1. **Online öğrenme / recursive least squares** → veri akış halinde gelir, model her örnekte güncellenir; SGD'nin kapalı-form atası. Adaptive filtreler (eko/gürültü iptali) hâlâ RLS kullanır. 2. **Kalman filtresi** → GPS, otopilot, robot navigasyonu, sensör füzyonu; ML köprüsü = durum-uzay modelleri (S4, Mamba) ve Bayesçi belirsizlik tahmini. 3. **Gauss süreçleri & kernel yöntemleri** → $n \times n$ kernel tersini düşük-rank (Nyström) yaklaşımla $k \times k$ terse indirgemek tam SMW'dir. 4. **Düşük-rank yapı** → LoRA'nın $\Delta W$'si, düşük-rank kovaryans güncellemeleri; "rank küçük, girdiler değil" fikrinin üretim karşılığı. 5. **$n \times n \to k \times k$ indirgeme** → büyük tersi/çözümü küçük tersle güncelle; gerçek zamanlı sistemler. 6. **$A^{T}A + vv^{T}$** → normal denklemin akış (stream) versiyonu; bellek sığmayan veride tek yol. 7. **Geriye köprü** → Ders 1 ($uv^{T}$ dış-çarpım), Phase 1 18.06 Ders 4 ($A=LU$ bir kez ayrıştır), normal denklem $A^{T}A\hat{x}=A^{T}b$. ::: {.callout-important title="Tek Şey"} Eğer bu dersten tek bir şey alıp gidersen: **$A$'ya düşük-rank bir değişim eklemek tersini de düşük-rank değiştirir — $(I - uv^{T})^{-1} = I + uv^{T}/(1 - v^{T}u)$ bir $n \times n$ tersi tek bir skaler bölmeye indirger, Sherman-Morrison-Woodbury ise bunu rank-k'ya ($n \times n$ ters → $k \times k$ ters) genelleştirir. Bu, yeni ölçüm geldiğinde $A^{T}A$'nın rank-1 büyümesini ($A^{T}A + vv^{T}$) ucuza güncelleyen recursive least squares ile her adımda kovaryansı düşük-rank güncelleyen Kalman filtresinin matematiksel temelidir — büyük matrisleri "bir kez kur, sonra ucuza güncelle" diliyle yönetmek.** :::