矩陣奇異值分解在最小二乘法中的應用
2011-12-31 00:00:00嚴雯
大觀周刊 2011年48期
中圖分類號：O151.21 文獻標識碼：A文章編號：1008-925X(2011)12-0135-02
摘要：總結了奇異值分解矩陣的降維、比例不變性、奇異值對矩陣的擾動不敏感等六個特征，并應用于最小二乘法問題中，列舉了矩陣滿秩情形，齊次方程組和帶約束方程組的最小二乘解。
關鍵詞：矩陣 奇異值分解 降維
1 引言
奇異值分解（SVD）是一種正交矩陣分解法；SVD是最可靠的分解法，但是它的計算時間幾乎十倍于QR分解；使用奇異值分解，不僅可以挖掘矩陣中隱藏的重要結構信息，從而發現局部與整體之間潛在的重要關聯模式，而且，更為重要的是，它可以降低矩陣的維數。以下將討論矩陣的奇異值分解在最小二乘問題中的應用。
1 奇異值分解在LS問題中的應用
LS問題即相當于，設A∈Rm×n（m>n），b∈Rm，求x∈Rn使得
‖Ax-b‖=min{‖Av-b‖2∶v∈Rn}
假設已知矩陣A有式子得到的SVD分解式為U∑VT ，U和V分別為m，n階正交方陣，而∑為和A具有相同維數的對角矩陣，那么我們可以得到:
Ax-b=U∑VTx-b
=U(∑VTx)-U(UTb)
=U(∑y-c)
因為U是一正交矩陣，所以‖Ax-b‖2=‖U(∑y-c) ‖2=‖∑y-c‖2，從而把原最小二乘法問題化為求使‖∑y-c ‖2最小的y這一最小二乘法問題，因為∑為對角矩陣，所以使得新的這一最小二乘法問題簡單的多，接著將對此仔細分析。
假設矩陣A的秩為r，則有：
∑y=σ1y1Mσryr00M0， ∑y-c=σ1y1-c1Mσryr-cr-cr+1-cr+2M-cm
可知y1=c1/σ1，(i=1，2，L，r)使得∑y-c達到它的最小長度［∑mi=r+1c21］1/2 ，并且可見當r=m時，上面的這一長度為0，也就是當矩陣A的列張成空間時最小二乘法問題可以無誤差地求解。而當r 我們將對∑轉置并且對非零的對角元素求逆所得到得矩陣定義為∑+，那么y=∑+c的前r個元素將等于ci/σi，(i=1，2，L r)，并且其余的元素為0，并且由y=VTx，c=UTb，容易得到： x=V∑+UTb 由此得到的是LS問題的最小范數解。 2 最小二乘法問題（滿秩情形） 現在考慮m≥n并且A的秩為n的情形。如果方程組不存在解，但是在許多情形下，找一個最接近于方程組的向量x仍然是有意義的。換句話說，尋求一個向量x使‖Ax-b‖最小，其中‖ ‖表示歐式范數。這時，x稱為該超定方程組的最小二乘解。用SVD能很方便地求最小二乘解，其方法如下所述。 尋求使‖Ax-b‖=‖U∑VT-b‖的最小值的向量x。利用正交矩陣的保范性，有‖U∑VT-b‖=‖∑VTx-UTb‖記y=VTx和b′=UTb，問題變成求‖∑y-b′‖的最小化問題，其中∑為m×n矩陣并且對角線以外的元素為零。 這方程組的形式是 d1 d2Odn0 y1y2Myn=b′1b′2Mb′nb′n+1Mb′m 顯然，離b′最近∑y的是向量(b′1，b′2，L ，b′n，0，L 0)T，并令y1=b′i/di(i=1，2，L ，n)得到。注意假定A的秩為n保證了di≠0。最后由x=Vy求出x，這里，給出了解的表達式。 3 齊次方程組的最小二乘解 與前一問題類似的問題是求形如Ax=0的方程組的非零解。注意到如果x是這方程組的一個解，那么對任何標量α，αx， 也是解，因此為了排除非零解，加入約束條件‖x‖=1是合理的。 這樣的方程組一般不存在精確解。假定A的維數是m×n，那么存在精確解的充要條件是rank（A） 問題1 在約束條件‖x‖=1的條件下，求使‖Ax‖最小的x。 注意到求‖Ax‖的最小值等價于求‖Ax‖2的最小值，而‖Ax‖2=xT(ATA)x，因此這個問題可以化為求對稱矩陣ATA的最小特征值問題，下面我們用來SVD求解這個問題： 設A=U∑VT，那么問題變成求‖U∑VTx‖的最小值。而‖U∑VTx‖=‖∑VTx‖和‖x‖=‖VTx‖。因此，問題變成在約束條件‖VTx‖=1下，求‖∑VTx‖的最小值。 令y=VTx，則問題簡化為： 問題1′ 在約束條件‖y‖=1下，求‖∑y‖的最小值。 現在，∑是對角元素按降序排列的一個對角矩陣。由此推出該問題的解是y=(0，0，L 0，1)，它的唯一非零元素1在最后的位置上（即為en ）。最后由x=Vy解出x，即x就是V的最后一列。V的最后一列實際上也是ATA的與最小特征值對應的特征向量。 4 帶約束方程組的最小二乘解 在一些應用場合，所求解的未知向量必須嚴格地滿足某些線性約束，這樣的約束可以用矩陣方程Cx=0來描述。要求它應準確地滿足，即沒有受到噪聲的干擾。這導出下列問題： 問題2 在約束‖x‖=1和Cx=0下，求使‖Ax‖最小的x。 類似于前一個問題的討論，這個問題可以看作是在約束Cx=0下，求ATA的最小特征值問題，利用SVD，它可以按如下方式來解： 滿足條件Cx=0意味著x垂直于C的每一行，因此所有這些x的集合形成一個向量空間，稱為C的行空間的正交補。現在考慮如何表示這個正交補空間。 設C∈Rp×n，如果C的行數少于列數，即p 這樣一來，上述最小化問題化為 問題2′ 在約束‖x′‖=1的條件下，求使‖AC⊥x′‖最小的x′。 這正是前面討論的問題，因此可以求解。 參考文獻 [1] 徐樹方.矩陣計算的理論與方法[M].北京：北京大學出版社，1995 [2] 周波，陳健.基于奇異值分解的、抗幾何失真的數字水印算法[J].中國圖象圖形學報，2004，9(4)
