Qual norma do erro de reconstrução é minimizada pela matriz de aproximação de baixa classificação obtida com o PCA?

Respostas:

30

Resposta em uma única palavra: Ambos.


Vamos começar definindo as normas. Para uma matriz , o operador 2 -norm é definido como " X " 2 = s u p " X v " 2X2e norma Frobenius comoXF=

X2=supXv2v2=max(si)
ondesisão valores singulares deX, ou seja, os elementos da diagonal deSna decomposição de valor singularX=LSV.
XF=ijXij2=tr(XX)=si2,
siXSX=USV

O PCA é fornecido pela mesma decomposição de valor singular quando os dados são centralizados. são componentes principais, V são eixos principais, ou seja, autovetores da matriz de covariância, e a reconstrução de X com apenas os k componentes principais correspondentes aos k maiores valores singulares é dada por X k = U k S k V k .USVXkkXk=UkSkVk

O teorema de Eckart-Young diz que é a matriz que minimiza a norma do erro de reconstrução " X - A " entre todas as matrizes A da classificação k . Isso é verdade tanto para a norma Frobenius quanto para o operador 2XkXAAk2 -norm. Como apontado por @cardinal nos comentários, foi provado por Schmidt (da fama de Gram-Schmidt) em 1907 para o caso Frobenius. Mais tarde foi redescoberto por Eckart e Young em 1936 e agora está associado principalmente a seus nomes. Mirsky generalizou o teorema em 1958 a todas as normas que são invariantes sob transformações unitárias, e isso inclui o operador 2-norma.

Esse teorema às vezes é chamado de teorema de Eckart-Young-Mirsky. Stewart (1993) o chama de teorema da aproximação de Schmidt. Eu já o vi chamado teorema de Schmidt-Eckart-Young-Mirsky.


Prova para o operador -norm2

Seja de posição completa n . Como A é da classificação k , seu espaço nulo tem n - k dimensões. O espaço medido pelos k + 1 vetores singulares à direita de X correspondentes aos maiores valores singulares possui k + 1 dimensões. Portanto, esses dois espaços devem se cruzar. Seja w um vetor unitário da interseção. Em seguida, obtemos: " X - A " 2 2" ( X - A ) w " 2XnAknkk+1Xk+1wQED.

XA22(XA)w22=Xw22=i=1k+1si2(viw)2sk+12=XXk22,

Prova da norma Frobenius

Queremos encontrar matriz de classificação k que minimiza X - A 2 F . Podemos fatorar A = B W , onde W tem k colunas ortonormais. Minimizando X - B W 2 para fixa W é um problema de regressão com solução B = X W . Ligá-lo, vemos que precisamos agora para minimizar X - X W W AkXAF2A=BWWkXBW2WB=XW onde Σ é a matriz de covariância de X , ou seja, Σ = X X / ( n - 1 ) . Isso significa que o erro de reconstrução é minimizado tomando como colunas de W alguns k

XXWW2=X2XWW2=consttr(WWXXWW)=constconsttr(WΣW),
ΣXΣ=XX/(n1)Wk ortonormal vectores maximizar a variância total da projecção.

É sabido que estes são os primeiros vetores da matriz de covariância. De fato, se X = U S V , então Σ = V S 2 V / ( n - 1 ) = V Λ V . Escrita R = V W que também tem colunas ortonormais, obtemos t R ( W Σ W ) = t r ( R Ganhe muitos RkX=USVΣ=VS2V/(n1)=VΛVR=VW

tr(WΣW)=tr(RΛR)=iλijRij2i=1kλk,
W=Vk . O teorema segue imediatamente.

Consulte os três segmentos relacionados a seguir:


Tentativa anterior de uma prova da norma Frobenius

Esta prova eu ​​encontrei em algum lugar online, mas está errado (contém uma lacuna), conforme explicado por @cardinal nos comentários.

XAF=USVA=SUAV=SB,
B=UAV
XAF=ij(SijBij)2=i(siBii)2+ijBij2.
This is minimized when all off-diagonal elements of B are zero and all k diagonal terms cancel out the k largest singular values si [gap here: this is not obvious], i.e. Boptimal=Sk and hence Aoptimal=UkSkVk.
amoeba says Reinstate Monica
fonte
2
The proof in the case of the Frobeniius norm is not correct (or at least complete) since the argument here does not preclude the possibility that a matrix of the same rank could cancel out some of the other diagonal terms while having "small" off-diagonals. To see the gap more clearly note that holding the diagonals constant and "zeroing" the off-diagonals can often increase the rank of the matrix in question!
cardinal
1
Note also that the SVD was known to Beltrami (at least in a quite general, though special case) and Jordan as early as 1874.
cardinal
@cardinal: Hmmmm, I am not sure I see the gap. If B cancels out some other diagonal terms in S instead of k largest ones and has some nonzero off-diagonal terms instead, then both sums, i(siBii)2 and ijBij2, are going to increase. So it will only increase the reconstruction error. No? Still, I tried to find another proof for Frobenius norm in the literature, and have read that it should somehow follow easily from the operator norm case. But so far I don't see how it should follow...
amoeba says Reinstate Monica
3
I do like G. W. Stewart (1993), On the early history of the singular value decomposition, SIAM Review, vol. 35, no. 4, 551-566 and, given your prior demonstrated interest in historical matters, I think you will too. Unfortunately, I think Stewart is unintentionally overly dismissive of the elegance of Schmidt's 1907 proof. Hidden within it is a regression interpretation that Stewart overlooks and which is really quite pretty. There is another proof that follows the initial diagonalization approach you take, but which requires some extra work to fill the gap. (cont.)
cardinal
2
@cardinal: Yes, you are right, now I see the gap too. Thanks a lot for the Stewart paper, that was a very interesting read. I see that Stewart presents Schmidt's and Weyl's proofs, but both of them look more complicated than what I would like to copy here (and so far I have not had the time to study them carefully). I am surprised: I expected this to be a very simple result, but it seems it is less trivial than I thought. In particular, I would not have expected that the Frobenius case is so much more complicated than the operator norm one. I will edit the post now. Happy New Year!
amoeba says Reinstate Monica