Matematikai Algoritmusok és Felfedezések I.

8. Előadás: Numpy

2021 március 29.

Tudományos csomagok (Python Scientific stack)

csomag
NumPy Hatékony N-dimenziós tömb
SciPy Numerikus számítások
Matplotlib Grafikonok és rajzok
IPython (Jupyter) Interaktív notebook
SymPy Szimbolikus számítások
Pandas Adatbányászat

Numpy

Vektorizáció

Ciklusok helyett automatikus elemenkénti műveletvégzés és optimalizálás a háttérben.

Copy

A slicing is view-t hoz létre. Viszont a tömbökkel indexelés nem!

Copy

Teljes másolat jön létre.

Sokszor megéri egy slicera copyt hívni, ha tömb többi részére később már nem lesz szükségünk. Így memóriát szabadíthatunk fel.

Ha csak b = a[:100] szerepelne, akkor a del a parancs kiadása után sem szabadulna fel a memória, hiszen b még hivatkozik rá.

np.random

Numpynak van egy gazdag random számmokkal operáló alcsomagja.

A numpy.random.rand például float64 számokat randomol a $[0, 1)$ intervallumról egyenletesen.

Más eloszlások:

Diszkrét eloszlások:

choice a valszóínűségeket is megadhatjuk:

A permutation az első dimenzió szerint permutál.

Lineáris algebra

linalg csomag: https://numpy.org/doc/stable/reference/routines.linalg.html

A mátrix szorzásra három jelölés is létezik:

Tudunk invertálni, de mint mindig, figyelni kell a kerkítési hibákra.

Kép tömörítés szingulásris érték felbontással (SVD decomposition)

Képek közelítése alacsony rangú mátrixokkal

Legyen $A\in\mathbb{R}^{n\times m}$ egy tetszőleges mátrix. Ekkor léteznek $U\in\mathbb{R}^{n\times n}$, $D\in\mathbb{R}^{n\times m}$ és $V\in\mathbb{R}^{m\times m}$ mátrxiok, melyekre

$$ A = UDV^*, $$

ahol $U$ és $V$ unitér mátrixok, tehát $U^*U = UU^* = I_n$ és $V^*V=VV^*=I_m$. $D$ pedig diakonális mátrix, azaz $d_{ij}=0$ ha $i\ne j$. A csillag operátor konjugált transzponáltja, tehát $(V^*)_{ij} = \overline V_{ji}$, de mivel mi valós mátrixokkal dolgozunk, elegendő transzponálásra gondolni. $D$ diagonális elemei nemnegatívak és csökkenő sorrenben jönnek: $d_{ii} = \sigma_i$, $\sigma_1\geq\sigma_2\geq\ldots\geq\sigma_r > \sigma_{r+1} = \ldots = \sigma_{\min(n,m)} = 0$, ahol $r$ az $A$ mátrix rangja. Ezeket a $\sigma$ értékeket az $A$ mátrix szinguláris értékeinek hívjuk.

Alacsony rangú aproximáció

Legyen $k\in\mathbb{N}$ egy természetes szám, ahol $k\leq\text{rank}(A)\leq\min\{n, m\}$. Egy olyan $A_k$ mátrixok keresünk, melyre $\text{rank}(A_k) = k$ és amelyik az $A$ mátrix legjobb közelítése a $k$ rangú mátrixok között. Tehát a következő minimalizálási feladatot szeretnénk megoldani:

$$ \left|\left| A - B \right|\right|_F \to \min !\qquad \mbox{ ahol }\quad B\in\mathbb{R}^{n\times m}, \ \text{rank}(B) = k. $$

Itt $\left|\left| X \right|\right|_F$ a Frobenius normát jelöli, ami az $X$ eleminek négyzetösszegének a gyöke.

A feladat megoldását mekapjuk az SVD-felbontás segítségével. Ha $A = UDV^*$, akkor megtartjuk $D$ átlójának első $k$ elemét és a többi szinguláris értéket pedig 0-ra állítjuk. Legyen $D_k$ az így kapott diagonális mátrix. Ezután újra kiszámítjuk a $UD_kV^*$ szorzatot. A nullára állított értékek miatt elég $U$ első k oszlopát és $V$ első $k$ sorát megtartani.

Összefoglalva, az $A_k := U_kD_kV_k^*$ mátrix van legközelebb az $A$ mátrixhoz a Frobenius norma szerint a $k$ rangú mátrixok között, ahol $U_k$ és $V_k$ az első $k$ oszlopla és sora $U$-nak és $V$-nek.

Képek közelítése

A képeket a korábban látott módon egy $n\times m\times 3$-as tömbben tároljuk.

A fenti közelítést mindhárom színre elvégezzük.

Semmi sem garantálja, hogy a közelítő mátrix értékei értelmezhetők képként.