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

看板Math作者 (QQ)時間6年前 (2018/05/16 17:06), 6年前編輯推噓6(6推 0噓 24→)
留言30則, 2人參與, 6年前最新討論串1/1
請教一下看過【周老師-線代啟示錄】網站的板友以下一個問題 在《 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
推
05/16 19:57, 6年前 , 1F
SVD的目的應該是要免除X是ill-conditioned的時候造
05/16 19:57, 1F
→
05/16 19:57, 6年前 , 2F
成的numerical instability 跟正交化硬不硬幹沒有
05/16 19:57, 2F
→
05/16 19:57, 6年前 , 3F
太大關係
05/16 19:57, 3F
推
05/16 20:31, 6年前 , 4F
因為數值上算 SVD 不會用 X^t*X, 而是用其他方法
05/16 20:31, 4F
→
05/16 20:32, 6年前 , 5F
比如分解 [0, X*; X, 0] 就是一個替代方案
05/16 20:32, 5F
→
05/16 20:37, 6年前 , 6F
你可以參考一下 wiki 頁面的 numerical approach
05/16 20:37, 6F
@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 的對角化 謝謝回答!
推
05/16 23:01, 6年前 , 7F
不知道你的「數值逼近」是什麼意思
05/16 23:01, 7F
→
05/16 23:04, 6年前 , 8F
不過數值計算和我們一般在線代所走的路徑不太一樣
05/16 23:04, 8F
→
05/16 23:05, 6年前 , 9F
我覺得他的文章「主要不是」從數值計算的角度出發
05/16 23:05, 9F
→
05/16 23:07, 6年前 , 10F
他 SVD 那邊就單純只是走線代傳統的路, 並不代表
05/16 23:07, 10F
→
05/16 23:07, 6年前 , 11F
數值計算上會採用這種方法.
05/16 23:07, 11F
→
05/16 23:08, 6年前 , 12F
比如線代介紹的特徵值求法, 在數值計算上就不會用
05/16 23:08, 12F
→
05/16 23:09, 6年前 , 13F
也是同樣的道理
05/16 23:09, 13F
推
05/16 23:09, 6年前 , 14F
數值逼近的意思其實就是當X ill conditioned的時候
05/16 23:09, 14F
→
05/16 23:09, 6年前 , 15F
XtX也會ill condition 然後計算反矩陣就會出現問題
05/16 23:09, 15F
→
05/16 23:09, 6年前 , 16F
所以改用SVD把XtX轉換成linear transformation (si
05/16 23:09, 16F
→
05/16 23:09, 6年前 , 17F
ngular valuer就是係數 eigenvector做基底)來做逼
05/16 23:09, 17F
→
05/16 23:09, 6年前 , 18F
近
05/16 23:09, 18F
推
05/16 23:17, 6年前 , 19F
我的意思是「數值逼近」這個詞用在太多地方了
05/16 23:17, 19F
→
05/16 23:17, 6年前 , 20F
重點是你用什麼方法做逼近.
05/16 23:17, 20F
我其實也不清楚數值逼近的方法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
推
05/16 23:40, 6年前 , 21F
就是有方法啊@@ wiki 那部分不是就有提供了?
05/16 23:40, 21F
→
05/16 23:41, 6年前 , 22F
算 SVD 不一定要透過 X^t*X, 但是數學上在介紹、
05/16 23:41, 22F
→
05/16 23:41, 6年前 , 23F
理解、證明性質時會透過 X^t*X. 所以你才會誤解了吧
05/16 23:41, 23F
→
05/16 23:42, 6年前 , 24F
但事實上是他文章編排沒有很嚴謹、或者說容易造成
05/16 23:42, 24F
→
05/16 23:42, 6年前 , 25F
誤會沒錯.
05/16 23:42, 25F
→
05/16 23:45, 6年前 , 26F
或許他沒有專門從數值角度計算 SVD 的文章, 所以
05/16 23:45, 26F
→
05/16 23:45, 6年前 , 27F
他才會退而求其次連結到 SVD 的介紹.
05/16 23:45, 27F
→
05/16 23:47, 6年前 , 28F
就如同我上面說過的, 線代所介紹的特徵值
05/16 23:47, 28F
→
05/16 23:47, 6年前 , 29F
「計算程序」, 並不會被用在數值計算上.
05/16 23:47, 29F
→
05/16 23:49, 6年前 , 30F
你可以看這篇 https://goo.gl/6x8cw9 底下的留言
05/16 23:49, 30F
同意這整個脈絡！那我沒有誤會他意思了，謝謝你~~^^ ※ 編輯: znmkhxrw (219.68.160.241), 05/17/2018 00:28:58
‣ 更多 znmkhxrw 的文章
文章代碼(AID): #1Q-_I5v8 (Math)