Eu li sobre decomposição de valor singular (SVD). Em quase todos os livros didáticos, é mencionado que ela fatoriza a matriz em três matrizes com determinada especificação.
Mas qual é a intuição por trás da divisão da matriz dessa forma? O PCA e outros algoritmos para redução de dimensionalidade são intuitivos no sentido de que o algoritmo possui uma boa propriedade de visualização, mas com SVD não é o caso.
matrix
linear-algebra
svd
intuition
SHASHANK GUPTA
fonte
fonte
Respostas:
Escreva o SVD da matriz (real, n × p ) como X = U D V T onde U é n × p , D é diagonal p × p e V T é p × p . Em termos das colunas das matrizes U e V , podemos escrever X = ∑ p i = 1 d i u i v T iX n×p
Pense agora em como contendo os valores em escala de cinza de uma imagem em preto e branco, cada entrada na matriz representando um pixel. Por exemplo, a seguinte imagem de um babuíno:X
Em seguida, leia esta imagem no R e obtenha a parte da matriz da estrutura resultante, talvez usando a biblioteca
pixmap
.Se você deseja um guia passo a passo de como reproduzir os resultados, pode encontrar o código aqui .
Calcule o SVD:
resultando nas duas imagens a seguir:
À esquerda, podemos ver facilmente as listras verticais / horizontais na imagem de classificação 1.
O que é bastante interessante: vemos as partes da imagem original que são difíceis de representar como superposição de linhas verticais / horizontais, principalmente pêlos do nariz na diagonal e alguma textura e os olhos!
fonte
Seja (então quantifica a potência explosiva de na direção ). Suponha que os vetores unitários sejam definidos de forma que As equações (2) podem ser expressas de forma concisa usando a notação da matriz como onde é a matriz cuja coluna é , é a matriz cuja a coluna é eσi=∥Avi∥2 σi A vi ui Avi=σiuifor i=1,…,n.(2) AV=UΣ,(3) V n×n i vi U m×n i ui Σ é o matriz diagonal cuja th entrada diagonal é . A matriz é ortogonal, então podemos multiplicar os dois lados de (3) por para obter
Pode parecer que agora derivamos o SVD de com quase zero esforço. Até agora, nenhuma das etapas foi difícil. No entanto, falta uma parte crucial da imagem - ainda não sabemos que é ortogonal.n×n i σi V VT A=UΣVT. A U
Aqui está o fato crucial, a peça que faltava: acontece que é ortogonal a : Eu afirmo que se isso não fosse verdade, então não seria o ideal para o problema (1). De fato, se (4) não fosse satisfeito, seria possível melhorar perturbando-o um pouco na direção .Av1 Av2 ⟨Av1,Av2⟩=0.(4) v1 v1 v2
Suponha (por uma contradição) que (4) não seja satisfeito. Se estiver ligeiramente perturbado na direção ortogonal , a norma de não será alterada (ou, pelo menos, a alteração na norma de será desprezível). Quando eu ando na superfície da terra, minha distância do centro da terra não muda. No entanto, quando é perturbado na direção , o vetor é perturbado na direção não ortogonal e, portanto, a alteração na norma de não é desprezível . A norma dev1 v2 v1 v1 v1 v2 Av1 Av2 Av1 Av1 pode ser aumentado em uma quantidade não desprezível. Isso significa que não é ideal para o problema (1), que é uma contradição. Adoro esse argumento porque: 1) a intuição é muito clara; 2) a intuição pode ser convertida diretamente em uma prova rigorosa.v1
Um argumento semelhante mostra que é ortogonal a e e assim por diante. Os vetores são ortogonais aos pares. Isso significa que os vetores unitários podem ser escolhidos para serem ortogonais em pares, o que significa que a matriz acima é uma matriz ortogonal. Isso completa nossa descoberta do SVD.Av3 Av1 Av2 Av1,…,Avn u1,…,un U
Para converter o argumento intuitivo acima em uma prova rigorosa, devemos confrontar o fato de que se é perturbado na direção , o vetor perturbado não é verdadeiramente um vetor unitário. (Sua norma é .) Para obter uma prova rigorosa, defina O vetor é realmente um vetor de unidade. Mas, como você pode mostrar facilmente, se (4) não for satisfeito, então, para valores suficientemente pequenos de , temos (assumindo que o sinal dev1 v2 v~1=v1+ϵv2 1+ϵ2−−−−−√ v¯1(ϵ)=1−ϵ2−−−−−√v1+ϵv2. v¯1(ϵ) ϵ f(ϵ)=∥Av¯1(ϵ)∥22>∥Av1∥22 ϵ é escolhido corretamente). Para mostrar isso, basta verificar se . Isso significa que não é ideal para o problema (1), que é uma contradição.f′(0)≠0 v1
(A propósito, eu recomendo a leitura da explicação de Qiaochu Yuan sobre o SVD aqui . Em particular, dê uma olhada no "Lema principal nº 1", que é o que discutimos acima. Como diz Qiaochu, o principal lema nº 1 é "o coração técnico de decomposição de valor singular ".)
fonte
Cara, tire uma hora do seu dia e assista a esta palestra: https://www.youtube.com/watch?v=EokL7E6o1AE
Esse cara é super direto, é importante não pular nada, porque tudo acaba junto no final. Mesmo que pareça um pouco lento no começo, ele está tentando identificar um ponto crítico, o que faz!
Vou resumir para você, em vez de apenas fornecer as três matrizes que todo mundo faz (porque isso estava me confundindo quando li outras descrições). De onde vêm essas matrizes e por que as configuramos assim? A palestra acertou em cheio! Toda matriz (sempre na história da eternidade) pode ser construída a partir de uma matriz base com as mesmas dimensões, depois girá-la e esticá-la (esse é o teorema fundamental da álgebra linear). Cada uma dessas três matrizes que as pessoas jogam representa uma matriz inicial (U), uma matriz de escala (sigma) e uma matriz de rotação (V).
A matriz de escala mostra quais vetores de rotação estão dominando, esses são chamados de valores singulares. A decomposição está resolvendo para U, sigma e V.
fonte