LA-09 — SVD & matrix decompositions

Why this matters for ML

La SVD es probablemente la factorización más importante en toda la ciencia de datos: funciona para cualquier matriz (no solo cuadradas o simétricas), y es el motor de PCA, compresión de imágenes, sistemas de recomendación (matrix factorization), low-rank approximation y la pseudo-inversa para least squares mal condicionados. Si dominas SVD, dominas media caja de herramientas del ML clásico.

Concepts covered

• Singular Value Decomposition $A=U\Sigma V^\top$
• Singular values vs. eigenvalues
• Interpretación geométrica (rotar–escalar–rotar)
• Low-rank approximation (teorema de Eckart–Young)
• Relación SVD ↔ eigendecomposition de $A^\top A$
• Panorama de otras factorizaciones: LU, QR, Cholesky

Intuition first

🎬 Busca "3Blue1Brown / Visual SVD" o Steve Brunton "SVD" (serie excelente y corta). Idea: toda transformación lineal = rotación, luego escalado por ejes, luego otra rotación.

Theory & key results

SVD: cualquier $A\in\mathbb{R}^{m\times n}$ se factoriza como $$A = U,\Sigma,V^\top,$$ donde $U$ ($m\times m$) y $V$ ($n\times n$) son ortogonales, y $\Sigma$ ($m\times n$) es diagonal con entradas $\sigma_1\ge\sigma_2\ge\dots\ge0$, los singular values.

• Columnas de $V$ = right singular vectors (direcciones de entrada).
• Columnas de $U$ = left singular vectors (direcciones de salida).
• $\sigma_i$ = cuánto se estira cada dirección.

Geometría: $A\mathbf{x}$ = rota con $V^\top$ → escala ejes con $\Sigma$ → rota con $U$. Una esfera unitaria se vuelve un elipsoide con semiejes $\sigma_i$.

Relación con eigen: los $\sigma_i^2$ son los eigenvalues de $A^\top A$ (que es simétrica PSD, LA-08), y $V$ son sus eigenvectors; $U$ son los eigenvectors de $AA^\top$. Por eso SVD "hereda" la limpieza del spectral theorem para matrices no simétricas.

Rank y estructura: el número de $\sigma_i>0$ = rank de $A$. Singular values chiquitos = direcciones de poca "energía" (a menudo ruido).

Low-rank approximation (Eckart–Young): la mejor aproximación de rank $k$ a $A$ (en norma de Frobenius/espectral) es quedarte con los $k$ mayores singular values: $$A_k = \sum_{i=1}^{k}\sigma_i,\mathbf{u}_i\mathbf{v}_i^\top.$$ Esto es compresión: guardas $k$ tripletes en vez de toda la matriz. Base de compresión de imágenes y de la reducción de dimensión.

Otras factorizaciones (panorama):

• LU ($A=LU$): eliminación gaussiana empaquetada; para resolver sistemas rápido.
• QR ($A=QR$, LA-06): least squares estable.
• Cholesky ($A=LL^\top$, para PD): la más eficiente; aparece en gaussianas y optimización.

Worked example

Idea numérica: para $A=\begin{bmatrix}3&0\0&-2\end{bmatrix}$, $A^\top A=\begin{bmatrix}9&0\0&4\end{bmatrix}$ → eigenvalues $9,4$ → singular values $\sigma=3,2$. $\Sigma=\text{diag}(3,2)$; $U,V$ son rotaciones/reflexiones que acomodan los signos. La esfera unidad se mapea a un elipsoide con semiejes 3 y 2.

Compresión intuitiva: una imagen $512\times512$ (262k números) reconstruida con $k=50$ usa $50\cdot(512+512+1)\approx 51$k números — ~5× menos, casi sin pérdida visible.

Notebook exercises (by hand)

1. Para $A=\begin{bmatrix}2&0\0&3\end{bmatrix}$, halla singular values (ya es diagonal — cuidado con signos/orden).
2. Muestra que los singular values de $A$ son las raíces de los eigenvalues de $A^\top A$.
3. Si $A$ es simétrica PD, ¿cómo se relacionan sus singular values con sus eigenvalues?
4. Explica por qué descartar los $\sigma_i$ pequeños "elimina ruido" y reduce dimensión.
5. ¿Cuántos números guarda una aproximación rank-$k$ de una matriz $m\times n$? Compara con $mn$.
6. Relaciona SVD con PCA en una frase (adelanto de LA-10).

Python lab

import numpy as np

A = np.array([[3.,1.,1.],[-1.,3.,1.]])
U, s, Vt = np.linalg.svd(A, full_matrices=False)
print("singular values:", s)
# reconstrucción exacta
print("reconstruye A:", np.allclose(U @ np.diag(s) @ Vt, A))

# singular values^2 == eigenvalues de AᵀA
print(np.allclose(np.sort(s**2)[::-1],
                  np.sort(np.linalg.eigvalsh(A.T @ A))[::-1]))

# low-rank approximation
def low_rank(A, k):
    U, s, Vt = np.linalg.svd(A, full_matrices=False)
    return U[:, :k] @ np.diag(s[:k]) @ Vt[:k, :]

B = np.random.randn(30, 20)
for k in [1, 5, 10, 20]:
    err = np.linalg.norm(B - low_rank(B, k)) / np.linalg.norm(B)
    print(f"k={k:2d}  error relativo={err:.3f}")

Reto: carga una imagen en escala de grises como matriz y compárala reconstruida con $k=5,20,50$.

Examen final 📝

Intenta cada nivel antes de abrir las soluciones.

🟡 Medio

1. Para $A=\begin{bmatrix}2&0\0&-3\end{bmatrix}$: da sus singular values (¡ojo con el signo!).
2. ¿Cuántos números guarda una aproximación rank-$k$ de una matriz $100\times80$? Compara con guardar la matriz completa para $k=10$.

🟠 Medio-difícil

3. Muestra que los singular values de $A$ son las raíces cuadradas de los eigenvalues de $A^\top A$, y que $V$ (right singular vectors) son los eigenvectors de $A^\top A$.
4. Si $A$ es simétrica positive definite, explica por qué su SVD y su eigendecomposition coinciden.

🔴 Difícil

5. Deriva la pseudo-inversa $A^+=V\Sigma^+U^\top$ desde la SVD y explica cómo resuelve least squares $\min|A\mathbf x-\mathbf b|^2$ incluso cuando $A^\top A$ es singular (rango deficiente).
6. Un sistema de recomendación tiene una matriz usuarios×ítems muy incompleta. Explica, usando la idea de low-rank approximation (Eckart–Young), por qué asumir "rank bajo" permite predecir ratings faltantes, y qué significa cada singular value grande en ese contexto.