v1 · padrão canônico

Lesson 117 — Singular value decomposition (SVD)

A = U Σ Vᵀ works for any real matrix. Singular values reveal the geometric structure. The foundation of image compression, recommendation, PCA, and the pseudoinverse.

Used in: 3.º ano do EM (17-18 anos) · Equiv. Lineare Algebra LK alemão · Equiv. H2 Math singapurense · Equiv. Math III japonês avançado

A = U\Sigma V^T

A SVD é a decomposição mais geral da álgebra linear: toda matriz $m \times n$ se escreve $A = U\Sigma V^T$ com $U$ e $V$ ortogonais e $\Sigma$ diagonal com valores singulares $\sigma_1 \geq \sigma_2 \geq \cdots \geq 0$ . A decomposição existe para qualquer matriz real (ou complexa) — mesmo retangular. É a base de PCA, compressão de imagem, recomendação e regressão estável.

Choose your door

Rigorous notation, full derivation, hypotheses

Definição e teorema

Teorema da SVD

"Any matrix A with rank r can be written as a product $A = U \Sigma V^T$ where U is orthogonal ( $m \times m$ ), $\Sigma$ is diagonal ( $m \times n$ , nonnegative entries decreasing), and V is orthogonal ( $n \times n$ ). The diagonal entries $\sigma_1 \geq \cdots \geq \sigma_r > 0$ are the singular values of A." — Understanding Linear Algebra, §6.3

"Theorem (Existence of SVD). Every real matrix A has a singular value decomposition. The singular values are the positive square roots of the nonzero eigenvalues of $A^T A$ ." — A First Course in Linear Algebra, §SVD

Conexão com autovalores

Os 4 subespaços fundamentais via SVD

Os 4 subespaços fundamentais de Strang lidos diretamente da SVD.

Teorema de Eckart-Young

Pseudoinversa de Moore-Penrose

Exemplos resolvidos

Example— 1· SVD de matriz quadrada 2x2 (aplicação)

Problema. Encontre a SVD de $A = \begin{pmatrix} 4 & 0 \\ 3 & -5 \end{pmatrix}$ .

Estratégia. Calcular $A^T A$ , encontrar autovalores e autovetores ortonormais para obter $V$ e os $\sigma_i$ ; depois $u_i = A v_i / \sigma_i$ .

Resolução.

Passo 1. $A^T A = \begin{pmatrix} 4 & 3 \\ 0 & -5 \end{pmatrix} \begin{pmatrix} 4 & 0 \\ 3 & -5 \end{pmatrix} = \begin{pmatrix} 25 & -15 \\ -15 & 25 \end{pmatrix}$ .

Passo 2. Autovalores: $\det(A^T A - \lambda I) = (25 - \lambda)^2 - 225 = 0 \Rightarrow \lambda = 25 \pm 15 = 40, 10$ .

Passo 3. Valores singulares: $\sigma_1 = \sqrt{40} = 2\sqrt{10}$ , $\sigma_2 = \sqrt{10}$ .

Passo 4. Autovetores de $A^T A$ :

Para $\lambda_1 = 40$ : $(A^TA - 40I)v = 0 \Rightarrow -15 v_1 - 15 v_2 = 0 \Rightarrow v_1 = -v_2$ . Logo $v_1 = (1, -1)/\sqrt{2}$ .
Para $\lambda_2 = 10$ : $v_2 = (1, 1)/\sqrt{2}$ .

Passo 5. Vetores singulares à esquerda:

u_1 = \frac{A v_1}{\sigma_1} = \frac{1}{2\sqrt{10}} \cdot \frac{1}{\sqrt{2}}\begin{pmatrix} 4 \\ 8 \end{pmatrix} = \frac{1}{\sqrt{20}}\begin{pmatrix} 2 \\ 4 \end{pmatrix}/\sqrt{2} = \frac{1}{\sqrt{5}}\begin{pmatrix} 1 \\ 2 \end{pmatrix}/\sqrt{?}

Cálculo simplificado: $A v_1 = \frac{1}{\sqrt{2}}(4, 8)^T$ ; $\|A v_1\| = \frac{\sqrt{80}}{\sqrt{2}} = \sqrt{40} = \sigma_1$ . Logo $u_1 = (1, 2)/\sqrt{5}$ .

Analogamente $A v_2 = \frac{1}{\sqrt{2}}(4, -2)^T$ ; $u_2 = (2, -1)/\sqrt{5}$ .

Resposta.

U = \frac{1}{\sqrt{5}}\begin{pmatrix} 1 & 2 \\ 2 & -1 \end{pmatrix}, \quad \Sigma = \begin{pmatrix} 2\sqrt{10} & 0 \\ 0 & \sqrt{10} \end{pmatrix}, \quad V = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}.

Verificação. $U \Sigma V^T = \frac{1}{\sqrt{5}}\begin{pmatrix}1 & 2 \\ 2 & -1\end{pmatrix}\begin{pmatrix}2\sqrt{10} & 0 \\ 0 & \sqrt{10}\end{pmatrix}\frac{1}{\sqrt{2}}\begin{pmatrix}1 & -1 \\ 1 & 1\end{pmatrix} = \begin{pmatrix}4 & 0 \\ 3 & -5\end{pmatrix} = A$ . Correto.

Fonte. Beezer, A First Course in Linear Algebra, §SVD — GNU FDL.

Example— 2· SVD de matriz retangular 3x2 (intermediário)

Problema. Calcule a SVD compacta de $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix}$ .

Estratégia. Para $A$ $3 \times 2$ , formar $A^T A$ $2 \times 2$ (mais fácil que $A A^T$ que seria $3 \times 3$ ).

Resolução.

$A^T A = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ .

Autovalores: $(2-\lambda)^2 - 1 = 0 \Rightarrow \lambda = 3, 1$ .

Valores singulares: $\sigma_1 = \sqrt{3}$ , $\sigma_2 = 1$ .

Autovetores: para $\lambda = 3$ : $v_1 = (1, 1)/\sqrt{2}$ . Para $\lambda = 1$ : $v_2 = (1, -1)/\sqrt{2}$ .

Vetores à esquerda:

$u_1 = \frac{A v_1}{\sigma_1} = \frac{1}{\sqrt{3}} \cdot \frac{1}{\sqrt{2}}\begin{pmatrix}2\\1\\1\end{pmatrix} = \frac{1}{\sqrt{6}}\begin{pmatrix}2\\1\\1\end{pmatrix}$ .

$u_2 = \frac{A v_2}{\sigma_2} = \frac{1}{\sqrt{2}}\begin{pmatrix}0\\1\\-1\end{pmatrix}$ .

Resposta (forma compacta, descartando coluna nula).

U_2 = \begin{pmatrix} 2/\sqrt{6} & 0 \\ 1/\sqrt{6} & 1/\sqrt{2} \\ 1/\sqrt{6} & -1/\sqrt{2} \end{pmatrix}, \quad \Sigma_2 = \begin{pmatrix} \sqrt{3} & 0 \\ 0 & 1 \end{pmatrix}, \quad V = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.

Verificação. O posto de $A$ é 2 (linhas $(1,1), (1,0), (0,1)$ têm 2 LI). Logo a SVD compacta tem exatamente 2 valores singulares positivos. Verificado.

Fonte. Beezer, A First Course in Linear Algebra, §SVD Example SVD3by2 — GNU FDL.

Example— 3· Aproximação de posto 1 e Eckart-Young (intermediário)

Problema. Para $A = \begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix}$ , encontre a melhor aproximação de posto 1 e calcule o erro de Frobenius.

Estratégia. Aplicar SVD, tomar o primeiro termo da expansão $A_1 = \sigma_1 u_1 v_1^T$ e calcular $\|A - A_1\|_F = \sigma_2$ .

Resolução.

Da Porta 25: $\sigma_1 = 3\sqrt{5}$ , $\sigma_2 = \sqrt{5}$ , $u_1 = (1, 3)/\sqrt{10}$ , $v_1 = (1, 1)/\sqrt{2}$ .

$A_1 = \sigma_1 u_1 v_1^T = 3\sqrt{5} \cdot \frac{1}{\sqrt{10}}\begin{pmatrix}1\\3\end{pmatrix} \cdot \frac{1}{\sqrt{2}}(1, 1) = \frac{3\sqrt{5}}{\sqrt{20}}\begin{pmatrix}1 & 1 \\ 3 & 3\end{pmatrix} = \frac{3}{2}\begin{pmatrix}1 & 1 \\ 3 & 3\end{pmatrix} = \begin{pmatrix}1{,}5 & 1{,}5 \\ 4{,}5 & 4{,}5\end{pmatrix}$ .

Erro: $A - A_1 = \begin{pmatrix}1{,}5 & -1{,}5 \\ -0{,}5 & 0{,}5\end{pmatrix}$ .

$\|A - A_1\|_F = \sqrt{1{,}5^2 + 1{,}5^2 + 0{,}5^2 + 0{,}5^2} = \sqrt{5} = \sigma_2$ .

Verificação. Conforme Eckart-Young, $\|A - A_k\|_F = \sqrt{\sum_{i>k} \sigma_i^2}$ . Aqui $k = 1$ , então $\|A - A_1\|_F = \sigma_2 = \sqrt{5} \approx 2{,}236$ . Compatível com nosso cálculo direto.

Energia capturada. $\sigma_1^2 / (\sigma_1^2 + \sigma_2^2) = 45/50 = 90\%$ . A aproximação de posto 1 captura 90% da energia de $A$ .

Fonte. Austin, Understanding Linear Algebra, §6.4 — CC-BY-SA.

Example— 4· Pseudoinversa e mínimos quadrados (avançado)

Problema. Use SVD para encontrar a solução de mínimos quadrados de $Ax = b$ , onde $A = \begin{pmatrix} 1 & 1 \\ 1 & 1 \\ 0 & 1 \end{pmatrix}$ e $b = (2, 0, 3)^T$ .

Estratégia. Calcular SVD compacta de $A$ , formar pseudoinversa $A^+ = V \Sigma^+ U^T$ , computar $x^* = A^+ b$ .

Resolução.

$A^T A = \begin{pmatrix} 2 & 2 \\ 2 & 3 \end{pmatrix}$ . Autovalores: $\det = (2-\lambda)(3-\lambda) - 4 = \lambda^2 - 5\lambda + 2 = 0$ , logo $\lambda = (5 \pm \sqrt{17})/2$ .

Numericamente: $\lambda_1 \approx 4{,}561$ , $\lambda_2 \approx 0{,}439$ . Valores singulares: $\sigma_1 \approx 2{,}136$ , $\sigma_2 \approx 0{,}662$ .

Autovetores (após normalização): $v_1 \approx (0{,}615, 0{,}789)^T$ , $v_2 \approx (0{,}789, -0{,}615)^T$ .

Vetores singulares à esquerda: $u_i = A v_i / \sigma_i$ . Cálculo direto dá $u_1 \approx (0{,}658, 0{,}658, 0{,}369)^T$ e $u_2 \approx (0{,}198, 0{,}198, -0{,}929)^T$ .

Pseudoinversa: $A^+ = V \text{diag}(1/\sigma_1, 1/\sigma_2) U^T$ .

Solução: $x^* = A^+ b$ . Equivalentemente, como $A$ tem posto completo de colunas, $x^* = (A^T A)^{-1} A^T b$ .

$A^T b = (2, 5)^T$ , $(A^T A)^{-1} = \frac{1}{2}\begin{pmatrix}3 & -2 \\ -2 & 2\end{pmatrix}$ .

$x^* = \frac{1}{2}\begin{pmatrix}3 & -2 \\ -2 & 2\end{pmatrix}\begin{pmatrix}2\\5\end{pmatrix} = \frac{1}{2}\begin{pmatrix}-4 \\ 6\end{pmatrix} = \begin{pmatrix}-2 \\ 3\end{pmatrix}$ .

Verificação. $A x^* = (1, 1, 3)^T$ ; resíduo $b - Ax^* = (1, -1, 0)^T$ ; norma $\sqrt{2}$ . O resíduo é ortogonal a $\text{col}(A)$ : $A^T(b - Ax^*) = (1 \cdot 1 + 1 \cdot (-1), 1 \cdot 1 + 1 \cdot (-1) + 1 \cdot 0)^T = (0, 0)^T$ . Correto.

Observação. Como $A$ tem posto completo, SVD e equações normais dão o mesmo resultado. Mas se $A$ tivesse posto deficiente, apenas SVD funcionaria (equações normais teriam infinitas soluções).

Fonte. Hefferon, Linear Algebra, cap. 5, §IV — CC-BY-SA.

Example— 5· Demonstrar existência da SVD via teorema espectral (demonstração)

Problema. Mostre que toda matriz $A \in \mathbb{R}^{m \times n}$ admite SVD, usando o teorema espectral de matrizes simétricas reais.

Estratégia. Aplicar o teorema espectral à matriz $A^T A$ (simétrica PSD), construir $V$ e $\Sigma$ , depois definir $U$ via $u_i = A v_i / \sigma_i$ e completar a base.

Resolução.

Passo 1. $A^T A \in \mathbb{R}^{n \times n}$ é simétrica e PSD (mostrado em L116, Exemplo 5).

Passo 2. Pelo teorema espectral (L116), existem autovalores $\lambda_1 \geq \cdots \geq \lambda_n \geq 0$ e autovetores ortonormais $v_1, \ldots, v_n$ tais que $A^T A v_i = \lambda_i v_i$ .

Passo 3. Seja $r$ o número de $\lambda_i > 0$ . Defina $\sigma_i = \sqrt{\lambda_i}$ para $i \leq r$ .

Passo 4. Para $i \leq r$ , defina $u_i = A v_i / \sigma_i \in \mathbb{R}^m$ . Verifique:

$\langle u_i, u_j \rangle = \frac{(Av_i)^T(Av_j)}{\sigma_i \sigma_j} = \frac{v_i^T A^T A v_j}{\sigma_i \sigma_j} = \frac{\lambda_j v_i^T v_j}{\sigma_i \sigma_j} = \frac{\lambda_j \delta_{ij}}{\sigma_i \sigma_j} = \delta_{ij}$ .

Logo $u_1, \ldots, u_r$ são ortonormais.

Passo 5. Complete $u_{r+1}, \ldots, u_m$ com base ortonormal de $\ker(A^T) = (\text{col}(A))^\perp$ . (Existe por Gram-Schmidt.) Então $U = [u_1 | \cdots | u_m] \in \mathbb{R}^{m \times m}$ é ortogonal.

Passo 6. Verifique $A = U \Sigma V^T$ . Equivalentemente, $A V = U \Sigma$ . Para $i \leq r$ : $(AV)_{:,i} = A v_i = \sigma_i u_i = (U\Sigma)_{:,i}$ . Para $i > r$ : $A v_i = 0$ (pois $\|A v_i\|^2 = v_i^T A^T A v_i = \lambda_i = 0$ ) e $(U\Sigma)_{:,i} = 0$ . Logo $AV = U\Sigma$ , ou seja $A = U \Sigma V^T$ . $\square$

Observação. A unicidade dos $\sigma_i$ segue da unicidade dos autovalores de $A^T A$ . Os $u_i, v_i$ são únicos quando os $\sigma_i$ são distintos e positivos; em caso de multiplicidade, há liberdade de rotação dentro do auto-espaço.

Fonte. Beezer, A First Course in Linear Algebra, §SVD Theorem EXIST-SVD — GNU FDL.

Exercise list

40 exercises · 10 with worked solution (25%)

Application 11Understanding 13Proof 16

Fontes

Beezer, A First Course in Linear Algebra — Rob Beezer · 2023 (3.50) · EN · GNU FDL · §SVD. Fonte primária desta lição: prova rigorosa de existência da SVD via teorema espectral em $A^T A$ , lemas auxiliares e exemplos numéricos completos.
Austin, Understanding Linear Algebra — David Austin · 2024 · EN · CC-BY-SA · §6.3–6.4 (Singular Value Decomposition, Low-rank approximations). Apresentação geométrica com transformação do círculo unitário em elipse, motivação aplicada à compressão e à PCA.
Hefferon, Linear Algebra — Jim Hefferon · 2020 (4th ed) · EN · CC-BY-SA · cap. 5, §IV. Exercícios de cálculo numérico, pseudoinversa Moore-Penrose e mínimos quadrados regularizados.