thumb|right|280px|Visualização da SVD de uma matriz real bi-dimensional (shearing matrix) M. Primeiro, vê-se o círculo unitário em azul juntamente com os dois vetores unitários da base canônica. Também pode ser vista a ação de M, que distorce o círculo a uma elipse. A SVD decompõe M em três transformações simples: a rotação V*, a escala (esticamento) Σ juntamente com os eixos rotacionados e uma segunda rotação U. Os comprimentos σ1 e σ2 dos semi-eixos da elipse são os valores singulares de M.
Em álgebra linear, a decomposição em valores singulares ou singular value decomposition (SVD) é a fatoração de uma matriz real ou complexa, com diversas aplicações importantes em processamento de sinais e estatística.
Formalmente, a decomposição em valores singulares de uma matriz m×n real ou complexa M é uma fatoração ou fatorização na forma:
onde U é uma matriz unitária m×m real ou complexa, Σ é uma matriz retangular diagonal m×n com números reais não-negativos na diagonal, e V* (a conjugada transposta de V) é uma matriz unitária n×n real ou complexa. As entradas diagonais Σi,i de Σ são os chamados valores singulares de M. As m colunas de U e as n colunas de V são os chamados vetores singulares à esquerda e vetores singulares à direita de M, respetivamente.
A decomposição em valores singulares e a decomposição em autovalores são intimamente relacionadas. Mais especificamente: Os vetores singulares à esquerda de M são autovetores de Os vetores singulares à direita de M são autovetores de Os valores singulares não-nulos de M (ao longo da diagonal de Σ) são as raízes quadradas dos autovalores não-nulos de ou Dentre as aplicações que envolvem a SVD estão o cálculo da pseudoinversa, o ajuste (fitting) de dados por mínimos quadrados, aproximação de matrizes, e a determinação do posto, imagem e núcleo de uma matriz.
Enunciado do teorema
Suponha-se que M é uma matriz m×n cujas entradas vêm de um corpo de escalares K, que pode ser tanto o corpo de números reais ou o corpo de números complexos. Então existe uma fatorização da forma:
onde U é uma matriz unitária m×m sobre K, a matriz Σ é uma matriz diagonal m×n com números reais não-negativos na diagonal, e V*, uma matriz unitária n×n sobre K, denota a transposta conjugada de V. Tal fatorização é chamada de decomposição em valores singulares de M.
Os elementos diagonais de Σ são chamados de valores singulares de M. Uma convenção bastante comum é listar os valores singulares em ordem decrescente. Neste caso, a matriz diagonal Σ é determinada de forma única por M (mas as matrizes U e V não são).
Interpretações intuitivas Rotação, escala, rotação No caso especial porém comum no qual M é apenas uma matriz quadrada m×m com determinante positivo cujas entradas são meros números reais, então U, V*, e Σ são matrizes m×m também de números reais, Σ pode ser vista como uma matriz de escala, e U e V* podem ser vistas como matrizes de rotação.
Se as condições supracitadas são satisfeitas, a expressão pode ser interpretada intuitivamente como uma composição (ou sequência) de três transformações geométricas: uma rotação, uma escala, e outra rotação. A figura acima exemplifica como uma matriz de cisalhamento (shear matrix) pode ser descrita como tal sequência.
Valores singulares como semi-eixos de uma elipse ou elipsoide Como ilustrado na figura, os valores singulares podem ser interpretados como os semi-eixos de uma elipse em 2D. Este conceito pode ser generalizado para o Espaço euclidiano n-dimensional, com valores singulares de qualquer matriz quadrada nxn sendo vistos como os semi-eixos de um elipsoide n-dimensional. Veja abaixo para maiores detalhes.
U e V são bases ortonormais Como U e V* são unitárias, as colunas de cada uma formam um conjunto de vetores ortonormais, que podem ser tomados uma base. Pela definição de matriz unitária, o mesmo vale para suas conjugadas transpostas U* e V. Em suma, U, U*, V, e V* são bases ortonormais.
Exemplo Considere-se a matriz 4×5
A decomposição em valores singulares desta matriz é dada por
Note-se que contém apenas zeros fora da diagonal. Ademais, como as matrizes e são unitárias, multiplicando-se por suas respectivas conjugadas transpostas gera matrizes identidades, como mostrado a seguir. Nesse caso, como e são reais, cada uma delas é uma matriz ortogonal.
e
Deve-se notar que esta decomposição em valores singulares em particular não é única. Escolhendo-se tal que
é também uma decomposição válida em valores singulares.
Valores singulares, vetores singulares e sua relação com a SVD Um número real não-negativo σ é um valor singular para M se e somente se existem vetores unitários u em Km e v em Kn tal que
Os vetores u e v são chamados vetor singular à esquerda e vetor singular à direita para σ, respectivamente.
Em qualquer decomposição em valores singulares
os elementos diagonais de Σ são iguais aos valores singulares de M. As colunas de U e V são, respectivamente, vetores singulares à esquerda e à direita para os valores singulares correspondentes. Por consequência, o teorema acima implica que:
Uma matriz m × n M tem pelo menos um e no máximo p = min(m,n) valores singulares distintos.
É sempre possível encontrar uma base ortogonal U para Km consistindo dos vetores singulares à esquerda de M.
É sempre possível encontrar uma base ortogonal V para Kn consistindo dos vetores singulares à direita de M.
Um valor singular para o qual podemos encontrar dois vetores singulares à esquerda (ou direita) que sejam linearmente independentes é chamado degenerado.
Valores singulares não-degenerados têm sempre vetores singulares à esquerda e à direita únicos, a não ser pela multiplicação por um fator de fase único eiφ (para o caso real a não ser pelo sinal). Assim, se todos os valores singulares de M são não-degenerados e não-zero, então sua decomposição em valores singulares é única, a não ser por multiplicação de uma coluna de U por um fator de fase único e a multiplicação simultânea da coluna correspondente de V pelo mesmo fator unitário de fase.
Valores singulares degenerados têm, por definição, vários vetores singulares distintos. Ademais, se u1 e u2 são dois vetores singulares à esquerda ambos correspondendo ao valor singular σ, então qualquer combinação linear normalizada de dois vetores é também um vetor singular à esquerda correspondendo ao valor singular σ. Raciocínio análogo é válido para vetores singulares à direita. Por consequência, se M tem valores singulares degenerados, então sua decomposição em valores singulares não é única.
Aplicações da SVD Pseudo-inversa
A decomposição em valores singulares pode ser usada para calcular a pseudoinversa de uma matriz, a qual é útil como uma forma de resolver problemas de mínimos quadrados lineares. De fato, a pseudoinversa da matriz M com decomposição em valores singulares é
onde Σ+ é a pseudoinversa de Σ, a qual é formada substituindo-se todo elemento diagonal não-nulo por seu inverso e tomando-se a transposta da matriz resultante.
Solução de sistemas lineares homogêneos
Um conjunto de equações lineares homogêneas pode ser escrito como para uma matriz e vetor . Uma situação típica é quando é dada e quer-se determinar não-nulo que satisfaça a equação. Tal pertence ao núcleo de e é por vezes chamado de vetor nulo (à direita) de . pode ser caracterizado como um vetor singular à direita correspondendo a um valor singular de que seja zero. Isto significa que se é uma matriz quadrada e não tem nenhum valor singular nulo, então a equação tem não-nulo como solução. Também significa que se existem vários valores singulares nulos, qualquer combinação linear dos vetores singulares à direita é uma solução válida. Analogamente à definição de um vetor nulo (à direita), um não-nulo satisfazendo , com sendo a transposta conjugada de , é chamada de um vetor nulo à esquerda de .
Minimização de mínimos quadrados totais
Um problema de mínimos quadrados totais (total least squares) objetiva determinar o vetor que minimiza a norma de um vetor sob a restrição . Mostra-se que a solução é o vetor singular à direita de correspondendo ao menor valor singular.
Imagem, núcleo e posto
Outra aplicação da SVD é que a mesma representa explicitamente a imagem e o núcleo de uma matriz M. Os vetores singulares à direita que correspondem a valores singulares nulos de M geram o núcleo (kernel) de M. Por exemplo, o núcleo é gerado pelas últimas duas colunas de no exemplo acima. Os valores singulares à esquerda correspondendo aos valores singulares não-nulos de M geram a imagem de M. Assim, o posto de M é igual ao número de valores singulares não-nulos que é igual ao número de elementos não-diagonais em .
Em álgebra linear numérica os valores singulares podem ser usados para determinar o posto efetivo de uma matriz, já que erros de arredondamento podem levar a valores singulares pequenos porém não-nulos numa matriz de posto deficiente.
Aproximação por matriz de baixo posto Algumas aplicações práticas precisam resolver o problema de se aproximar uma matriz usando outra matriz de posto . Para o caso em que a aproximação é baseada na minimização da norma de Frobenius da diferença entre e sob a restrição de que , pode-se mostrar que a solução é dada pela SVD de :
onde é a mesma matriz que a não ser pelo fato de conter os maiores valores singulares (os outros valores singulares são substituídos por zero). Isso é conhecido como o teorema Eckart–Young, provado por tais autores em 1936 (apesar de ter-se descoberto mais tarde que já era conhecido por outros autores; veja ).
Modelos separáveis A SVD pode ser vista como a decomposição de uma matriz em uma soma ponderada e ordenada de matrizes separáveis. O termo 'separável' refere-se ao fato de uma matriz poder ser escrita como um produto externo de dois vetores , ou, em coordenadas, . Especificamente, a matriz M pode ser decomposta como:
Aqui, e são as i-ésimas colunas das matrizes SVD correspondentes, são os autovalores ordenados, e cada é separável. A SVD pode ser usada para encontrar a decomposição de um filtro de processamento de imagens em filtros separados verticais e horizontais. Note-se que o número de 's não-nulos é precisamente o posto da matriz.
Matriz ortogonal mais próxima
Pode-se utilizar a SVD de para determinar a matriz ortogonal mais próxima de . A proximidade é medida pela norma de Frobenius de . A solução é o produto .The Singular Value Decomposition in Symmetric (Lowdin) Orthogonalization and Data Compression Isso confere com a intuição já que uma matriz ortogonal deveria ter a decomposição onde é a matriz identidade, de forma que se então o produto se reduz a colocar 1's no lugar dos valores singulares.
Um problema similar, com aplicações fundamentais em visão computacional, robótica e :en:shape analysis, é o Problema de Procrustes Ortogonal (orthogonal Procrustes problem), que consiste em encontrar uma matriz ortogonal que mapeia o mais próximo possível de . Formalmente,
onde é a norma de Frobenius.
Este problema é equivalente ao de encontrar a matriz ortogonal mais próxima a uma dada matriz .
O Algoritmo de Kabsch O algoritmo de Kabsch (Kabsch algorithm), também conhecido como Wahba's problem, utiliza a SVD para calcular a rotação ótima (no sentido dos mínimos quadrados) que alinha um conjunto de pontos com um conjunto de pontos correspondentes. Isso tem aplicações para a comparação de estruturas moleculares e em problemas relacionados a modelos 3D em visão computacional e robótica.
Outros exemplos