Exercícios — Aula 5: Decomposição em Valores Singulares (SVD)

Álgebra Linear e Otimização para Aprendizado de Máquina

Autor

Prof. Marcos Medeiros Raimundo

Aula Soluções

Convenções usadas nesta lista

Para qualquer \(A\in\mathbb{R}^{m\times n}\) (quadrada ou não), a SVD (Decomposição em Valores Singulares) é \(A=U\Sigma V^T\), com \(U\in\mathbb{R}^{m\times m}\) e \(V\in\mathbb{R}^{n\times n}\) ortogonais (\(U^TU=I\), \(V^TV=I\)) e \(\Sigma\in\mathbb{R}^{m\times n}\) “diagonal” (zero fora da diagonal principal) com entradas \(\sigma_1\ge\sigma_2\ge\dots\ge0\), os valores singulares. O número de valores singulares estritamente positivos é igual ao posto de \(A\).
Construção: as colunas \(\mathbf{v}_i\) de \(V\) (vetores singulares à direita) são autovetores de \(A^TA\) — que é sempre simétrica semidefinida positiva, qualquer que seja \(A\) (mesmo prova de definitude usada para \(X^TX\): \((A^TA)^T=A^TA\), e \(\mathbf{x}^TA^TA\mathbf{x}=\|A\mathbf{x}\|_2^2\ge0\)), logo seus autovalores \(\lambda_i\) são reais e \(\ge0\); \(\sigma_i:=\sqrt{\lambda_i}\); as colunas \(\mathbf{u}_i\) de \(U\) (vetores singulares à esquerda) vêm de \(\mathbf{u}_i=A\mathbf{v}_i/\sigma_i\) (para \(\sigma_i>0\)).
A norma espectral de \(A\) é \(\|A\|_2=\max_{\mathbf{x}\ne\mathbf{0}}\|A\mathbf{x}\|_2/\|\mathbf{x}\|_2=\sigma_1\) (o maior valor singular); a norma de Frobenius é \(\|A\|_F=\sqrt{\sum_i\sigma_i^2}\) (equivalentemente, a raiz da soma dos quadrados de todas as entradas de \(A\)).
A aproximação de posto \(k\) de \(A\) é \(\hat{A}^{(k)}=\sum_{i=1}^k\sigma_i\mathbf{u}_i\mathbf{v}_i^T\) (os \(k\) primeiros termos da SVD). O Teorema de Eckart-Young-Mirsky garante que \(\hat{A}^{(k)}\) minimiza \(\|A-B\|_2\) (e também \(\|A-B\|_F\)) entre todas as matrizes \(B\) de posto \(\le k\); o erro mínimo é \(\sigma_{k+1}\) em norma espectral, e \(\sqrt{\sum_{i>k}\sigma_i^2}\) em norma de Frobenius.
A Decomposição Polar de uma matriz quadrada \(A\) é \(A=QS\), com \(Q=UV^T\) ortogonal e \(S=V\Sigma V^T\) simétrica semidefinida positiva — obtida rearranjando os fatores da SVD.
Para matrizes simétricas, o Teorema Espectral Real garante \(A=Q\Lambda Q^T\), com \(Q\) ortogonal e \(\Lambda\) diagonal de autovalores reais.
Para \(X\in\mathbb{R}^{N\times d}\) de posto completo, vale \(\sigma_i(X)^2=\lambda_i(X^TX)\) para todo \(i\); como \(\text{cond}(X)=\sigma_{\max}(X)/\sigma_{\min}(X)\) e \(\text{cond}(X^TX)=\lambda_{\max}(X^TX)/\lambda_{\min}(X^TX)\), segue \(\text{cond}(X^TX)=\text{cond}(X)^2\).
Problema Motivador usado nesta lista: três espectadores (Ali, Beatrix, Chandra) avaliam quatro filmes (Guerra nas Estrelas, Blade Runner, Amélie Poulain, Delicatessen) numa escala de \(0\) a \(5\), formando uma matriz de notas \(A\in\mathbb{R}^{4\times3}\) (uma linha por filme, uma coluna por espectador) de posto \(3\) (posto completo). A SVD trunca essa matriz em “perfis”: os vetores singulares à esquerda \(\mathbf{u}_i\) podem ser lidos como “filmes estereotípicos” (perfis de tema, ex.: ficção científica vs. cinema de arte) e os vetores singulares à direita \(\mathbf{v}_i\) como “espectadores estereotípicos” (perfis de gosto) — sob a suposição de que cada espectador avalia filmes como combinação linear desses perfis.

Questões discursivas

Explique, com suas próprias palavras, por que a Decomposição Polar (ver Convenções acima) exige que \(A\) seja quadrada, enquanto a SVD não exige isso — aponte, com precisão, o passo algébrico da construção de \(Q\) e \(S\) que deixa de fazer sentido se \(A\) for retangular.
A prova do Teorema de Eckart-Young-Mirsky usa, numa de suas partes, uma contagem de dimensão entre dois subespaços — o núcleo de uma matriz candidata \(B\) de posto \(k\), \(\ker(B)\), e o subespaço gerado pelos \(k+1\) primeiros vetores singulares à direita, \(\text{span}(\mathbf{v}_1,\dots,\mathbf{v}_{k+1})\) — para chegar a uma contradição (mostrando que nenhuma matriz de posto \(k\) pode fazer melhor que \(\hat{A}^{(k)}\) em norma espectral). Reproduza esse argumento e explique, especificamente, por que a soma das duas dimensões ultrapassar \(n\) (a dimensão do espaço ambiente) é a peça central da contradição.
Compare dois papéis que a matriz \(X^TX\) (ver Convenções) pode desempenhar: como matriz das Equações Normais de um ajuste por mínimos quadrados, e como objeto central de estudo de autovalores, definitude e número de condição. Compare também com o papel que \(X^TX\) desempenha na construção da SVD de \(X\) (ver Convenções). Explique por que a relação \(\text{cond}(X^TX)=\text{cond}(X)^2\) é uma consequência direta dessa mesma relação entre \(X\) e \(X^TX\), e não um fato novo e independente.

Questões de Verdadeiro/Falso

Cada bloco de 4 itens trata do mesmo tema. A questão só é considerada correta se todos os 4 itens forem julgados corretamente (deixar em branco tem penalidade de 20% da nota da questão).

Teste 1 — Existência e formato da SVD

□ A SVD de \(A\in\mathbb{R}^{m\times n}\) sempre existe, mesmo quando \(A\) tem alguns autovalores complexos (no caso em que \(A\) é quadrada).
□ Se \(A\in\mathbb{R}^{5\times 2}\) tiver posto \(2\), sua matriz \(\Sigma\) na SVD reduzida é uma matriz diagonal \(2\times 2\) com ambas as entradas estritamente positivas.
□ Numa matriz de adjacência de um grafo bipartido (linhas = usuários, colunas = produtos, entrada \(1\) se o usuário comprou o produto), a SVD está bem definida mesmo que o número de usuários seja muito diferente do número de produtos.
□ Como toda matriz quadrada tem autovalores (reais ou complexos) e toda matriz retangular tem valores singulares, isso implica que autovalor e valor singular são, no fundo, o mesmo conceito com nomes diferentes.

Teste 2 — Construção via \(A^TA\) e \(AA^T\)

□ Se \(A^TA\) tiver um autovalor com multiplicidade geométrica \(2\) (autoespaço de dimensão \(2\)), os dois vetores singulares à direita associados a esse autovalor não são únicos — qualquer base ortonormal desse autoespaço serve.
□ Se \(A\) for a matriz nula (\(A=\mathbf{0}\), todas as entradas zero), a construção da SVD descrita acima ainda produz uma SVD válida, com todos os valores singulares iguais a zero.
□ Numa matriz de co-ocorrência de palavras (linhas e colunas ambas indexadas pelo vocabulário, entrada = frequência conjunta), \(A^TA\) e \(AA^T\) continuam sendo, cada uma, simétricas e semidefinidas positivas, pela mesma prova geral (ver Convenções).
□ Como os vetores singulares à esquerda são definidos como \(\mathbf{u}_i=A\mathbf{v}_i/\sigma_i\), isso implica que, para calcular \(U\), é sempre necessário calcular também a decomposição espectral de \(AA^T\) separadamente.

Teste 3 — Valores singulares e norma espectral

□ Se todos os valores singulares de \(A\) forem iguais a um mesmo valor \(c>0\), então \(\|A\mathbf{x}\|_2=c\|\mathbf{x}\|_2\) para todo vetor \(\mathbf{x}\), não só para o vetor que maximiza a razão.
□ Para uma matriz identidade \(I_n\in\mathbb{R}^{n\times n}\), a norma espectral \(\|I_n\|_2\) tende a infinito conforme \(n\to\infty\).
□ Na matriz de pesos de uma camada linear de uma rede neural, \(\|W\|_2\) (a norma espectral) limita o quanto essa camada pode, no pior caso, amplificar a norma de um vetor de ativação que passa por ela.
□ Como a norma espectral é o maior valor singular, isso implica que a soma de todos os valores singulares de \(A\) é igual à norma de Frobenius de \(A\).

Teste 4 — Aproximação de baixo posto e SVD truncada

□ Se \(\sigma_3\) de uma matriz \(A\) de posto \(5\) for exatamente igual a \(\sigma_4\), a aproximação de posto \(3\), \(\hat{A}^{(3)}\), ainda assim fica bem definida e única.
□ No limite em que se usa \(k=\text{posto}(A)\) (isto é, sem truncar nada), a aproximação \(\hat{A}^{(k)}\) coincide exatamente com \(A\).
□ Numa matriz de avaliações de estudantes (linhas = estudantes, colunas = provas, entrada = nota), uma aproximação de posto \(1\) equivaleria, aproximadamente, a resumir cada estudante por uma única nota de “habilidade geral” e cada prova por um único peso de “dificuldade”.
□ Como a aproximação de posto-\(k\) descarta os \(\sigma_i\) menores, isso implica que ela sempre preserva os valores absolutos exatos das entradas mais extremas (maiores em módulo) da matriz original \(A\).

Teste 5 — Eckart-Young-Mirsky

□ Se existisse uma matriz \(B\) de posto \(k\) com \(\|A-B\|_2\) estritamente menor que \(\|A-\hat{A}^{(k)}\|_2\), isso contradiria diretamente o Teorema de Eckart-Young-Mirsky.
□ No caso extremo \(k=0\) (a única matriz de “posto \(0\)” é a matriz nula), o Teorema de Eckart-Young-Mirsky garante que \(\|A-\mathbf{0}\|_2=\sigma_1\), isto é, a própria norma espectral de \(A\).
□ Num sistema de compressão de imagens que usa aproximação de baixo posto (como o clássico exemplo de comprimir a imagem de um monumento reduzindo o posto de sua matriz de pixels), a mesma garantia de otimalidade do Teorema de Eckart-Young-Mirsky se aplica, já que comprimir uma imagem é, matematicamente, aproximar sua matriz de pixels por uma de posto menor.
□ O próprio nome “Eckart-Young-Mirsky” vem da generalização de Mirsky (1960): a mesma \(\hat{A}^{(k)}\) que minimiza \(\|A-B\|_2\) também minimiza \(\|A-B\|_F\) (norma de Frobenius) entre as matrizes de posto \(k\) — e, por ser a mesma matriz minimizadora nos dois casos, isso implica que o valor mínimo do erro é numericamente igual nas duas normas.

Teste 6 — Decomposição Polar

□ Se a matrix quadrada \(A\) já for ortogonal (\(A^TA=I\)), sua Decomposição Polar tem \(S=I\) e \(Q=A\).
□ Se todos os valores singulares da matrix quadrada \(A\) forem iguais entre si (\(\sigma_1=\dots=\sigma_n=c\)), o fator \(S\) da Decomposição Polar é exatamente \(cI\) (um múltiplo escalar da identidade).
□ Numa iteração de treinamento de rede neural que ortogonaliza a matriz de atualização de pesos antes de aplicá-la (o algoritmo iterativo de Newton-Schulz), o alvo dessa ortogonalização é precisamente o fator \(Q\) da Decomposição Polar da matriz de atualização original.
□ Como \(S\) é sempre semidefinida positiva na Decomposição Polar, isso implica que \(S\) é sempre invertível, qualquer que seja \(A\).

Teste 7 — SVD vs. decomposição espectral

□ Se \(A\) for simétrica, a SVD de \(A\) e a decomposição espectral de \(A\) (ver Convenções) coincidem exatamente, com \(U=V=Q\) e \(\Sigma=|\Lambda|\) (valor absoluto de cada autovalor).
□ Se \(A\) for simétrica mas tiver algum autovalor negativo, os vetores singulares (à esquerda ou à direita) associados a esse autovalor podem diferir, em sinal, do autovetor correspondente da decomposição espectral.
□ Numa matriz de covariância empírica de atributos (sempre simétrica semidefinida positiva), calcular a SVD ou a decomposição espectral dá exatamente o mesmo resultado, sem nenhuma diferença de sinal a se preocupar.
□ Como toda matriz simétrica tem decomposição espectral (ver Convenções), isso implica que só matrizes simétricas têm SVD, já que a SVD seria apenas um caso particular da decomposição espectral.

Teste 8 — A SVD aplicada a \(X\): posto e número de condição

□ Se uma quinta coluna fosse adicionada a uma matriz de design \(X\in\mathbb{R}^{16\,640\times4}\) como cópia exata de uma coluna já existente (multiplicada por um escalar não-nulo), o quinto valor singular da nova matriz \(X'\in\mathbb{R}^{16\,640\times 5}\) seria exatamente zero.
□ Aumentar artificialmente a escala de uma única coluna de \(X\) (por exemplo, medir um atributo em unidades \(1000\times\) maiores) nunca muda nenhum dos valores singulares de \(X\).
□ Num modelo de regressão sobre o dataset Breast Cancer Wisconsin (atributos em escalas bem diferentes, como área do núcleo celular vs. simetria), a mesma relação \(\text{cond}(X^TX)=\text{cond}(X)^2\) se aplicaria à matriz de design correspondente.
□ Como \(\sigma_i(X)^2=\lambda_i(X^TX)\) para todo \(i\), isso implica que o vetor singular à esquerda \(\mathbf{u}_1\) de \(X\) é igual ao autovetor principal de \(X^TX\).

Teste 9 — Filtragem colaborativa e interpretação de perfis latentes

□ Na matriz de notas de filmes descrita nas Convenções acima, se um quarto espectador desse nota \(5\) a todos os quatro filmes por igual, esse espectador contribuiria para um valor singular adicional além dos três já existentes, mesmo que sua nota não distinga nenhum tema.
□ No limite em que só se usa o primeiro perfil latente (\(k=1\)), a filtragem colaborativa deste exemplo passa a prever a mesma proporção relativa de notas de ficção científica para qualquer espectador.
□ Num sistema de recomendação de música (matriz usuário \(\times\) artista, notas de audição implícitas), a mesma lógica de perfis latentes via SVD/aproximação de baixo posto se aplicaria, trocando “filme”/“espectador” por “artista”/“ouvinte”.
□ Como a interpretação de \(\mathbf{u}_i\)/\(\mathbf{v}_i\) como “temas”/“perfis” depende da suposição de que as notas seguem exatamente uma combinação linear desses perfis, essa interpretação deveria ser tratada como uma leitura conveniente, não como um fato provado sobre os dados.