[線代] SVD理論算法問題(線代啟示錄)

[znmkhxrw (QQ)]

請教一下看過【周老師-線代啟示錄】網站的板友以下一個問題

在《 https://goo.gl/kURGDq PCA & SVD 》這個連結裡他提到：

在數值計算上，矩陣乘法運算可能因引進捨入或截斷誤差而造成破壞性的影響

因此 (X^t*X)/(n-1) 的正交譜分解(diagonized by an orthonormal basis)

用X的SVD算比較好

但是！ 點超連結去《 https://goo.gl/zw9KRe SVD 》看SVD的推導過程

要導出X的SVD的話就是要計算X^t*X的對角化...........

是我誤會了什麼嗎？


總之，感覺文意表達是：用X的SVD去避免硬幹X^t*X的正交對角化

但是，X的SVD就是要硬幹X^t*X的正交對角化才能得來


謝謝指教！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.242.52.37
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1526461573.A.E48.html
推 LiamIssac   : SVD的目的應該是要免除X是ill-conditioned的時候造
→ LiamIssac   : 成的numerical instability 跟正交化硬不硬幹沒有
→ LiamIssac   : 太大關係
推 arthurduh1  : 因為數值上算 SVD 不會用 X^t*X, 而是用其他方法
→ arthurduh1  : 比如分解 [0, X*; X, 0] 就是一個替代方案
→ arthurduh1  : 你可以參考一下 wiki 頁面的 numerical approach
@L大 @a大 意思是算SVD時會用數值逼近，不會去計算X^t*X的對角化

之後逼近出 X = UΣV^t 後就用 X = UΣV^t 去計算PCA


而周老師那樣寫，或許是因為《PCA & SVD》這篇是2013的 而《SVD》是2009的

年代差有點多，他所謂的用SVD算PCA的本意其實就是你們說的那樣

不然就會有我問的那個問題---不管怎樣都逃不了處理 X^t X 的對角化


謝謝回答!

推 arthurduh1  : 不知道你的「數值逼近」是什麼意思
→ arthurduh1  : 不過數值計算和我們一般在線代所走的路徑不太一樣
→ arthurduh1  : 我覺得他的文章「主要不是」從數值計算的角度出發
→ arthurduh1  : 他 SVD 那邊就單純只是走線代傳統的路, 並不代表
→ arthurduh1  : 數值計算上會採用這種方法.
→ arthurduh1  : 比如線代介紹的特徵值求法, 在數值計算上就不會用
→ arthurduh1  : 也是同樣的道理
推 LiamIssac   : 數值逼近的意思其實就是當X ill conditioned的時候
→ LiamIssac   :  XtX也會ill condition 然後計算反矩陣就會出現問題
→ LiamIssac   :  所以改用SVD把XtX轉換成linear transformation (si
→ LiamIssac   : ngular valuer就是係數 eigenvector做基底)來做逼
→ LiamIssac   : 近
推 arthurduh1  : 我的意思是「數值逼近」這個詞用在太多地方了
→ arthurduh1  : 重點是你用什麼方法做逼近.
我其實也不清楚數值逼近的方法QQ

主要問題脈絡就是為什麼他說 PCA 用 SVD 來算比較好，不要解X^t*X的對角化

原因應該就是如L大說的 當X ill conditioned時 XtX也會ill condition

聽起來很OK，但是點進去 SVD 的連結，他文章的算法卻是 解X^t*X的對角化

才讓我整個很困惑@@"

之後聽你們回說 SVD不一定要用X^t*X的對角化來算 可以用numerical approach

我才跟著說【數值逼近】這個詞


總之，如果我沒有誤會周老師的文意，那會是循環敘述，因為都避不開X^t*X的對角化

除非有其他計算方法可以找SVD (數值?)


P.S. 我用【循環敘述】而非【循環論證】是因為 每一個矩陣確實可以證明存在SVD

     只是實際上的計算要怎麼算出U,V罷了
※ 編輯: znmkhxrw (219.68.160.241), 05/16/2018 23:36:55
推 arthurduh1  : 就是有方法啊@@ wiki 那部分不是就有提供了?
→ arthurduh1  : 算 SVD 不一定要透過 X^t*X, 但是數學上在介紹、
→ arthurduh1  : 理解、證明性質時會透過 X^t*X. 所以你才會誤解了吧
→ arthurduh1  : 但事實上是他文章編排沒有很嚴謹、或者說容易造成
→ arthurduh1  : 誤會沒錯.
→ arthurduh1  : 或許他沒有專門從數值角度計算 SVD 的文章, 所以
→ arthurduh1  : 他才會退而求其次連結到 SVD 的介紹.
→ arthurduh1  : 就如同我上面說過的, 線代所介紹的特徵值
→ arthurduh1  : 「計算程序」, 並不會被用在數值計算上.
→ arthurduh1  : 你可以看這篇 https://goo.gl/6x8cw9 底下的留言
同意這整個脈絡！那我沒有誤會他意思了，謝謝你~~^^
※ 編輯: znmkhxrw (219.68.160.241), 05/17/2018 00:28:58