Norma apa dari kesalahan rekonstruksi yang diminimalkan oleh matriks aproksimasi peringkat rendah yang diperoleh dengan PCA?

Jawaban:

30

Satu kata jawaban: Keduanya.


Mari kita mulai dengan mendefinisikan norma-norma. Untuk matriks X , operator 2 -norm didefinisikan sebagai dan norma Frobenius sebagaiXF=

X2=skamuhalXv2v2=mSebuahx(ssaya)
manasiadalah nilai singularX, yaitu elemen diagonalSdalam dekomposisi nilai singularX=USV.
XF=sayajXsayaj2=tr(XX)=ssaya2,
ssayaXSX=USV

PCA diberikan oleh dekomposisi nilai singular yang sama ketika data dipusatkan. merupakan komponen utama, V adalah sumbu utama, yaitu vektor eigen dari matriks kovarians, dan rekonstruksi X dengan hanya k komponen utama yang sesuai dengan k nilai tunggal terbesar diberikan oleh X k = U k S k V k .USVXkkXk=UkSkVk

The Eckart-Young teorema mengatakan bahwa adalah matriks meminimalkan norma kesalahan rekonstruksi X - Sebuah antara semua matriks A pangkat k . Ini berlaku untuk keduanya, norma Frobenius dan operator 2 -norm. Seperti yang ditunjukkan oleh @ cardinal dalam komentar, itu pertama kali dibuktikan oleh Schmidt (dari ketenaran Gram-Schmidt) pada tahun 1907 untuk kasus Frobenius. Itu kemudian ditemukan kembali oleh Eckart dan Young pada tahun 1936 dan sekarang sebagian besar dikaitkan dengan nama mereka. Mirsky menggeneralisasi teorema pada tahun 1958 untuk semua norma yang tidak berubah di bawah transformasi kesatuan, dan ini termasuk norma 2 operator.XkX-SEBUAHSEBUAHk2

Teorema ini kadang-kadang disebut teorema Eckart-Young-Mirsky. Stewart (1993) menyebutnya teorema aproksimasi Schmidt. Saya bahkan pernah melihatnya disebut teorema Schmidt-Eckart-Young-Mirsky.


Bukti untuk operator -norm2

Biarkan menjadi peringkat penuh n . Karena A adalah peringkat k , ruang nolnya memiliki dimensi n - k . Ruang yang direntang oleh k + 1 vektor X tunggal yang sesuai dengan nilai singular terbesar memiliki dimensi k + 1 . Jadi kedua ruang ini harus bersilangan. Biarkan w menjadi vektor satuan dari persimpangan. Kemudian kita mendapatkan: X - A 2 2( X - A ) w 2XnSEBUAHkn-kk+1Xk+1wQED.

X-SEBUAH22(X-SEBUAH)w22=Xw22=saya=1k+1ssaya2(vsayaw)2sk+12=X-Xk22,

Bukti untuk norma Frobenius

Kami ingin mencari matriks dari peringkat k yang meminimalkan X - A 2 F . Kita bisa pd A = B W , di mana W memiliki k ortonormal kolom. Meminimalkan X - B W 2 untuk tetap W adalah masalah regresi dengan solusi B = X W . Memasukkannya, kita melihat bahwa kita sekarang perlu meminimalkan X - X W W SEBUAHkXAF2A=BWWkXBW2WB=XW mana Σ adalah matriks kovarian X , yaitu Σ = X X / ( n - 1 ) . Berarti bahwa kesalahan rekonstruksi ini diminimalkan dengan mengambil sebagai kolom W beberapa k ortonormal vektor memaksimalkan total varian dari proyeksi.

XXWW2=X2XWW2=consttr(WWXXWW)=constconsttr(WΣW),
ΣXΣ=XX/(n1)Wk

kX=USVΣ=VS2V/(n1)=VΛVR=VW

tr(WΣW)=tr(RΛR)=iλijRij2i=1kλk,
with maximum achieved when W=Vk. The theorem then follows immediately.

See the following three related threads:


Earlier attempt of a proof for Frobenius norm

This proof I found somewhere online but it is wrong (contains a gap), as explained by @cardinal in the comments.

Frobenius norm is invariant under unitary transformations, because they do not change the singular values. So we get:

XAF=USVA=SUAV=SB,
where B=UAV. Continuing:
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
sumber
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