Phase 01 - Lesson 11

Decomposição em Valores Singulares

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

A SVD é o canivete suico dá álgebra linear. Toda matriz tem uma. Todo cientista de dados precisa de uma.

Tipo: Build Linguagens: Python, Julia Pré-requisitos: Fase 1, Lições 01 (Intuição de Álgebra Linear), 02 (Operações de Vetores e Matrizes), 03 (Transformacoes de Matrizes) Tempo: ~120 minutos

Objetivos de Aprendizagem

• Implementar SVD via iteração de potência e explicar o significado geométrico de U, Sigma e V^T
• Aplicar SVD truncada para compressão de imagens e medir a razão de compressão vs erro de reconstrução
• Calcular a pseudoinversa de Moore-Penrose via SVD para resolver sistemas de mínimos quadrados sobredeterminados
• Conectar a SVD ao PCA, sistemas de recomendacao (fatores latentes) e Analise Semântica Latente em NLP

O Problema

Você tem uma matriz 1000x2000. Talvez sejam avaliações de usuário-filme. Talvez seja uma tabela de frequência documento-termo. Talvez sejam os valores de pixels de uma imagem. Você precisa comprimi-la, remover ruido dela, encontrar estrutura oculta nela ou resolver um sistema de mínimos quadrados com ela. A autodecomposição só funciona em matrizes quadradas. Mesmo assim, ela requer que a matriz tenha um conjunto completo de autovetores linearmente independentes.

A SVD funciona em qualquer matriz. Qualquer formato. Qualquer posto. Sem condições. Ela decompõe a matriz em três fatores que revelam a geometria do que a matriz faz com o espaço. É a fatoração mais geral e mais útil de toda a álgebra linear.

O Conceito

O que a SVD faz geometricamente

Toda matriz, independente do formato, realiza três operações em sequência: rotacionar, escalar, rotacionar. A SVD torna essa decomposição explicita.

A = U * Sigma * V^T

      m x n     m x m    m x n    n x n
     (any)    (rotate)  (scale)  (rotate)

Dada qualquer matriz A, a SVD a fatora em:

• V^T rotaciona vetores no espaço de entrada (n-dimensional)
• Sigma escala ao longo de cada eixo (estica ou comprime)
• U rotaciona o resultado para o espaço de saída (m-dimensional)

graph LR
    A["Input space (n-dim)\nData cloud\n(arbitrary orientation)"] -->|"V^T\n(rotate)"| B["Scaled space\nAligned with axes\nthen scaled by Sigma"]
    B -->|"U\n(rotate)"| C["Output space (m-dim)\nRotated to output\norientation"]

Pense assim. Você entrega uma matriz para a SVD. Ela te diz: "Está matriz pega uma esfera de entradas, primeiro a rotaciona por V^T, depois a estica em um elipsoide por Sigma, depois rotaciona o elipsoide por U." Os valores singulares são os comprimentos dos eixos do elipsoide.

A decomposição completa

Para uma matriz A com formato m x n:

A = U * Sigma * V^T

where:
  U     is m x m, orthogonal (U^T U = I)
  Sigma is m x n, diagonal (singular values on the diagonal)
  V     is n x n, orthogonal (V^T V = I)

The singular values sigma_1 >= sigma_2 >= ... >= sigma_r > 0
where r = rank(A)

As colunas de U são chamadas de vetores singulares a esquerda. As colunas de V são chamadas de vetores singulares a direita. As entradas diagonais de Sigma são chamadas de valores singulares. Elas são sempre não-negativas e convencionalmente ordenadas em ordem decrescente.

Vetores singulares a esquerda, valores singulares, vetores singulares a direita

Cada componente dá SVD tem um significado geométrico distinto.

Vetores singulares a direita (colunas de V): Eles formam uma base ortonormal para o espaço de entrada (R^n). São as direções no espaço de entrada que a matriz mapeia para direções ortogonais no espaço de saída. Pense neles como o sistema de coordenadas natural para o dominio.

Valores singulares (diagonal de Sigma): Esses são os fatores de escala. O i-esimo valor singular te diz o quanto a matriz estica vetores ao longo do i-esimo vetor singular a direita. Um valor singular de zero significa que a matriz esmaga aquela direção completamente.

Vetores singulares a esquerda (colunas de U): Eles formam uma base ortonormal para o espaço de saída (R^m). O i-esimo vetor singular a esquerda é a direção no espaço de saída onde o i-esimo vetor singular a direita pousa (após o escalonamento).

A relação entre eles:

A * v_i = sigma_i * u_i

The matrix A takes the i-th right singular vector v_i,
scales it by sigma_i, and maps it to the i-th left singular vector u_i.

Isso te dá uma imagem coordenada por coordenada do que qualquer matriz faz.

Forma de produto externo

A SVD pode ser escrita como uma soma de matrizes de posto 1:

A = sigma_1 * u_1 * v_1^T + sigma_2 * u_2 * v_2^T + ... + sigma_r * u_r * v_r^T

Each term sigma_i * u_i * v_i^T is a rank-1 matrix (an outer product).
The full matrix is the sum of r such matrices, where r is the rank.

Essa forma é o fundamento dá aproximação de baixo posto. Cada termo adiciona uma camada de estrutura. O primeiro termo captura o padrão mais importante. O segundo captura o próximo mais importante.É assim por diante. Truncar essa soma te dá a melhor aproximação possível em qualquer posto dado.

Rank-1 approx:    A_1 = sigma_1 * u_1 * v_1^T
                  (captures the dominant pattern)

Rank-2 approx:    A_2 = sigma_1 * u_1 * v_1^T + sigma_2 * u_2 * v_2^T
                  (captures the two most important patterns)

Rank-k approx:    A_k = sum of top k terms
                  (optimal by the Eckart-Young theorem)

Relação com a autodecomposição

A SVD e a autodecomposição estão profundamente conectadas. Os valores e vetores singulares de A vêm diretamente dos autovalores e autovetores de A^T A e A A^T.

A^T A = V * Sigma^T * U^T * U * Sigma * V^T
      = V * Sigma^T * Sigma * V^T
      = V * D * V^T

where D = Sigma^T * Sigma is a diagonal matrix with sigma_i^2 on the diagonal.

So:
- The right singular vectors (V) are eigenvectors of A^T A
- The singular values squared (sigma_i^2) are eigenvalues of A^T A

Similarly:
A A^T = U * Sigma * V^T * V * Sigma^T * U^T
      = U * Sigma * Sigma^T * U^T

So:
- The left singular vectors (U) are eigenvectors of A A^T
- The eigenvalues of A A^T are also sigma_i^2

Essa conexao te diz três coisas:

1. Os valores singulares são sempre reais e não-negativos (eles são raízes quadradas de autovalores de uma matriz positiva semi-definida).
2. Você poderia calcular a SVD via autodecomposição de A^T A, mas isso eleva ao quadrado o número de condição e perde precisão numérica. Algoritmos de SVD dedicados evitam isso.
3. Quando A e quadrada é simétrica positiva semi-definida, a SVD é a autodecomposição são a mesma coisa.

SVD truncada: aproximação de baixo posto

O teorema de Eckart-Young-Mirsky afirma que a melhor aproximação de posto k para A (tanto na norma de Frobenius quanto na espectral) é obtida mantendo apenas os k maiores valores singulares e seus vetores correspondentes:

A_k = U_k * Sigma_k * V_k^T

where:
  U_k     is m x k  (first k columns of U)
  Sigma_k is k x k  (top-left k x k block of Sigma)
  V_k     is n x k  (first k columns of V)

Approximation error = sigma_{k+1}  (in spectral norm)
                    = sqrt(sigma_{k+1}^2 + ... + sigma_r^2)  (in Frobenius norm)

Está não é apenas "uma boa" aproximação. E comprovadamente a melhor aproximação possível de posto k. Nenhuma outra matriz de posto k está mais próxima de A.

Mantenha os top 3: A_3 captura os três maiores valores singulares. Erro = valores restantes (sigma_4 até sigma_8).

Se os valores singulares decaem rápido, um k pequeno captura a maior parte dá matriz. Se eles decaem devagar, a matriz não têm estrutura de baixo posto.

Compressão de imagens com SVD

Uma imagem em escala de cinza é uma matriz de intensidades de pixels. Uma imagem 800x600 tem 480.000 valores. A SVD permite aproximá-la com muito menos.

Original image: 800 x 600 = 480,000 values

SVD with rank k:
  U_k:      800 x k values
  Sigma_k:  k values
  V_k:      600 x k values
  Total:    k * (800 + 600 + 1) = k * 1401 values

  k=10:   14,010 values   (2.9% of original)
  k=50:   70,050 values  (14.6% of original)
  k=100: 140,100 values  (29.2% of original)

  The compression ratio improves as k gets smaller,
  but visual quality degrades.

O insight chave: imagens naturais tem valores singulares que decaem rapidamente. Os primeiros valores singulares capturam a estrutura ampla (formas, gradientes). Os posteriores capturam detalhes finos e ruido. Truncar no posto 50 frequentemente produz uma imagem que parece quase idêntica a original enquanto usa 85% menos armazenamento.

SVD para sistemas de recomendacao

O Premio Netflix tornou isso famoso. Você tem uma matriz de avaliações usuário-filme onde a maioria das entradas está faltando.

             Movie1  Movie2  Movie3  Movie4  Movie5
  User1      [  5      ?       3       ?       1  ]
  User2      [  ?      4       ?       2       ?  ]
  User3      [  3      ?       5       ?       ?  ]
  User4      [  ?      ?       ?       4       3  ]

  ? = unknown rating

A ideia: essa matriz de avaliações tem baixo posto. Os usuários não têm gostos completamente independentes. Existe um punhado de fatores latentes (acao vs drama, antigo vs novo, cerebral vs visceral) que explicam a maioria das preferências.

A SVD na matriz de avaliações (preenchida) a decompõe em:

• U: perfis de usuário no espaço de fatores latentes
• Sigma: importancia de cada fator latente
• V^T: perfis de filme no espaço de fatores latentes

A avaliação prevista de um usuário para um filme é o produto escalar entre o perfil do usuário é o perfil do filme (ponderado pelos valores singulares). A aproximação de baixo posto preenche as entradas faltantes.

Na prática, você usa variantes como a SVD incremental de Simon Funk ou ALS (alternating least squares) que lidam diretamente com dados faltantes. Mas a ideia central é a mesma: decomposição em fatores latentes via SVD.

SVD em NLP: Analise Semântica Latente

A Analise Semântica Latente (LSA), também chamada de Indexacao Semântica Latente (LSI), aplica SVD a uma matriz termo-documento.

             Doc1   Doc2   Doc3   Doc4
  "cat"      [  3      0      1      0  ]
  "dog"      [  2      0      0      1  ]
  "fish"     [  0      4      1      0  ]
  "pet"      [  1      1      1      1  ]
  "ocean"    [  0      3      0      0  ]

After SVD with rank k=2:

  Each document becomes a point in 2D "concept space."
  Each term becomes a point in the same 2D space.
  Documents about similar topics cluster together.
  Terms with similar meanings cluster together.

  "cat" and "dog" end up near each other (land pets).
  "fish" and "ocean" end up near each other (water concepts).
  Doc1 and Doc3 cluster if they share similar topics.

A LSA foi um dos primeiros métodos bem-sucedidos para capturar similaridade semântica a partir de texto bruto. Ela funciona porque termos sinonimos tendem a aparecer em documentos similares, então a SVD os agrupa nas mesmas dimensões latentes. Os word embeddings modernos (Word2Vec, GloVe) podem ser vistos como descendentes dessa ideia.

SVD para redução de ruido

Dados ruidosos tem sinal concentrado nos valores singulares principais e ruido espalhado por todos os valores singulares. Truncar remove o piso de ruido.

Valores singulares de sinal limpo:

Valores singulares de sinal ruidoso (o ruido se adiciona a todos):

graph TD
    A["All singular values"] --> B{"Clear gap?"}
    B -->|"Above gap"| C["Signal: keep these (top k)"]
    B -->|"Below gap"| D["Noise: discard these"]
    C --> E["Reconstruct with A_k to get denoised version"]

Isso é usado em processamento de sinais, medicao cientifica e limpeza de dados. Toda vez que você tem uma matriz corrompida por ruido aditivo, a SVD truncada é uma forma fundamentada de separar sinal de ruido.

Pseudoinversa via SVD

A pseudoinversa de Moore-Penrose A+ generaliza a inversao de matrizes para matrizes não-quadradas e singulares. A SVD torna trivial o seu cálculo.

If A = U * Sigma * V^T, then:

A+ = V * Sigma+ * U^T

where Sigma+ is formed by:
  1. Transpose Sigma (swap rows and columns)
  2. Replace each non-zero diagonal entry sigma_i with 1/sigma_i
  3. Leave zeros as zeros

For A (m x n):      A+ is (n x m)
For Sigma (m x n):  Sigma+ is (n x m)

A pseudoinversa resolve problemas de mínimos quadrados. Se Ax = b não têm solucao exata (sistema sobredeterminado), então x = A+ b é a solucao de mínimos quadrados (minimiza ||Ax - b||).

Overdetermined system (more equations than unknowns):

  [1  1]         [3]
  [2  1] x   =   [5]       No exact solution exists.
  [3  1]         [6]

  x_ls = A+ b = V * Sigma+ * U^T * b

  This gives the x that minimizes the sum of squared residuals.
  Same result as the normal equations (A^T A)^(-1) A^T b,
  but numerically more stable.

Vantagens de estabilidade numérica

Calcular a autodecomposição de A^T A eleva ao quadrado os valores singulares (os autovalores de A^T A são sigma_i^2). Isso eleva ao quadrado o número de condição, amplificando erros numéricos.

Example:
  A has singular values [1000, 1, 0.001]
  Condition number of A: 1000 / 0.001 = 10^6

  A^T A has eigenvalues [10^6, 1, 10^{-6}]
  Condition number of A^T A: 10^6 / 10^{-6} = 10^{12}

  Computing SVD directly: works with condition number 10^6
  Computing via A^T A:     works with condition number 10^{12}
                           (6 extra digits of precision lost)

Algoritmos modernos de SVD (bidiagonalizacao de Golub-Kahan) trabalham diretamente em A, nunca formando A^T A.É por isso que você deve sempre preferir np.linalg.svd(A) em vez de np.linalg.eig(A.T @ A).

Conexao com o PCA

PCA E SVD em dados centralizados. Isso não é uma analogia. E literalmente o mesmo cálculo.

Given data matrix X (n_samples x n_features), centered (mean subtracted):

Covariance matrix: C = (1/(n-1)) * X^T X

PCA finds eigenvectors of C. But:

  X = U * Sigma * V^T    (SVD of X)

  X^T X = V * Sigma^2 * V^T

  C = (1/(n-1)) * V * Sigma^2 * V^T

So the principal components are exactly the right singular vectors V.
The explained variance for each component is sigma_i^2 / (n-1).

In sklearn, PCA is implemented using SVD, not eigendecomposition.
It is faster and more numerically stable.

Isso significa que tudo o que você aprendeu sobre redução de dimensionalidade na Lição 10 e SVD por baixo dos panos. O PCA é a aplicacao mais comum dá SVD em machine learning.

Construa

Passo 1: SVD do zero usando iteração de potência

A ideia: para encontrar o maior valor singular e seus vetores, use iteração de potência em A^T A (ou A A^T). Depois deflacione a matriz e repita para o próximo valor singular.

import numpy as np

def power_iteration(M, num_iters=100):
    n = M.shape[1]
    v = np.random.randn(n)
    v = v / np.linalg.norm(v)

    for _ in range(num_iters):
        Mv = M @ v
        v = Mv / np.linalg.norm(Mv)

    eigenvalue = v @ M @ v
    return eigenvalue, v

def svd_from_scratch(A, k=None):
    m, n = A.shape
    if k is None:
        k = min(m, n)

    sigmas = []
    us = []
    vs = []

    A_residual = A.copy().astype(float)

    for _ in range(k):
        AtA = A_residual.T @ A_residual
        eigenvalue, v = power_iteration(AtA, num_iters=200)

        if eigenvalue < 1e-10:
            break

        sigma = np.sqrt(eigenvalue)
        u = A_residual @ v / sigma

        sigmas.append(sigma)
        us.append(u)
        vs.append(v)

        A_residual = A_residual - sigma * np.outer(u, v)

    U = np.column_stack(us) if us else np.empty((m, 0))
    S = np.array(sigmas)
    V = np.column_stack(vs) if vs else np.empty((n, 0))

    return U, S, V

Passo 2: Teste e compare com o NumPy

np.random.seed(42)
A = np.random.randn(5, 4)

U_ours, S_ours, V_ours = svd_from_scratch(A)
U_np, S_np, Vt_np = np.linalg.svd(A, full_matrices=False)

print("Our singular values:", np.round(S_ours, 4))
print("NumPy singular values:", np.round(S_np, 4))

A_reconstructed = U_ours @ np.diag(S_ours) @ V_ours.T
print(f"Reconstruction error: {np.linalg.norm(A - A_reconstructed):.8f}")

Passo 3: Demo de compressão de imagem

def compress_image_svd(image_matrix, k):
    U, S, Vt = np.linalg.svd(image_matrix, full_matrices=False)
    compressed = U[:, :k] @ np.diag(S[:k]) @ Vt[:k, :]
    return compressed

image = np.random.seed(42)
rows, cols = 200, 300
image = np.random.randn(rows, cols)

for k in [1, 5, 10, 20, 50]:
    compressed = compress_image_svd(image, k)
    error = np.linalg.norm(image - compressed) / np.linalg.norm(image)
    original_size = rows * cols
    compressed_size = k * (rows + cols + 1)
    ratio = compressed_size / original_size
    print(f"k={k:>3d}  error={error:.4f}  storage={ratio:.1%}")

Passo 4: Redução de ruido

np.random.seed(42)
clean = np.outer(np.sin(np.linspace(0, 4*np.pi, 100)),
                 np.cos(np.linspace(0, 2*np.pi, 80)))
noise = 0.3 * np.random.randn(100, 80)
noisy = clean + noise

U, S, Vt = np.linalg.svd(noisy, full_matrices=False)
denoised = U[:, :5] @ np.diag(S[:5]) @ Vt[:5, :]

print(f"Noisy error:    {np.linalg.norm(noisy - clean):.4f}")
print(f"Denoised error: {np.linalg.norm(denoised - clean):.4f}")
print(f"Improvement:    {(1 - np.linalg.norm(denoised - clean) / np.linalg.norm(noisy - clean)):.1%}")

Passo 5: Pseudoinversa

A = np.array([[1, 1], [2, 1], [3, 1]], dtype=float)
b = np.array([3, 5, 6], dtype=float)

U, S, Vt = np.linalg.svd(A, full_matrices=False)
S_inv = np.diag(1.0 / S)
A_pinv = Vt.T @ S_inv @ U.T

x_svd = A_pinv @ b
x_lstsq = np.linalg.lstsq(A, b, rcond=None)[0]
x_pinv = np.linalg.pinv(A) @ b

print(f"SVD pseudoinverse solution:  {x_svd}")
print(f"np.linalg.lstsq solution:   {x_lstsq}")
print(f"np.linalg.pinv solution:    {x_pinv}")

Use

Demos completas e funcionais estão em code/svd.py. Execute-o para ver a SVD aplicada a compressão de imagens, sistemas de recomendacao, analise semântica latente e redução de ruido.

python svd.py

A versao em Julia em code/svd.jl demonstra os mesmos conceitos usando a função nativa svd() de Julia é o pacote LinearAlgebra.

julia svd.jl

Entregue

Está lição produz:

• outputs/skill-svd.md - uma skill para saber quando e como aplicar SVD em projetos reais

Exercícios

1. Implemente a SVD completa do zero sem usar iteração de potência. Em vez disso, calcule a autodecomposição de A^T A para obter V e os valores singulares, depois calcule U = A V Sigma^{-1}. Compare a precisão numérica com a sua versao de iteração de potência e com o NumPy.

2. Carregue uma imagem real em escala de cinza (ou converta uma para escala de cinza). Comprima-a nos postos 1, 5, 10, 25, 50, 100. Para cada posto, calcule a razão de compressão é o erro relativo. Encontre o posto onde a imagem se torna visualmente aceitável.

3. Construa um pequeno sistema de recomendacao. Crie uma matriz de avaliações usuário-filme 10x8 com algumas entradas conhecidas. Preencha as entradas faltantes com as médias das linhas. Calcule a SVD e reconstrua uma aproximação de posto 3. Use a matriz reconstruida para prever as avaliações faltantes. Verifique se as predições são razoaveis.

4. Crie uma matriz documento-termo 100x50 com 3 tópicos sintéticos. Cada tópico tem 5 termos associados. Adicione ruido. Aplique SVD e verifique se os 3 maiores valores singulares são muito maiores que o resto. Projete os documentos no espaço latente 3D e verifique se documentos do mesmo tópico se agrupam.

5. Gere uma matriz limpa de baixo posto (posto 3, tamanho 50x40) e adicione ruido gaussiano em diferentes níveis (sigma = 0.1, 0.5, 1.0, 2.0). Para cada nível de ruido, encontre o posto de truncamento ótimo varrendo k de 1 a 40 e medindo o erro de reconstrução em relação a matriz limpa. Plote como o k ótimo muda com o nível de ruido.

Termos-Chave

Leitura Adicional

• Gilbert Strang: Linear Álgebra and Its Applications, Chapter 7 - tratamento completo dá SVD com aplicações
• 3Blue1Brown: But what is the SVD? - intuição geométrica para a SVD
• We Recommend a Singular Value Decomposition - visao geral acessível dá American Mathematical Society
• Netflix Prize and Matrix Factorization - post original de blog de Simon Funk sobre SVD para recomendacoes
• Latent Semantic Analysis - a aplicacao original de NLP dá SVD
• Numerical Linear Álgebra by Trefethen and Bau - o padrão ouro para entender algoritmos de SVD e suas propriedades numéricas