矩陣奇異值分解在最小二乘法中的應(yīng)用

中圖分類號：O151.21 文獻(xiàn)標(biāo)識碼：A文章編號：1008-925X(2011)12-0135-02

摘要：總結(jié)了奇異值分解矩陣的降維、比例不變性、奇異值對矩陣的擾動不敏感等六個特征，并應(yīng)用于最小二乘法問題中，列舉了矩陣滿秩情形，齊次方程組和帶約束方程組的最小二乘解。

關(guān)鍵詞：矩陣 奇異值分解 降維

1 引言

奇異值分解（SVD）是一種正交矩陣分解法；SVD是最可靠的分解法，但是它的計(jì)算時間幾乎十倍于QR分解；使用奇異值分解，不僅可以挖掘矩陣中隱藏的重要結(jié)構(gòu)信息，從而發(fā)現(xiàn)局部與整體之間潛在的重要關(guān)聯(lián)模式，而且，更為重要的是，它可以降低矩陣的維數(shù)。以下將討論矩陣的奇異值分解在最小二乘問題中的應(yīng)用。

1 奇異值分解在LS問題中的應(yīng)用

LS問題即相當(dāng)于，設(shè)A∈Rm×n（m>n），b∈Rm，求x∈Rn使得

‖Ax-b‖=min{‖Av-b‖2∶v∈Rn}

假設(shè)已知矩陣A有式子得到的SVD分解式為U∑VT ，U和V分別為m，n階正交方陣，而∑為和A具有相同維數(shù)的對角矩陣，那么我們可以得到: 

Ax-b=U∑VTx-b

=U(∑VTx)-U(UTb)

=U(∑y-c) 

因?yàn)閁是一正交矩陣，所以‖Ax-b‖2=‖U(∑y-c) ‖2=‖∑y-c‖2，從而把原最小二乘法問題化為求使‖∑y-c ‖2最小的y這一最小二乘法問題，因?yàn)椤茷閷蔷仃嚕允沟眯碌倪@一最小二乘法問題簡單的多，接著將對此仔細(xì)分析。 

假設(shè)矩陣A的秩為r，則有：

∑y=σ1y1Mσryr00M0， ∑y-c=σ1y1-c1Mσryr-cr-cr+1-cr+2M-cm

可知y1=c1/σ1，(i=1，2，L，r)使得∑y-c達(dá)到它的最小長度［∑mi=r+1c21］1/2 ，并且可見當(dāng)r=m時，上面的這一長度為0，也就是當(dāng)矩陣A的列張成空間時最小二乘法問題可以無誤差地求解。而當(dāng)r

我們將對∑轉(zhuǎn)置并且對非零的對角元素求逆所得到得矩陣定義為∑+，那么y=∑+c的前r個元素將等于ci/σi，(i=1，2，L r)，并且其余的元素為0，并且由y=VTx，c=UTb，容易得到：

x=V∑+UTb

由此得到的是LS問題的最小范數(shù)解。

2 最小二乘法問題（滿秩情形）

現(xiàn)在考慮m≥n并且A的秩為n的情形。如果方程組不存在解，但是在許多情形下，找一個最接近于方程組的向量x仍然是有意義的。換句話說，尋求一個向量x使‖Ax-b‖最小，其中‖ ‖表示歐式范數(shù)。這時，x稱為該超定方程組的最小二乘解。用SVD能很方便地求最小二乘解，其方法如下所述。

尋求使‖Ax-b‖=‖U∑VT-b‖的最小值的向量x。利用正交矩陣的保范性，有‖U∑VT-b‖=‖∑VTx-UTb‖記y=VTx和b′=UTb，問題變成求‖∑y-b′‖的最小化問題，其中∑為m×n矩陣并且對角線以外的元素為零。 這方程組的形式是

d1 d2Odn0 y1y2Myn=b′1b′2Mb′nb′n+1Mb′m

顯然，離b′最近∑y的是向量(b′1，b′2，L ，b′n，0，L 0)T，并令y1=b′i/di(i=1，2，L ，n)得到。注意假定A的秩為n保證了di≠0。最后由x=Vy求出x，這里，給出了解的表達(dá)式。

3 齊次方程組的最小二乘解

與前一問題類似的問題是求形如Ax=0的方程組的非零解。注意到如果x是這方程組的一個解，那么對任何標(biāo)量α，αx， 也是解，因此為了排除非零解，加入約束條件‖x‖=1是合理的。

這樣的方程組一般不存在精確解。假定A的維數(shù)是m×n，那么存在精確解的充要條件是rank（A）

問題1 在約束條件‖x‖=1的條件下，求使‖Ax‖最小的x。

注意到求‖Ax‖的最小值等價(jià)于求‖Ax‖2的最小值，而‖Ax‖2=xT(ATA)x，因此這個問題可以化為求對稱矩陣ATA的最小特征值問題，下面我們用來SVD求解這個問題：

設(shè)A=U∑VT，那么問題變成求‖U∑VTx‖的最小值。而‖U∑VTx‖=‖∑VTx‖和‖x‖=‖VTx‖。因此，問題變成在約束條件‖VTx‖=1下，求‖∑VTx‖的最小值。 令y=VTx，則問題簡化為：

問題1′ 在約束條件‖y‖=1下，求‖∑y‖的最小值。

現(xiàn)在，∑是對角元素按降序排列的一個對角矩陣。由此推出該問題的解是y=(0，0，L 0，1)，它的唯一非零元素1在最后的位置上（即為en ）。最后由x=Vy解出x，即x就是V的最后一列。V的最后一列實(shí)際上也是ATA的與最小特征值對應(yīng)的特征向量。

4 帶約束方程組的最小二乘解

在一些應(yīng)用場合，所求解的未知向量必須嚴(yán)格地滿足某些線性約束，這樣的約束可以用矩陣方程Cx=0來描述。要求它應(yīng)準(zhǔn)確地滿足，即沒有受到噪聲的干擾。這導(dǎo)出下列問題：

問題2 在約束‖x‖=1和Cx=0下，求使‖Ax‖最小的x。

類似于前一個問題的討論，這個問題可以看作是在約束Cx=0下，求ATA的最小特征值問題，利用SVD，它可以按如下方式來解：

滿足條件Cx=0意味著x垂直于C的每一行，因此所有這些x的集合形成一個向量空間，稱為C的行空間的正交補(bǔ)。現(xiàn)在考慮如何表示這個正交補(bǔ)空間。

設(shè)C∈Rp×n，如果C的行數(shù)少于列數(shù)，即p

這樣一來，上述最小化問題化為

問題2′ 在約束‖x′‖=1的條件下，求使‖AC⊥x′‖最小的x′。

這正是前面討論的問題，因此可以求解。

參考文獻(xiàn)

[1] 徐樹方.矩陣計(jì)算的理論與方法[M].北京：北京大學(xué)出版社，1995

[2] 周波，陳健.基于奇異值分解的、抗幾何失真的數(shù)字水印算法[J].中國圖象圖形學(xué)報(bào)，2004，9(4)