Soluções — Aula 5: Decomposição em Valores Singulares (SVD)
Gabarito de exercicios.qmd
Dica(Resposta) Teste 1 — Existência e formato da SVD
- ✔ Verdadeiro — A construção da SVD nunca usa os autovalores de \(A\) propriamente dita — usa os autovalores de \(A^TA\), que são sempre reais e não-negativos, qualquer que seja \(A\). Uma matriz de rotação \(2\times 2\), por exemplo, tem autovalores complexos mas SVD perfeitamente real e bem definida (\(U=V=I\), \(\Sigma=I\), já que rotações preservam norma).
- ✔ Verdadeiro — O número de valores singulares estritamente positivos é, por construção, exatamente igual ao posto de \(A\). Posto \(2\) (o máximo possível para uma matriz de \(2\) colunas) significa exatamente \(2\) valores singulares positivos — a SVD reduzida, ao descartar as direções com \(\sigma=0\), fica com \(\Sigma\) diagonal \(2\times 2\) sem nenhum zero na diagonal.
- ✔ Verdadeiro — A existência da SVD não impõe nenhuma relação entre \(m\) e \(n\) — a SVD existe para qualquer \(A\in\mathbb{R}^{m\times n}\), incluindo matrizes extremamente “compridas” ou “largas” (é exatamente o caso da matriz de design \(X\) do exemplo do California Housing, \(16\,640\times 4\)).
- ✗ Falso — São conceitos relacionados, não idênticos. Autovalor satisfaz \(A\mathbf{x}=\lambda\mathbf{x}\) (mesmo espaço nos dois lados); valor singular satisfaz \(A\mathbf{v}_i=\sigma_i\mathbf{u}_i\) (espaços possivelmente diferentes, já que \(A\) pode ser retangular). Só coincidem, e mesmo assim a menos de sinal, quando \(A\) é simétrica (ver bloco “SVD vs. decomposição espectral”).
Dica(Resposta) Teste 2 — Construção via \(A^TA\) e \(AA^T\)
- ✔ Verdadeiro — Dentro de um autoespaço de dimensão \(\ge 2\), qualquer base ortonormal desse subespaço é uma escolha válida de autovetores (mesmo fenômeno de não-unicidade de autovetores em autoespaços de dimensão \(>1\)). Como os vetores singulares à direita são autovetores de \(A^TA\), a mesma não-unicidade se aplica — e os vetores singulares à esquerda correspondentes (\(\mathbf{u}_i=A\mathbf{v}_i/\sigma_i\)) se ajustam automaticamente para qualquer escolha de base feita.
- ✔ Verdadeiro — \(A=\mathbf{0}\Rightarrow A^TA=\mathbf{0}\), cujo único autovalor é \(\lambda=0\) (multiplicidade \(n\)) — logo todo \(\sigma_i=\sqrt{0}=0\). A decomposição \(A=U\Sigma V^T\) com \(\Sigma=\mathbf{0}\) vale para qualquer escolha ortogonal de \(U,V\) (por exemplo \(U=I_m,V=I_n\)) — um caso degenerado, mas ainda uma SVD tecnicamente válida, consistente com a existência da SVD não excluir \(\text{posto}(A)=0\).
- ✔ Verdadeiro — A prova de que \(A^TA\) (e, por simetria do argumento, \(AA^T\)) é simétrica e semidefinida positiva não faz nenhuma suposição sobre o que as entradas de \(A\) representam — vale para qualquer matriz real, seja ela de preços de imóveis, notas de filmes ou frequências de co-ocorrência de palavras.
- ✗ Falso — Essa é precisamente a economia que a construção oferece: uma vez que \(V\) já foi obtida diagonalizando \(A^TA\), \(U\) vem de graça, calculando \(\mathbf{u}_i=A\mathbf{v}_i/\sigma_i\) diretamente — sem nenhuma diagonalização adicional de \(AA^T\). (É verdade que \(AA^T\) tem os mesmos \(\mathbf{u}_i\) como autovetores, mas isso é uma caracterização alternativa, não um passo obrigatório do cálculo.)
Dica(Resposta) Teste 3 — Valores singulares e norma espectral
- ✗ Falso — A igualdade \(\|A\mathbf{x}\|_2 = c\|\mathbf{x}\|_2\) só é válida para todo \(\mathbf{x}\) se \(A\) for uma matriz quadrada ou alta (\(m \ge n\)). Para matrizes largas (\(m < n\)), mesmo que todos os \(m\) valores singulares sejam iguais a \(c\), existe um núcleo não-trivial (\(\text{dim}(\text{null}(A)) \ge n - m \ge 1\)). Para qualquer vetor não-nulo \(\mathbf{x} \in \text{null}(A)\), obtém-se \(\|A\mathbf{x}\|_2 = 0 \neq c\|\mathbf{x}\|_2\).
- ✗ Falso — \(\|I_n\mathbf{x}\|_2/\|\mathbf{x}\|_2=1\) para todo \(\mathbf{x}\ne\mathbf{0}\) e todo \(n\) — a norma espectral de \(I_n\) é sempre exatamente \(1\) (todos os valores singulares de \(I_n\) são \(1\)), independente da dimensão.
- ✔ Verdadeiro — É exatamente a definição de norma espectral aplicada a \(W\): \(\|W\|_2=\max_{\mathbf{x}\ne\mathbf{0}}\|W\mathbf{x}\|_2/\|\mathbf{x}\|_2\) — o maior fator de amplificação possível. Essa é a base de técnicas de regularização por normalização espectral em redes neurais profundas.
- ✗ Falso — Confunde três normas matriciais distintas: a norma espectral é \(\sigma_1\) (o maior); a norma de Frobenius é \(\sqrt{\sum_i\sigma_i^2}\) (soma dos quadrados, com raiz); a soma simples \(\sum_i\sigma_i\) é uma quarta quantidade (a norma nuclear), diferente das outras duas.
Dica(Resposta) Teste 4 — Aproximação de baixo posto e SVD truncada
- ✗ Falso — O Teorema de Eckart-Young-Mirsky garante que o valor do erro mínimo, \(\sigma_4\), é bem definido — mas não garante que a matriz minimizadora seja única quando há empate entre \(\sigma_k\) e \(\sigma_{k+1}\). Com \(\sigma_3=\sigma_4\), o subespaço de \(2\) dimensões associado a esse valor singular repetido admite infinitas escolhas ortonormais equivalentes (mesmo fenômeno de autoespaço de dimensão \(\ge 2\) do bloco anterior), e diferentes escolhas produzem diferentes matrizes \(\hat{A}^{(3)}\), todas atingindo o mesmo erro mínimo — a unicidade da matriz só é garantida quando \(\sigma_k>\sigma_{k+1}\) estritamente.
- ✔ Verdadeiro — Com \(k=r=\text{posto}(A)\), a soma \(\hat{A}^{(k)}=\sum_{i=1}^k\sigma_i\mathbf{u}_i\mathbf{v}_i^T\) inclui todos os termos não-nulos da decomposição \(A=\sum_{i=1}^r\sigma_i\mathbf{u}_i\mathbf{v}_i^T\) — não há nada para descartar, logo \(\hat{A}^{(k)}=A\) exatamente (erro \(\sigma_{k+1}=0\), já que não existe \((k+1)\)-ésimo valor singular não-nulo).
- ✔ Verdadeiro — Mesma interpretação usada para a matriz de notas de filmes (ver Convenções em
exercicios.qmd): num rank-1, \(\hat{A}^{(1)}=\sigma_1\mathbf{u}_1\mathbf{v}_1^T\), cada entrada vira um produto de um número por estudante (\(\mathbf{v}_1\), “habilidade”) por um número por prova (\(\mathbf{u}_1\), “dificuldade”) — a mesma estrutura matemática usada em modelos clássicos de teoria de resposta ao item (IRT) de um parâmetro. - ✗ Falso — A aproximação de baixo posto é uma projeção de \(A\) sobre o subespaço de matrizes de posto \(\le k\) — ela minimiza o erro agregado (em norma espectral ou de Frobenius), não preserva nenhuma entrada individual exatamente. No exemplo da matriz de notas de filmes (ver Convenções), mesmo as notas máximas (\(5\)) da matriz original viram \(4{,}78\), \(4{,}97\) etc. na aproximação de posto \(2\) — nenhuma entrada extrema fica intacta.
Dica(Resposta) Teste 5 — Eckart-Young-Mirsky
- ✔ Verdadeiro — É a própria definição de \(\hat{A}^{(k)}\) ser o minimizador de \(\|A-B\|_2\) sobre todas as matrizes de posto \(k\) — por definição de mínimo, nenhuma outra matriz de posto \(k\) pode fazer estritamente melhor. Encontrar tal \(B\) seria, literalmente, uma contradição da tese do teorema.
- ✔ Verdadeiro — Com \(k=0\), \(\hat{A}^{(0)}=\mathbf{0}\) (soma vazia) e a fórmula do erro mínimo dá \(\|A-\hat{A}^{(0)}\|_2=\sigma_{0+1}=\sigma_1\) — que é exatamente \(\|A\|_2\), a própria norma espectral de \(A\) (ver Convenções). Os dois resultados ficam consistentes nesse caso-limite, como deveriam.
- ✔ Verdadeiro — Uma imagem em tons de cinza é, matematicamente, só uma matriz de valores de pixel — a aproximação de posto-\(k\) dessa matriz é ótima em norma espectral pela mesma prova geral do teorema, independente de a matriz representar preços de imóveis, notas de filmes ou intensidades de pixel.
- ✗ Falso — A premissa está correta — Mirsky (1960) estendeu o resultado original de Eckart-Young (que valia para a norma de Frobenius) para mostrar que a mesma \(\hat{A}^{(k)}\) minimiza o erro em qualquer norma unitariamente invariante, incluindo a espectral e a de Frobenius simultaneamente (é por isso que o teorema leva os três nomes). Mas a conclusão do item erra: minimizadora igual não significa valor mínimo igual — em norma espectral o erro mínimo é \(\sigma_{k+1}\); em norma de Frobenius é \(\sqrt{\sum_{i>k}\sigma_i^2}\) (soma de todos os valores singulares descartados, não só o primeiro). Verificação numérica na matriz de notas de filmes (\(k=1\), ver Convenções): erro espectral \(\approx6{,}364\) contra erro de Frobenius \(\approx6{,}403\) — próximos, mas não iguais.
Dica(Resposta) Teste 6 — Decomposição Polar
- ✔ Verdadeiro — \(A\) ortogonal \(\Rightarrow A^TA=I\Rightarrow\) todos os autovalores de \(A^TA\) são \(1\) \(\Rightarrow\) todos os \(\sigma_i=1\) \(\Rightarrow\Sigma=I\). Daí \(S=V\Sigma V^T=VIV^T=I\), e como \(A=QS=QI=Q\), segue \(Q=A\) necessariamente — não há ambiguidade nesse caso, porque \(S=I\) já fixa \(Q\) de forma única.
- ✔ Verdadeiro — \(S=V\Sigma V^T=V(cI)V^T=c(VV^T)=cI\) (usando \(VV^T=I\), \(V\) ortogonal) — o mesmo cálculo do item (a) do bloco “Valores singulares e norma espectral”, agora aplicado à Decomposição Polar.
- ✔ Verdadeiro — Newton-Schulz é um método iterativo que converge para o fator \(Q\) (ortogonal) da Decomposição Polar de uma matriz, sem calcular a SVD completa — mais barato computacionalmente para matrizes grandes de atualização de pesos.
- ✗ Falso — Semidefinida positiva não é o mesmo que definida positiva/invertível — se \(A\) for singular (algum \(\sigma_i=0\)), \(S=V\Sigma V^T\) tem esse mesmo autovalor \(0\), logo \(S\) também é singular. A mesma confusão (semidefinida positiva \(\ne\) invertível) aparece no bloco seguinte destes Exercícios.
Dica(Resposta) Teste 7 — SVD vs. decomposição espectral
- ✗ Falso — A afirmação só vale quando \(A\) é, além de simétrica, semidefinida positiva (todos os autovalores \(\ge 0\)): definindo \(U=V=Q\) e \(\Sigma=\Lambda\), a SVD de uma matriz simétrica semidefinida positiva coincide com sua decomposição espectral. Para uma matriz simétrica com algum autovalor negativo, \(U\) e \(V\) não podem ser iguais entre si e iguais a \(Q\) simultaneamente — ver item (b) a seguir.
- ✔ Verdadeiro — Para um autovalor \(\lambda_i<0\) de \(A=Q\Lambda Q^T\), \(\lambda_i\mathbf{q}_i\mathbf{q}_i^T=(-\lambda_i)(-\mathbf{q}_i)\mathbf{q}_i^T\), com \(-\lambda_i=|\lambda_i|=\sigma_i>0\) — ou seja, para manter \(\sigma_i\ge 0\) (exigido na definição de valor singular), é preciso inverter o sinal de exatamente um dos dois vetores (\(\mathbf{u}_i\) ou \(\mathbf{v}_i\), não ambos) em relação ao autovetor \(\mathbf{q}_i\) original. É precisamente por isso que o item (a) é falso em geral.
- ✔ Verdadeiro — Matrizes de covariância nunca têm autovalor negativo — logo caem exatamente na condição do item (a): \(U=V=Q\), \(\Sigma=\Lambda\) diretamente, sem nenhum ajuste de sinal necessário.
- ✗ Falso — A relação de continência é exatamente o oposto do que o item afirma: a SVD existe para qualquer matriz, quadrada ou não, simétrica ou não — é a decomposição espectral que é o caso restrito, exigindo simetria (ou, mais geralmente, diagonalizabilidade com autovalores reais). É a decomposição espectral que é um caso particular da SVD (quando \(A\) é simétrica semidefinida positiva), não o contrário.
Dica(Resposta) Teste 8 — A SVD aplicada a \(X\): posto e número de condição
- ✔ Verdadeiro — Uma cópia escalada de uma coluna já existente é, por definição, uma combinação linear das colunas de \(X\) — o posto de \(X'\) permanece \(4\) (o mesmo de \(X\)), mesmo com \(5\) colunas. Como o número de valores singulares não-nulos é igual ao posto, o \(5^o\) valor singular de \(X'\) é exatamente zero — o mesmo fenômeno de multicolinearidade exata visto anteriormente nesta disciplina, agora visto pela lente dos valores singulares.
- ✗ Falso — Os valores singulares dependem da matriz inteira, não são invariantes a reescala de uma única coluna — multiplicar uma coluna por \(1000\) muda \(X^TX\) (e, portanto, seus autovalores/valores singulares associados) de forma substancial. É o mesmo aviso de que a covariância bruta (sem padronizar) é dominada pela escala numérica das variáveis, não pela estrutura de correlação — o mesmo aviso se aplica aqui.
- ✔ Verdadeiro — Essa relação é uma consequência algébrica direta de \(\sigma_i(X)^2=\lambda_i(X^TX)\) (ver Convenções) — vale para qualquer matriz real de posto completo, não é uma propriedade específica do California Housing.
- ✗ Falso — Confunde dimensões: \(\mathbf{u}_1\in\mathbb{R}^{16\,640}\) (o codomínio de \(X\), um vetor por observação), enquanto o autovetor principal de \(X^TX\) é \(\mathbf{v}_1\in\mathbb{R}^4\) (o domínio de \(X\), um vetor por atributo) — os dois vivem em espaços de dimensões completamente diferentes, não podem ser “iguais” em nenhum sentido. A identidade \(\sigma_i(X)^2=\lambda_i(X^TX)\) relaciona apenas os valores (escalares), não os vetores.
Dica(Resposta) Teste 9 — Filtragem colaborativa e interpretação de perfis latentes
- ✔ Verdadeiro — Verificado numericamente: a matriz original (posto \(3\), ver Convenções) ganha uma quarta coluna \((5,5,5,5)^T\); essa coluna não está no espaço-coluna gerado pelas outras três (resíduo de mínimos quadrados \(\approx 0{,}577\), não-nulo), então o posto sobe para \(4\) e aparece um quarto valor singular não-nulo (\(\approx 0{,}362\), pequeno, mas não-zero). O fato de a nota ser “uniforme” (não distinguir gêneros) não implica ser uma combinação linear exata dos perfis já existentes — uniformidade e redundância linear são propriedades diferentes.
- ✔ Verdadeiro — Com \(k=1\), \(\hat{A}^{(1)}=\sigma_1\mathbf{u}_1\mathbf{v}_1^T\) — cada coluna (espectador) é um múltiplo escalar do mesmo vetor \(\mathbf{u}_1\) (o “filme estereotípico” de ficção científica). Isso significa que a proporção relativa entre as notas previstas para os diferentes filmes é idêntica para todo espectador (só a magnitude geral, dada por \(\mathbf{v}_1\), muda) — a razão entre as notas de “Guerra nas Estrelas” e “Blade Runner” em \(\hat{A}^{(1)}\) é a mesma para Ali, Beatrix e Chandra, mesmo Chandra não gostando de ficção científica.
- ✔ Verdadeiro — A matemática da aproximação de baixo posto não depende de a matriz representar filmes, músicas ou qualquer outro item — a mesma interpretação de “perfis estereotípicos” (à esquerda) e “gostos estereotípicos” (à direita) se aplica a qualquer matriz de avaliações usuário \(\times\) item.
- ✔ Verdadeiro — Este item, apesar de nascer de uma tentativa de “falsa dicotomia”, é na verdade um alerta epistemológico correto — vale a pena registrar como tal. A leitura de “temas”/“perfis” depende de suposições explícitas (“todos os espectadores avaliam filmes de forma consistente, usando o mesmo mapeamento linear”; “não há erro ou ruído nas notas”) — a SVD em si é só álgebra linear exata; a interpretação de “temas”/“perfis” é uma leitura semântica sobreposta aos números, condicionada a essas suposições serem razoáveis para os dados em questão, não uma consequência matemática automática da decomposição.