較低等級矩陣的計算

鑑於我有一個等級爲3的矩陣3x3 A。我想創建一個秩爲2的矩陣，它在$ {l} _ {2} $/Frobenius範數中與A最接近。我們稱這個矩陣爲F.較低等級矩陣的計算

很容易通過SVD實現，也就是說，如果$ A = US {V}^{H} $通過SVD分解$ F = U \ hat {S} {V}^{H} $。其中$ \ hat {S} $與最後一個奇異值爲零的$ S $相同。

現在的問題是，是否有一個計算強度較小的方法來創建F但使用SVD分解？

謝謝。

2012-02-07 Royi

如果您知道矩陣是第3級，那麼恰好3個Householder變換足以將nxm矩陣減少到3xm矩陣。現在可以很容易地將其轉換爲特徵值問題。計算特徵多項式。例如，考慮這個矩陣（我將使用MATLAB做的工作）：

>> A = rand(10,3); 
>> B = A*rand(3,6);

顯然，B排名爲3，但是如果你不相信我，等級確認要求。

>> rank(B) 
ans = 
    3 

>> size(B) 
ans = 
    10  6

所以B是一個10x6矩陣，等級爲3.SVD證實了這一點。

>> svd(B) 
ans = 
      6.95958965358531 
      1.05904552889497 
     0.505730235622534 
     7.37626877572817e-16 
     2.36322066654691e-16 
     1.06396598411356e-16

我覺得懶得寫Householder轉換。（我已經得到了一些代碼，但是...）所以我會用QR來幫助我。

>> [Q,R] = qr(B,0); 
>> C = Q(:,1:3)'*B 
C = 
    -2.0815 -1.7098 -3.7897 -1.6186 -3.6038 -3.0809 
    0.0000 0.91329 0.78347 0.44597 -0.072369 0.54196 
    0.0000 0.0000 -0.2285 -0.43721 -0.85949 -0.41072

這裏的乘法顯示了在三次Householder轉換後我們會看到什麼。看到它是我們所期望的上三角形。接下來，計算特徵多項式。我會在這裏象徵性地使用我自己的工具，但計算只是一點代數。

>> sympoly lambda 
>> det(C*C' - lambda*eye(3)) 
ans = 
    13.8942 + 66.9996*lambda + 49.8132*lambda^2 + lambda^3 

>> P = det(C*C' - lambda*eye(3)) 
P = 
    13.8942 - 66.9996*lambda + 49.8132*lambda^2 - lambda^3

P是什麼根源，所以C * C'的特徵值？

>> r = roots(P) 
r = 
     48.436 
     1.1216 
     0.25576

我們知道，特徵值必須是這裏的奇異值的平方，所以這裏一個很好的測試是看我們是否收回該SVD發現singlular值。所以再次擴大顯示格式，我們看到它做得很好。

>> sqrt(roots(P)) 
ans = 
      6.95958965358531 
      1.05904552889497 
     0.505730235622533

數學可以很有趣，當它工作。我們可以用這些信息做什麼？如果我知道一個特定的特徵值，我可以計算相應的特徵向量。從本質上講，我們需要解決的方程

(C*C' - eye(3)*r(3)) * X = 0

的線性3x3的均相體系同樣，我會在這裏偷懶找到沒有實際編寫任何代碼的解決方案。高斯消除會做到這一點。

>> V = null((C*C' - eye(3)*r(3))) 
V = 
     -0.171504758161731 
     -0.389921448437349 
     0.904736084157367

所以我們有V，C * C'的一個特徵向量。我們可以說服自己，這是由以下呼籲svd。

>> svd(C - V*(V'*C)) 
ans = 
      6.9595896535853 
      1.05904552889497 
     2.88098729108798e-16

因此，通過在方向V減去關C的分量，我們就得到一個秩2矩陣。

同樣，我們可以將V輸入原來的問題空間，並使用由B.

>> U = Q(:,1:3)*V; 
>> D = B - U*(U'*B);

的秩一更新改造矩陣B，我們原來的矩陣，什麼是d的秩？

>> svd(D) 
ans = 
      6.95958965358531 
      1.05904552889497 
     2.62044567948618e-15 
     3.18063391331806e-16 
     2.16520878207897e-16 
     1.56387805987859e-16 

>> rank(D) 
ans = 
    2

正如你所看到的，即使我做了很多數學的，叫SVD，QR，排名等，都多次，到最後，實際的計算相對簡單。我只需要...

3戶戶主改造。（存儲它們供以後使用請注意，Householder變換隻是對矩陣的一級更新。）
計算特徵多項式。
使用您最喜歡的方法計算三次多項式的最小根。
恢復相應的特徵向量。這裏高斯消除就足夠了。
使用我們原來所做的戶主變換將該特徵向量返回到原始空間。
矩陣的一級更新。

只要我們知道實際等級是3，所有這些計算步驟對於任何大小矩陣都是快速和高效的。甚至不值得關於這個主題的論文。

編輯：

既然問題已經修訂，使得矩陣本身只是大小3×3，計算更是微不足道。然而，我會留下帖子的第一部分，因爲它描述了一個完全有效的解決方案，用於排名爲3的任意大小的通用矩陣。

如果你的目標是殺死一個3x3矩陣的最後奇異值，那麼3x3上的svd看起來好像很有效。通過間接手段產生最後一個奇異值的精度也會有一些損失。例如，在此比較由svd計算的最小奇異值，然後使用特徵值。所以你可能會在這裏看到一些小錯誤，因爲形成A'* A會導致一些精確性。這種損失的程度可能將取決於A的條件數

>> A = rand(3); 
>> sqrt(eig(A'*A)) 
ans = 
     0.0138948003095069 
     0.080275195586312 
      1.50987693453097 
>> svd(A) 
ans = 
      1.50987693453097 
     0.0802751955863124 
     0.0138948003095054

但是，如果你真的想自己做的工作，你可以做到這一點。

直接從3x3矩陣A'* A計算特徵多項式。
計算該三次多項式的根。選擇最小的根。
生成相應的特徵向量。
對A進行排名第一更新，殺死A中位於該特徵向量方向的部分。

這是否比簡單調用svd更簡單或計算效率更低，然後進行一級更新？我不確定這是值得在3x3上的努力。一個3x3 svd真的是非常快速的計算。

來源

2012-02-07 18:56:12

我忘了提，A是一個3×3矩陣的等級3.我相應地編輯了這篇文章。它對你有什麼影響嗎？ – Royi 2012-02-08 12:00:54

您可能已經考慮過了，但如果A是正常的，則可以通過特徵值分解來計算SVD。這相當於求解特徵多項式，並且由於它是秩爲3的矩陣的3次多項式，根可以通過衆所周知的立方公式找到。

它也看起來像SVD一般必須可以簡化爲一個3級矩陣求解立方體，但我不記得讀過任何東西。一個快速谷歌轉身this piece of code，聲稱以這種方式解決等級3 SVD。不幸的是，沒有附帶的文件。如果使用這個代碼，用一個非正定矩陣測試它應該是一個很好的測試用例。

編輯：在二讀時，似乎作者也使用了特徵分解。可能對非PD矩陣不太好，但我想在這裏證明是錯誤的。

來源

2012-02-07 10:27:35 kkm

您可以使用功率迭代來找到對應於最大奇異值的奇異向量。一旦你有了，你可以使用功率迭代的修改版本來找到第二大奇異值的矢量;在每次迭代之後，您需要將部分解矢量的投影減去最大奇異值的矢量。

這是找到所有奇異向量的一種很差的方法，但應該對前兩種方法工作得很好。

來源

2012-02-07 17:56:02

較低等級矩陣的計算

回答

相關問題