3.4 Sajátérték, SVD és spektrális határ

3.4.1 Cél, előismeret és induló kérdés

A 3.3. Vetítés, legkisebb négyzetek és kondicionáltság a legkisebb négyzetes feladatot vetítésként és normálegyenletként vizsgálta. Ott a kondíciószámot már megelőlegeztük, mélyebb definíció nélkül. Most az a kérdés, hogy egy $A\in\mathbb R^{m\times n}$ lineáris leképezés mely irányban nyújtja a legerősebben az egységvektorokat, és ez a maximális nyújtás hogyan ad felső korlátot minden $\|Ax\|_2$ értékre.

Induló becslésként használjuk az oszlopnormákat. Ha $A$ oszlopai legfeljebb $1$ hosszúak, akkor a háromszög-egyenlőtlenséggel $$\|Ax\|_2\le \sum_j |x_j|\,\|a_j\|_2\le \sum_j |x_j|\le \sqrt n\,\|x\|_2,$$ tehát valamilyen $\sqrt n$-es korlát mindig van. Ez azonban általában nem éles: ortogonális oszlopú mátrixra a maximális nyújtás $1$, nem $\sqrt n$. A fejezet célja az éles állandó, a spektrális norma bevezetése.

A 3.3. Vetítés, legkisebb négyzetek és kondicionáltság alfejezetből ismert az ortogonális mátrix fogalma, a vetítés és a ranghiány alapgondolata. A 2.4. Kis tudományos szoftverprojekt alfejezetből a kódprojekt-fegyelem: explicit input, reprodukálható ellenőrzés, futási jegyzék. Az itteni labor ugyanezt a formát követi.

3.4.2 Sajátérték és amiért nem elég

Definíció. Legyen $A\in\mathbb R^{n\times n}$ négyzetes mátrix. A $\lambda\in\mathbb C$ szám sajátértéke $A$-nak, ha létezik $v\neq 0$, $v\in\mathbb C^n$, amelyre $$Av=\lambda v .$$

A $v$ vektor a $\lambda$-hoz tartozó sajátvektor. A definíció csak négyzetes mátrixra van értelmezve, mert $Av$ és $\lambda v$ alakjának meg kell egyeznie. Az $x\mapsto Ax$ leképezés tehát egy sajátirányban csak skáláz: a kép párhuzamos az inputtal.

A sajátérték nem mindig jellemzi a torzítást. Tekintsük a $$J=\begin{pmatrix}0&1\\0&0\end{pmatrix}$$ mátrixot. Karakterisztikus polinomja $\lambda^2$, tehát egyetlen sajátértéke $\lambda=0$, algebrai multiplicitással $2$. A leképezés mégsem nulla: $Je_2=e_1$, így a $e_2$ egységvektor képe $1$ hosszú. Általában egy nem szimmetrikus mátrix sajátvektorai nem alkotnak ortonormált bázist, ezért a maximális nyújtást nem olvashatjuk le pusztán a legnagyobb $|\lambda|$-ból. Erre való a szinguláris érték.

3.4.3 A teljes SVD-tétel és a szinguláris értékek

Tétel (teljes SVD, felhasznált állítás). Minden $A\in\mathbb R^{m\times n}$ mátrix előáll $$A=U\Sigma V^{\top},$$ alakban, ahol $U\in\mathbb R^{m\times m}$ és $V\in\mathbb R^{n\times n}$ ortogonális mátrixok, $\Sigma\in\mathbb R^{m\times n}$ olyan mátrix, amelynek csak a $\Sigma_{ii},\ i=1,\dots,\min(m,n)$ elemei lehetnek nullától különbözők, és ezek $$\sigma_1\ge \sigma_2\ge\dots\ge\sigma_r>0,\qquad \sigma_{r+1}=\dots=\sigma_{\min(m,n)}=0$$ szerint rendezettek. Az $r$ a mátrix rangja, a $\sigma_i$ számok a szinguláris értékek. Ebből következnek a kapcsolatok $$Av_i=\sigma_i u_i,\qquad A^{\top}u_i=\sigma_i v_i\qquad(i=1,\dots,r).$$

Ezt a létezési és ortonormáltsági állítást a [B01] tárgyalja; a teljes bizonyítást itt tudatosan nem másoljuk, a kézirat csak az itt megnevezett állításait használja. A felhasznált rész tehát: $U,V$ ortogonális, $\Sigma$ diagonális szerkezetű, és a nemnulla $\sigma_i$-k száma $r$.

A redukált SVD elhagyja a nulla szinguláris értékekhez tartozó oszlopokat: $$A=U_r\Sigma_r V_r^{\top},$$ ahol $U_r\in\mathbb R^{m\times r}$, $\Sigma_r\in\mathbb R^{r\times r}$ pozitív diagonális, $V_r\in\mathbb R^{n\times r}$. Mivel $A$ képtere legfeljebb $r$-dimenziós, a redukált alak is egzakt egyenlőség.

Rang. Az $A$ rangja a képtér dimenziója, azaz a lineárisan független oszlopok száma. A fenti tételben éppen a pozitív szinguláris értékek száma. Az $A$ magtere a nulla szinguláris értékhez tartozó jobb oldali szinguláris vektorok terének feszítője, képtérét pedig az $u_1,\dots,u_r$ vektorok feszítik. A gyakorlatban a rangot gyakran numerikus küszöbbel becsüljük: a nagyon kicsi $\sigma_i$-t nulla rangnak tekintjük, de ez a skálafüggő küszöb heurisztika, nem a matematikai rang definíciója.

Kézi példa. $$A=\begin{pmatrix}3&0\\4&0\end{pmatrix}.$$ A mátrix második oszlopa nulla, ezért a képtér az $\binom{3}{4}$ által feszített egyenes, tehát $\operatorname{rank}(A)=1$. Az SVD: $$U=\begin{pmatrix}3/5&-4/5\\4/5&3/5\end{pmatrix},\quad \Sigma=\begin{pmatrix}5&0\\0&0\end{pmatrix},\quad V=\begin{pmatrix}1&0\\0&1\end{pmatrix}.$$ Ellenőrzésül: $$U\Sigma V^{\top}= \begin{pmatrix}3/5\\4/5\end{pmatrix}5\begin{pmatrix}1&0\end{pmatrix} =\begin{pmatrix}3&0\\4&0\end{pmatrix}=A.$$ Tehát $\sigma_1=5$, $\sigma_2=0$. Az $Ae_1=\binom{3}{4}$ vektor hossza $5$, az $Ae_2=0$; a maximális nyújtás sejthetően $5$. A könyvtári ellenőrző munkamenet, jelölt várt kimenettel (a kód e kézirat írásakor nem futtatott mérés):

import numpy as np

A = np.array([[3.0, 0.0],
              [4.0, 0.0]], dtype=np.float64)
print(np.linalg.svd(A, compute_uv=False))
# Várt: [5. 0.]
print(np.linalg.matrix_rank(A))
# Várt: 1

Az $A^{\top}A$ mátrix $\binom{25\ 0}{0\ 0}$, sajátértékei $25$ és $0$; a pozitív sajátérték négyzetgyöke éppen $\sigma_1=5$. Általában $A^{\top}A=V\Sigma^{\top}\Sigma V^{\top}$, tehát $A^{\top}A$ sajátértékei a $\sigma_i^2$ értékek. Numerikusan mégsem az $A^{\top}A$ sajátfelbontásából számolunk szinguláris értékeket, mert a kondíciószám négyzetre emelkedik; az np.linalg.svd közvetlenül az $A$-n dolgozik.

3.4.4 Spektrális norma és a normakorlát levezetése

Definíció. Az $A\in\mathbb R^{m\times n}$ mátrix spektrális normája $$\|A\|_2=\max_{\|x\|_2=1}\|Ax\|_2.$$ Ez a leképezés maximális nyújtási aránya. A maximum létezik, mert véges dimenzióban az egységgömb kompakt, és az $x\mapsto \|Ax\|_2$ függvény folytonos.

Először a kötelező levezetést diagonális operátorra végezzük el.

Lemma (diagonális operátor normakorlátja). Legyen $D\in\mathbb R^{m\times n}$ olyan mátrix, amelynek csak a $D_{ii}=d_i$, $i=1,\dots,q=\min(m,n)$ elemei lehetnek nullától különbözők. Ekkor $$\|D\|_2=\max_{1\le i\le q}|d_i|.$$

Bizonyítás. Legyen $d_*=\max_i |d_i|$, és legyen $j$ olyan index, amelyre $|d_j|=d_*$. Az $e_j\in\mathbb R^n$ standard egységvektorra $De_j=d_j e_j$ teljesül, tehát $$\|De_j\|_2=|d_j|=d_*,$$ így $\|D\|_2\ge d_*$.

A felső korláthoz legyen $x\in\mathbb R^n$, $\|x\|_2=1$. A diagonális szerkezetből $(Dx)_i=d_i x_i$ az $i\le q$ koordinátákra, és nulla a többi helyen. Ezért $$\|Dx\|_2^2=\sum_{i=1}^{q}d_i^2 x_i^2 \le d_*^2\sum_{i=1}^{q}x_i^2 \le d_*^2\sum_{i=1}^{n}x_i^2 =d_*^2\|x\|_2^2 =d_*^2.$$ Négyzetgyököt vonva $\|Dx\|_2\le d_*$, és mivel ez minden egységvektorra igaz, $\|D\|_2\le d_*$. A két egyenlőtlenségből az állítás. $\square$

A tetszőleges $A$ esetét erre vezetjük vissza a megnevezett SVD-állítás segítségével.

Levezetés: a spektrális norma SVD-ből. Legyen $A=U\Sigma V^{\top}$ teljes SVD. Egy tetszőleges egységvektorra legyen $y=V^{\top}x$. Mivel $V$ ortogonális, $$\|y\|_2^2=y^{\top}y=x^{\top}VV^{\top}x=x^{\top}x=\|x\|_2^2,$$ tehát $y$ is egységvektor. Hasonlóan $U$ ortogonalitása miatt $\|Uz\|_2=\|z\|_2$. Így $$\|Ax\|_2=\|U\Sigma V^{\top}x\|_2=\|\Sigma(V^{\top}x)\|_2=\|\Sigma y\|_2.$$ A lemma szerint $\|\Sigma y\|_2\le \sigma_1\|y\|_2=\sigma_1\|x\|_2$, mert a $\Sigma$ diagonális elemei nemnegatívak, csökkenően rendezettek, és a legnagyobb $\sigma_1$. Ezért $$\|Ax\|_2\le \sigma_1\|x\|_2\qquad\text{minden }x\in\mathbb R^n\text{ esetén}.$$ Az $x=v_1$ választással $y=e_1$, így $Av_1=\sigma_1 u_1$, és $\|Av_1\|_2=\sigma_1\|u_1\|_2=\sigma_1$. Tehát az egyenlőség felvétetik, és $$\|A\|_2=\sigma_1=\sigma_{\max}(A).$$

Ez a hasznos normakorlát tehát: $$\|Ax\|_2\le \|A\|_2\|x\|_2.$$ A legélesebb, mert a jobb oldali szinguláris vektorok mentén egyenlőség áll fenn.

3.4.5 Kapcsolat a kondíciószámmal és az alacsony rangú közelítéssel

A 3.3. Vetítés, legkisebb négyzetek és kondicionáltság alfejezetben igértük meg a kondíciószám pontos definícióját. Ha $A\in\mathbb R^{m\times n}$ teljes oszloprangú ($\sigma_n>0$), akkor $$\kappa_2(A)=\frac{\sigma_1}{\sigma_n}=\frac{\|A\|_2}{\sigma_{\min}(A)}.$$ Ranghiányos esetben $\sigma_{\min}=0$, ezért a kondíciószámot $+\infty$ szimbólummal jelöljük. Ebből azonnal látszik a 3.3. Vetítés, legkisebb négyzetek és kondicionáltság alfejezetbeli figyelmeztetés indoka is: $A^{\top}A$ sajátértékei $\sigma_i^2$, tehát $$\kappa_2(A^{\top}A)=\frac{\sigma_1^2}{\sigma_n^2}=\kappa_2(A)^2.$$ A normálegyenlet mátrixa tehát pontosan a négyzetére növelt érzékenységet örökli.

A szinguláris értékek csökkenő sorrendje természetes tömörítést is ad. Rögzítsünk $1\le k\le r$-t, és legyen $$A_k=\sum_{i=1}^{k}\sigma_i u_i v_i^{\top}.$$ Jelölje $A_k$ az $A$ alacsony rangú közelítését. A $\operatorname{rank}(A_k)=k$, mert a $k$ darab diád lineárisan független képtér-irányt feszít.

Tétel (Eckart–Young–Mirsky, megnevezett eredmény, itt nem bizonyított). Tetszőleges $B\in\mathbb R^{m\times n}$, $\operatorname{rank}(B)\le k$ mátrixra $$\|A-B\|_2\ge \sigma_{k+1},$$ és a fenti $A_k$ választással egyenlőség teljesül. A $k=r$ esetben $\sigma_{r+1}=0$ konvencióval $A_r=A$.

A tétel pontos feltételeihez és bizonyításához a [B01] vonatkozó szingulárisérték-felbontás szakaszát kell használni; ez az egység csak a spektrális norma alakú állítását nevezi meg. A kép- és mátrixtömörítésben ugyanez a konstrukció a kiindulópont: a legnagyobb $\sigma_i$-khez tartozó tagok hordozzák a legerősebb lineáris struktúrát.

A PCA-előkép szempontjából ez a következőt jelenti. Legyen $X_c\in\mathbb R^{N\times d}$ egy soronként centrált adatmátrix, azaz minden megfigyelés egy sor. A $\tilde X_c^{\top}\tilde X_c$ szimmetrikus mátrix sajátfelbontásának főtengelyeit a jobb oldali szinguláris vektorok adják, mert $X_c=U\Sigma V^{\top}$. Az első főtengely $v_1$, azaz a legnagyobb szinguláris értékhez tartozó irány a $d$-dimenziós bemeneti térben. Egy centrált $x$-sor kódját $z=V_k^{\top}x^{\top}\in\mathbb R^k$ adja, és ennek az ortogonális vetítés szerinti lineáris előkép/rekonstrukciója: $$\hat x^{\top}=V_k z=V_kV_k^{\top}x^{\top}.$$ A $k$ kódkoordinátából tehát az adatpontnak csak a $V_k$ által feszített altérbe eső részét kapjuk vissza; a komplementer rész az eldobott szinguláris irányokban maradt hiba. A formális variancia- és valószínűségértelmezés az 5.1.–5.2. feladata; itt a „szóródási irány” csak a centrált négyzetes eltérések lineáris algebrai jellemzését jelenti.

3.4.6 Labor: négyzet és kör két lineáris transzformáció alatt

A labor két fix $2\times 2$-es mátrixszal transzformál egy egységnégyzetet és egy egységkörvonalat, majd a véges pontmintán mért maximális nyújtást a szinguláris értékkel hasonlítja össze. Az inputok: $A_1=\operatorname{diag}(2,0.5)$, $A_2=\binom{1.5\ 0.5}{0.5\ 1.0}$. Az alakzatok a $2$D-sík pontjai; a kód float64-ben, CPU-n dolgozik. A példa determinisztikus, ezért seedre nincs szükség; ha a hallgató később zajt ad a ponthalmazhoz, akkor np.random.default_rng(20261020) használandó.

"""n012_shape_stretch.py

A négyzet és kör maximális véges-mintás nyújtása két lineáris
transzformáció alatt, összevetve a spektrális normával.

Munkakönyvtár: lab/n012
Futtatás:      python n012_shape_stretch.py

A kimeneti 'shape_under_transforms.png' a torzított alakzatokat menti.
Az itt közölt konzolszöveg jelölt számított várt kimenet, nem futtatási jegyzőkönyv.
"""

from pathlib import Path

import matplotlib.pyplot as plt
import numpy as np

WORK = Path("lab/n012")
WORK.mkdir(parents=True, exist_ok=True)
DTYPE = np.float64

# Két vizsgált lineáris transzformáció.
A1 = np.array([[2.0, 0.0],
               [0.0, 0.5]], dtype=DTYPE)
A2 = np.array([[1.5, 0.5],
               [0.5, 1.0]], dtype=DTYPE)


def unit_circle(n: int = 512) -> np.ndarray:
    """Az egységkörvonal n darab pontja, shape (n, 2)."""
    theta = np.linspace(0.0, 2.0 * np.pi, n, endpoint=False, dtype=DTYPE)
    return np.column_stack((np.cos(theta), np.sin(theta)))


def unit_square() -> np.ndarray:
    """A zárt egységnégyzet csúcsai; a zárt alakzathoz az első pont ismétlődik."""
    return np.array([[-1.0, -1.0],
                     [ 1.0, -1.0],
                     [ 1.0,  1.0],
                     [-1.0,  1.0],
                     [-1.0, -1.0]], dtype=DTYPE)


def max_finite_stretch(A: np.ndarray, X: np.ndarray) -> float:
    """A véges ponthalmaz pontjaiban mért maximális ||Ax||/||x|| arány."""
    AX = X @ A.T
    return float(np.max(np.linalg.norm(AX, axis=1)
                        / np.linalg.norm(X, axis=1)))


def spectral_norm(A: np.ndarray) -> float:
    """A spektrális norma, azaz a legnagyobb szinguláris érték."""
    return float(np.linalg.svd(A, compute_uv=False)[0])


def main() -> None:
    square = unit_square()
    circle = unit_circle()

    results = []
    for name, A in [("A1", A1), ("A2", A2)]:
        sigma = spectral_norm(A)
        square_stretch = max_finite_stretch(A, square)
        circle_stretch = max_finite_stretch(A, circle)
        print(f"{name}: sigma={sigma:.16f}, "
              f"square_max={square_stretch:.16f}, "
              f"circle_max={circle_stretch:.16f}")
        results.append((A, sigma, square_stretch, circle_stretch))

    # A1: mindkét szinguláris irány szerepel a négyzet csúcsaiban is,
    # ezért a négyzetminta is pontosan eléri a spektrális normát.
    (_, sigma1, square1, circle1) = results[0]
    np.testing.assert_allclose(square1, sigma1, rtol=0.0, atol=1e-12)
    np.testing.assert_allclose(circle1, sigma1, rtol=0.0, atol=1e-12)

    # A2: a négyzetminta általában nem tartalmazza a legnagyobb nyújtás
    # irányát, tehát csak alsó becslés; a sűrű körvonal az irányt közelíti.
    (_, sigma2, square2, circle2) = results[1]
    assert square2 <= sigma2 * (1.0 + 1e-12) + 1e-15
    np.testing.assert_allclose(circle2, sigma2, rtol=5e-4, atol=5e-4)

    fig, axes = plt.subplots(1, 2, figsize=(10, 5))
    for ax, (A, _, _, _) in zip(axes, results):
        ax.plot(square[:, 0], square[:, 1], "--", label="eredeti négyzet")
        ax.plot((square @ A.T)[:, 0], (square @ A.T)[:, 1],
                label="transzformált négyzet")
        ax.plot(circle[:, 0], circle[:, 1], ":", label="eredeti kör")
        ax.plot((circle @ A.T)[:, 0], (circle @ A.T)[:, 1],
                label="transzformált kör", linewidth=2.0)
        ax.set_aspect("equal")
        ax.set_title(f"A = {A.tolist()}")
        ax.legend(loc="upper left")
        ax.grid(True, alpha=0.3)
    fig.tight_layout()
    fig.savefig(WORK / "shape_under_transforms.png", dpi=150)
    print(f"Ábra: {WORK / 'shape_under_transforms.png'}")


if __name__ == "__main__":
    main()

Várt, számított értelmezés a kód determinisztikus előírásából:

• $A_1=\operatorname{diag}(2,0.5)$, tehát $\sigma_1=2$, $\sigma_2=0.5$. A négyzet csúcsai között szerepel $e_1$ iránya, ezért a mért maximális nyújtás pontosan $2.0$.
• $A_2=\binom{1.5\ 0.5}{0.5\ 1.0}$ szimmetrikus, pozitív definit, sajátértékei $(2.5\pm\sqrt{1.25})/2$, így $\sigma_1\approx 1.80901699$. A négyzetminta maximális aránya $2.5/\sqrt 2\approx1.76777$, mert a négyzet csúcsai nem esnek a pontos legmeredekebb irányba. A $512$ pontos körvonalon a legközelebbi pont relatív hibája a $5\times10^{-4}$ tűrésen belül van; ez a véges minta diszkretizációs hibája.

A labor legfontosabb tanulsága: a véges alakzatpontokból mért maximum alsó becslés a spektrális normára. A spektrális norma minden irány felett veszi a szuprémumot; a szögben folytonos kör már jól közelíti ezt, a négyzet viszont nem feltétlenül.

3.4.7 Gyakori tévedés ellenpéldával

A nagy varianciájú irány nem szükségképpen a predikció szempontjából legjobb irány. A PCA az $X$ mátrix szóródását magyarázza, nem azt, hogy egy irány mennyire hasznos egy külső $y$ cél előrejelzésére.

Ellenpélda futtatás nélkül is látható. Legyen a megfigyelések első koordinátája $x_{i1}=10u_i$, a második $x_{i2}=3t_i$, ahol $u_i$ a predikciótól független erős háttérjel. A cél legyen $y_i=x_{i2}$. A centrált $X$ szóródási mátrixát az első koordináta dominálja, mert a faktora $10$ a $3$-mal szemben, tehát az első főtengely lényegében $e_1$. Az $y$-t azonban csak $e_2$ irány mentén tudjuk jól lineárisan magyarázni. A legnagyobb variancia iránya tehát a lehető legrosszabb prediktor, a címke szempontjából hasznos irány pedig kisebb teljes varianciájú. Ez a heurisztika irányválogatásnál fontos: a PCA célfüggetlen dimenziócsökkentés, nem címkeoptimalizáló transzformáció.

3.4.8 Önellenőrzés

1. Miért nem értelmezünk sajátértéket $3\times2$-es mátrixra, szinguláris értéket viszont igen?
2. Ha $A^{\top}A$ legkisebb sajátértéke nulla, mit mondhatunk $\sigma_{\min}$-ről és a legkisebb négyzetes megoldás egyértelműségéről?

Az elsőnél az $Av=\lambda v$ alak-egyezése dönt: $Av\in\mathbb R^3$, $\lambda v\in\mathbb R^2$, ez csak $m=n$ esetben lehet általánosan értelmes. A másodiknál $\sigma_{\min}=0$, a mátrix ranghiányos, így az együttható nem egyértelmű; a predikció ettől még lehet egyértelmű, ahogy 3.3. Vetítés, legkisebb négyzetek és kondicionáltság tárgyalta.

3.4.9 Feladatok

3.4.9.1 F1 fogalmi — sajátérték és szinguláris érték viszonya

Nehézség: 1. Előfeltétel: 3.3. Vetítés, legkisebb négyzetek és kondicionáltság ortogonális mátrix, jelen egység SVD-definíciója. Adja meg, hogy egy $A\in\mathbb R^{m\times n}$ mátrix szinguláris értékei hogyan viszonyulnak az $A^{\top}A$ és az $AA^{\top}$ mátrixok sajátértékeihez. Válaszát egy $2\times2$-es, nem szimmetrikus példán ellenőrizze. Átadandó: a két sajátérték-kapcsolat pontos megfogalmazása, alakokkal, és a példa kiszámolt értékei.

3.4.9.2 F2 levezetési — szubmultiplikativitás és ortogonális invariancia

Nehézség: 2. Előfeltétel: a spektrális norma definíciója. Legyen $A\in\mathbb R^{m\times n}$, $B\in\mathbb R^{n\times p}$. Igazolja, hogy $$\|AB\|_2\le\|A\|_2\|B\|_2.$$ Ezután mutassa meg, hogy bármely kompatibilis méretű ortogonális $Q$ mátrixra $$\|QA\|_2=\|A\|_2=\|AQ\|_2.$$ Átadandó: teljes, indokolt levezetés, az egyenlőség vagy az éles korlát kérdésének jelzése.

3.4.9.3 F3 implementációs — nyújtási arány ellenőrző függvény

Nehézség: 2. Előfeltétel: jelen egység laborja, 2.4. Kis tudományos szoftverprojekt tesztfegyelem. Írjon olyan ratio_and_check(A, X) függvényt, amely minden X sorra kiszámítja a $\|Ax\|_2/\|x\|_2$ arányt, ellenőrzi, hogy az nem haladja meg a $\|A\|_2(1+\tau_{\mathrm{rel}})+\tau_{\mathrm{abs}}$ korlátot, és visszaadja a maximális arányt. Tesztelje a jelen egység $A=\binom{3\ 0}{4\ 0}$ példáján az $e_1$, $e_2$ és $(e_1+e_2)/\sqrt2$ vektorokra, a megadott toleranciákkal. Átadandó: teljes kód, a három arány és az ellenőrzés kimenete.

3.4.9.4 F4 hibakeresési — miért rossz a sajátérték-alapú korlát?

Nehézség: 2. Előfeltétel: a $J$ ellenpélda ebből az egységből. Az alábbi függvény állítólag a maximális nyújtást adja meg:

def wrong_max_stretch(A):
    import numpy as np
    return float(np.max(np.abs(np.linalg.eigvals(A))))

Adjon konkrét mátrixot, amelyre ez hibás eredményt ad. Lokalizálja a hiba okát, mondja meg a következményt, javítsa a függvényt, és ellenőrizze a javítást a konkrét példán. Átadandó: hibás és helyes kimenet, a hiba magyarázata, javított kód és visszaellenőrzés.

3.4.9.5 F5 kísérlettervezési/transzfer — varianciairány kontra prediktív irány

Nehézség: 3. Előfeltétel: 3.3. Vetítés, legkisebb négyzetek és kondicionáltság legkisebb négyzetek, 1.3. Adatfelosztás és a megfigyelési egység adatfelosztás, jelen egység PCA-előképe. Tervezzen olyan kis szimulációs protokollt, amely azt vizsgálja, hogy az első főkomponensre vetített egyetlen prediktor jobb-e, mint egy kézzel kiválasztott, kisebb varianciájú jelirány. Használjon folytonos $y$ célváltozót. Rögzítse a megfigyelési egységet, a generáló sémát, a seedet, a felosztást, a baseline-t, a metrikát és a következtetési korlátot. Átadandó: egy megvalósítható protokoll leírása, amelyen a két prediktor összehasonlítható anélkül, hogy a kimenetét előre „előírnánk”. Előre garantált győztes nem szükséges.

3.4.10 Megoldások és indoklás

3.4.10.1 F1 megoldása

Az SVD-alakból $$A^{\top}A=V\Sigma^{\top}\Sigma V^{\top},\qquad AA^{\top}=U\Sigma\Sigma^{\top}U^{\top}.$$ A $V$ és $U$ ortogonalitása miatt ezek valódi sajátfelbontások. Ezért $A^{\top}A$ pozitív szemidefinit, sajátértékei $\sigma_i^2$, $AA^{\top}$ sajátértékei $\sigma_i^2$; a két mátrix nemnulla sajátértékeinek halmaza megegyezik, a nulla sajátértékek multiplicitása az $m,n$ méretkülönbség szerint változhat.

Példa: $A=\binom{3\ 0}{4\ 0}$. Ekkor $A^{\top}A=\binom{25\ 0}{0\ 0}$, sajátértékei $25,0$, tehát a szinguláris értékek $5,0$. Az $AA^{\top}=\binom{9\ 12}{12\ 16}$, karakterisztikus polinomja $\lambda^2-25\lambda$, sajátértékei szintén $25,0$.

3.4.10.2 F2 megoldása

Legyen $x$ egységvektor. A normakorlátot kétszer alkalmazzuk: $$\|(AB)x\|_2=\|A(Bx)\|_2 \le \|A\|_2\|Bx\|_2 \le \|A\|_2\|B\|_2\|x\|_2 =\|A\|_2\|B\|_2.$$ Mivel ez minden egység $x$-re fennáll, a bal oldali maximumra is igaz: $$\|AB\|_2\le\|A\|_2\|B\|_2.$$

Ortogonális $Q$-ra $\|Qz\|_2=\|z\|_2$ minden $z$-re, ezért $$\|QA\|_2=\max_{\|x\|=1}\|QAx\|_2 =\max_{\|x\|=1}\|Ax\|_2=\|A\|_2.$$ Az $AQ$ esetben $z=Qx$ az egységgömböt önmagára képezi, ezért az $\{AQx:\|x\|=1\}$ halmaz azonos az $\{Az:\|z\|=1\}$ halmazzal, tehát a két maximum egyenlő. Az állítás kompatibilis méretekre érvényes: $QA$ esetén $Q\in\mathbb R^{m'\times m}$ ortogonális, $AQ$ esetén $Q\in\mathbb R^{n\times n}$ ortogonális.

3.4.10.3 F3 megoldása

import numpy as np

def ratio_and_check(A, X, rtol=1e-12, atol=1e-15):
    A = np.asarray(A, dtype=np.float64)
    X = np.asarray(X, dtype=np.float64)
    if X.ndim != 2:
        raise ValueError("X legyen (n, d) alakú.")
    denom = np.linalg.norm(X, axis=1)
    if np.any(denom == 0.0):
        raise ValueError("A nullvektorhoz nincs nyújtási arány.")
    ratios = np.linalg.norm(X @ A.T, axis=1) / denom
    bound = np.linalg.norm(A, 2) * (1.0 + rtol) + atol
    if np.any(ratios > bound):
        raise AssertionError(
            f"Spektrálisnorma-sértés: max={ratios.max():.16f}, bound={bound:.16f}"
        )
    return float(np.max(ratios))

A = np.array([[3.0, 0.0],
              [4.0, 0.0]], dtype=np.float64)
X = np.array([[1.0, 0.0],
              [0.0, 1.0],
              [1.0, 1.0]]) / np.sqrt(2.0) * np.sqrt(2.0)
X = np.array([[1.0, 0.0],
              [0.0, 1.0],
              [1.0/np.sqrt(2.0), 1.0/np.sqrt(2.0)]], dtype=np.float64)

print(ratio_and_check(A, X))
# A három arány: 5.0, 0.0, 5/sqrt(2) ~= 3.5355339059327378;
# a függvény ezek maximumát, 5.0-t adja vissza, ami pontosan sigma_1.

A függvény a $\binom{3}{4}$ képet adó $e_1$ irányban éri el a $5$-ös felső korlátot; az $e_2$ a magtérbe esik, aránya $0$; a diagonális irány aránya $5/\sqrt2$. A toleranciák a lebegőpontos kerekítést fedik le, nem lazítják a matematikai korlátot.

3.4.10.4 F4 megoldása

A hibás függvény a nem szimmetrikus $J=\binom{0\ 1}{0\ 0}$ mátrixra a sajátértékeket vizsgálja. A két sajátérték $0$, így wrong_max_stretch(J) a $0.0$ értéket adná. A valódi spektrális norma $\sigma_1=1$, mert $Je_2=e_1$ egységvektor. A hiba oka: a maximális nyújtás általában a $|\lambda_{\max}|$-nál nagyobb lehet, mert a sajátvektorok nem feltétlenül fedik a teljes teret ortonormáltan. Következmény: a modell érzékenységi korlátját alulbecsülhetjük, ami például gradienselemzésben hibás normalizálást ad.

Javítás:

def correct_max_stretch(A):
    import numpy as np
    return float(np.linalg.svd(A, compute_uv=False)[0])

Visszaellenőrzés: correct_max_stretch(J) eredménye $1.0$, a np.linalg.svd(J, compute_uv=False) várt szinguláris értékei $[1,0]$.

3.4.10.5 F5 megoldásminta

Egy lehetséges protokoll:

• Kérdés: a centrált adatmátrix első főkomponensére vetített egyváltozós prediktor jobb-e, mint a generátor által ismert jelirány?
• Megfigyelési egység: egy szimulált rekord; a rekord két bemeneti koordinátát és egy folytonos célt tartalmaz.
• Generáló séma: seed 20261020; $N=2000$; $t_i\sim \mathrm{Uniform}(-1,1)$, $u_i\sim \mathrm{Uniform}(-1,1)$ független, $\eta_i\sim N(0,0.1^2)$; $x_{i1}=10u_i$, $x_{i2}=3t_i$, $y_i=3t_i+\eta_i$.
• Split: $60\%$ train, $20\%$ valid, $20\%$ test, azonos seeddel; folytonos cél esetén egyszerű véletlen részekre bontás elég, mert nincs osztálycsoport, de a véletlen sorrendet rögzíteni kell.
• PCA: csak a train centrálási átlagát és főtengelyét szabad kiszámítani, ezeket kell alkalmazni valid/test adatra.
• Prediktorok: $p_{\mathrm{PCA},i}=x_i^{\top}v_1$ az első főtengely menti kód; $p_{\mathrm{jel},i}=x_{i2}$ az ismert jelirány.
• Baseline: intercept-only átlagprediktor, amely mindig a train célátlagát adja.
• Metrika: teszt-MSE és teszt-$R^2$ a least squares illesztés után; a baseline $R^2=0$ szintjéhez viszonyítsunk.
• Következtetési határ: a generátor szerint $v_1\approx e_1$ várható, a $p_{\mathrm{PCA}}$ lényegében zaj, tehát a gyenge PCA-eredmény a konstrukció következménye, nem általános tétel minden adatra. Egy seed és egy séma nem globális PCA-bizonyíték; a protokoll ezt a konkrét „nagy variancia, de címke-irreleváns” jelenetet ellenőrzi.

3.4.11 Rövid összefoglaló

A szinguláris érték felbontás minden valós téglalapmátrixra ortonormált $U,V$ mátrixokkal adja az $A=U\Sigma V^{\top}$ alakot. A pozitív $\sigma_i$ értékek száma a rang, a legnagyobb $\sigma_1$ a spektrális norma. A diagonális operátorra közvetlenül beláttuk, hogy maximális nyújtása a legnagyobb $|d_i|$, majd a teljes SVD-tétel megnevezett létezési és ortonormáltsági állításából levezettük, hogy tetszőleges $A$-ra $\|A\|_2=\sigma_{\max}$. Ebből következik a $\|Ax\|_2\le\sigma_1\|x\|_2$ normakorlát és a 3.3. Vetítés, legkisebb négyzetek és kondicionáltság alfejezetben megelőlegezett $\kappa_2(A)=\sigma_1/\sigma_{\min}$ definíció. Az alacsony rangú $A_k$ közelítés a legnagyobb szinguláris irányokat tartja meg, ez a PCA-előkép lineáris rekonstrukciójának alapja.

3.4.12 Következő alkalmazás

A 4.1. Függvény, határérték és derivált a függvény-határértéket és a deriváltat vezeti be; ott a lineáris közelítés érzékenységét, majd a 4.2.–4.3. a gradienst és a vektor–Jacobi-szorzatot tárgyalja.

3.4.13 Források

• [B01] Deisenroth, Faisal és Ong (2020). Mathematics for Machine Learning. Cambridge University Press. https://mml-book.github.io/.
• [B02] Goodfellow, Bengio és Courville (2016). Deep Learning. MIT Press. https://www.deeplearningbook.org/.