矩陣的因子分解

第4章矩陣的因子分解〔MatrixFactorizationandDecomposition〕教學要求掌握矩陣的滿秩分解；掌握矩陣的三角分解；掌握矩陣的正交分解；掌握Schur定理和正規(guī)矩陣的定義；熟練掌握矩陣的奇異值分解；整理課件數(shù)據(jù)集中可能包含大量特征，維災難使得數(shù)據(jù)分析很困難，1.維歸約〔降維〕：利用舊屬性的線性組合得到新屬性，使得新屬性相互正交，捕獲到數(shù)據(jù)的最大變差〔PCA：主成分分析(principlecomponentsanalysis)和SVD〕2.選擇特征子集：嵌入〔決策樹分類其〕，過濾和包裝〔搜索，特征加權(quán)等〕〕整理課件

矩陣的各種分解在矩陣計算中也扮演相當重要的角色。由于變換即矩陣，所以各種分解從根本上看是各種變換，其目的是將矩陣變換成特殊的矩陣。整理課件

§4.2矩陣的滿秩分解滿秩分解定理：設(shè)為任意矩陣，那么存在使得A=BC,其中B為列滿秩矩陣,C為行滿秩矩陣.任一非〔行或列〕滿秩的非零矩陣可表示為一列滿秩矩陣和一行滿秩矩陣的積；B的列可取為A的列的任一極大線性無關(guān)組；C可取為其行為A的行所生成的空間的基,然后用定理確定矩陣B。應用于極小最小二乘解和極小范數(shù)最小二乘解的算法中。整理課件例1

求下面矩陣的滿秩分解解思路：對矩陣A實施初等行變換得簡化階梯形矩陣H〔階梯型的非零行的第一個非零元為1，其所在的列其它元素為0〕,取A的r個使H陣滿秩的列為B，將H全為零的行去掉后即可構(gòu)成行滿秩矩陣C。整理課件由此可知rank(A)=2，且該矩陣第一列、第三列是線性無關(guān)的。選取整理課件同樣，我們也可以選取

由上述例子可以看出矩陣的滿秩分解形式并不唯一。但是不同的分解形式之間有如下聯(lián)系：注：如果均為矩陣A

的滿秩分解，那么存在矩陣滿足整理課件那么稱其為A的LU分解或三角分解?！?.3矩陣的三角分解定義1

如果方陣A可以分解成一個單位下三角矩陣L與一個上三角矩陣U的乘積整理課件初等下三角矩陣整理課件初等下三角矩陣性質(zhì)(1)det(Li)=1,整理課件(2)用初等下三角矩陣左乘矩陣A，等于將A的第i行依次乘以-li+1i,…,-lni分別加到第i+1行到第n行上去。(3)設(shè)A=(aij)n

n,且ajj0，并且取

那么LiA在(i+1,j),(i+2,j)…(n,j)的位置上為0整理課件(4)整理課件定理1(LU分解定理)設(shè)A是n階非奇異矩陣，那么存在唯一的單位下三角矩陣L〔主對角線上元素全為1的下三角矩陣〕與唯一的上三角矩陣U，使得的充要條件是A的所有順序主子式均非零，即矩陣的LU分解也稱為Doolitte分解假設(shè)L為下三角矩陣,U為單位上三角矩陣,稱為Crout分解。整理課件定理2(LDU分解定理)設(shè)A是n階非奇異矩陣，那么存在唯一的單位下三角矩陣L，對角矩陣D=diag(d1,d2,…dn)和單位上三角矩陣U，使得A=LDU的充要條件是A的所有順序主子式均非零，即整理課件矩陣的LU分解方法矩陣的LU分解方法有很多種，這里主要介紹初等行變換消元法步驟：1.通過初等行變換將A化為上三角矩陣U：〔A，I〕〔U，L1〕2.取L=：因為L1是一系列初等下三角矩陣乘積〔對應初等行變換〕，所以L是單位下三角矩陣。整理課件例1求以下矩陣的LU分解：整理課件解：從而得這里整理課件因為所以整理課件1.即使矩陣A非奇異，如果A不滿足前n-1個順序主子式非零，未必能做LU分解，2.適當改變非奇異矩陣的行的次序，可使改變后的矩陣做LU分解，引入排列陣的概念說明整理課件定義1設(shè)e1,e2,…,en是n階單位矩陣I的n個列向量，矩陣P=(ei1,ei2,,…,ein)稱為一個n階排列陣，其中i1,i2,…,in是1,2…n的一個排列.P是排列陣的充要條件是P為一系列形如P(i,j)的初等交換矩陣的乘積.整理課件排列陣的性質(zhì)：1.P是排列陣，那么PT和P-1也是排列陣，且PT=P-12.P1，P2是排列陣，那么P1P2是排列陣3.即：用排列陣左乘矩陣A相當于將A的行按照排列陣的次序重排，右乘對A的列按排列陣的次序重排。整理課件引理1設(shè)A是n階非奇異矩陣，那么存在排列陣P，使得PA的所有順序主子式要條件均非零。定理3設(shè)A是n階非奇異矩陣，那么存在排列陣P，使得PA=LDU所其中L是單位下三角矩陣，U是單位上三角矩陣，D是對角矩陣。整理課件三角方程組易于求解矩陣LU分解的一個應用——解線性方程組整理課件定理設(shè)矩陣A對稱正定，那么存在唯一的對角元為正的下三角陣L，使得

稱為對稱正定矩陣A的喬累斯基分解利用喬累斯基〔Cholesky〕分解式來求解Ax=b的方法也稱Cholesky方法或平方根法MATLAB函數(shù)：Chol(A)；lu(A)是求矩陣的LU分解函數(shù)喬累斯基〔Cholesky〕分解整理課件§4.4

QR分解QR分解在矩陣計算中占據(jù)相當重要的地位。利用QR分解，可以解決各種應用中〔例如圖像壓縮處理、結(jié)構(gòu)分析等〕出現(xiàn)的最小二乘問題、特征值問題等矩陣計算中的核心問題。以初等變換為工具的三角分解無法消除病態(tài)矩陣的不穩(wěn)定性，因此引入以正交變換為工具的QR分解方法整理課件定理1(QR分解定理)設(shè)A是n階非奇異實〔復〕矩陣，那么存在正交〔酉〕矩陣Q與非奇異實〔復〕上三角矩陣R，使得A=QR且除去相差一個對角元絕對值全等于1的對角矩陣因子，分解式是唯一的。矩陣的QR分解也稱為正交三角分解；假設(shè)規(guī)定上三角矩陣R的對角元符號，那么A的QR分解唯一。整理課件證明：先證明分解的存在性。將矩陣A按列分塊得到由于，所以是線性無關(guān)的。利用Schmidt正交化與單位化方法，先得到一組正交向量組再單位化，這樣得到一組標準正交向量組并且向量組之間有如下關(guān)系整理課件于是有整理課件為正交矩陣。證畢整理課件唯一性：設(shè)A=QR=Q1R1,那么Q=Q1R1R-1=Q1D，其中D=R1R-1為非奇異上三角矩陣，于是I=QHQ=(Q1D)H(Q1D)=DHD所以D為酉矩陣，比較DHD=DDH=I的對角元，可得D為對角矩陣，且對角元的模為1，于是R1=DR,Q1=QD-1證畢整理課件定理2設(shè)A是列滿秩的mn實〔復〕矩陣，那么存在m階正交〔酉〕矩陣Q和n階非奇異實〔復〕上三角矩陣R，使得定理3設(shè)A是mn矩陣，且rank(A)=r>0,那么存在m階正交〔酉〕矩陣Q和rn階行滿秩矩陣R，使得非奇異矩陣的QR分解的推廣：整理課件推論設(shè)A是mn矩陣，且rank(A)=r>0,那么存在mr列正交標準矩陣Q1和rn行滿秩矩陣R，使得A=Q1R，列正交標準矩陣指的是mr矩陣Q1滿足。矩陣Q1是列正交標準矩陣的充要條件是Q1的列向量組是標準正交向量組整理課件一、Schmidt方法步驟：1.將矩陣A的列向量1，2，…n施以Schmidt標準正交化,得到1，2，…n標準正交組：2.取Q=(1，2，…n)，那么Q為正交矩陣3.取R=QTA矩陣的QR分解方法整理課件例1利用Schmidt方法將以下矩陣進行QR分解：整理課件解

先將A=[

1，

2

，

3]的三個列向量正交化與單位化：整理課件所以A的QR分解為：A=QR整理課件從而1.取A的列向量1，2，…n，對1，由Householder矩陣性質(zhì)知存在Householder矩陣H1，使得〔為方便說明，不妨取負號〕二、Householder

變換法步驟：整理課件從而2.對，當

時，存在Householder

矩陣H2，使得整理課件那么得取如果，那么，直接進行下一步。整理課件使得3.對An-2繼續(xù)類似的變換，如此最多n-1步，也即至多可以找到n-1個矩陣令Q=Hn-1…H2H1，那么Q為正交矩陣，從而得到QR分解整理課件例2利用Householder變換將以下矩陣進行QR分解整理課件對向量，令解：從而得Householder

矩陣整理課件使得

注意

，即被反射到對向量，令可得Householder

矩陣整理課件因此取從而有整理課件所求的QR分解為整理課件定義1設(shè)A，BRnn(Cnn),假設(shè)存在n階正交〔酉〕矩陣U使得UTAU=U-1AU=B〔UHAU=U-1AU=B〕，稱A正交〔酉〕相似B?！?.5Schur

定理和正規(guī)矩陣(SchurtheoryandNormalMatrices)定理1〔Schur定理〕任何一個n階復矩陣A都酉相似于一個上三角矩陣，即存在一個n階酉矩陣U和一個n階上三角矩陣R使得UHAU=R其中R的對角元是A的特征值，可以按要求的順序排列整理課件定義2設(shè)ACnn，假設(shè)AHA=AAH，稱A為正規(guī)矩陣。常見的正規(guī)矩陣：對角矩陣;對稱和反對稱矩陣：AT=A，AT=–A。Hermite矩陣和反Hermite矩陣：AH=A，AH=–A正交矩陣和酉矩陣：ATA=AAT=I，AHA=AAH=I。正規(guī)矩陣整理課件正規(guī)矩陣的性質(zhì)：1.正規(guī)矩陣有n個線性無關(guān)的特征向量；2.正規(guī)矩陣屬于不同特征值的特征向量是正交的；3.與正規(guī)矩陣酉相似的矩陣都是正規(guī)矩陣。整理課件由定理2假設(shè)A是n階正規(guī)矩陣，那么A酉相似于一個對角陣，即存在一個n階酉矩陣U使得UHAU=，其中=diag(1,…,n),i(i=1,2,…n)是A的特征值。該式稱為正規(guī)矩陣的譜分解式.正規(guī)是酉相似的不變性質(zhì)定理2

n階矩陣A酉相似于一個對角陣的充要條件是A是正規(guī)矩陣。整理課件即

i是矩陣A的特征值

i所對應的單位特征向量。設(shè)U=(1,2,…,n),那么由定理2知UHAU==diag(1,…,n),可得即Ai=ii〔1,2,…n〕求譜分解式的步驟整理課件例1：求正規(guī)矩陣的譜分解表達式。解：首先求出矩陣A

的特征值與特征向量。容易計算整理課件從而A的特征值為

λ1=λ2=λ3=1,λ4=-3當λ=1時，求得三個線性無關(guān)的特征向量為

α1=[1,1,0,0]T

α2=[1,0,1,0]T

α3=[-1,0,0,1]T整理課件當λ=-3時，求得一個線性無關(guān)的特征向量為

α4=[1,-1,-1,1]T將α1,α2,α3正交化與單位化可得整理課件將α4單位化可得：于是有這樣可得其譜分解表達式為A=U

UH整理課件推論1設(shè)A是n階Hermite矩陣，那么A必酉相似于對角矩陣，即存在一個n階酉矩陣U使得UHAU=，其中=diag(1,…,n),i(i=1,2,…n)是A的實特征值。該分解式稱為Hermite矩陣A的譜分解式。整理課件是一種通用的降維工具。在我們處理高維數(shù)據(jù)的時候，為了能降低后續(xù)計算的復雜度，在“預處理〞階段通常要先對原始數(shù)據(jù)進行降維。原那么：降維后的數(shù)據(jù)不能失真，也就是說，被PCA降掉的那些維度只能是那些噪聲或是冗余的目的就是“降噪〞和“去冗余〞?！敖翟毹暤哪康木褪鞘贡４嫦聛淼木S度間的相關(guān)性盡可能小，“去冗余〞的目的就是使保存下來的維度含有的“能量〞盡可能大。著名的PCA〔PrincipalComponentAnalysis〕整理課件形成樣本矩陣S

N

d，假設(shè)我們有一個樣本集X，里面有N個樣本，每個樣本的維度為d。即：即每行為一個樣本，每一列為一個維度，得到樣本矩陣S著名的PCA〔PrincipalComponentAnalysis〕整理課件2.計算樣本矩陣的協(xié)方差矩陣；協(xié)方差矩陣度量的是維度與維度之間的關(guān)系，主對角線上的元素是各個維度上的方差(即能量)，其他元素是兩兩維度間的協(xié)方差(即相關(guān)性)。著名的PCA〔PrincipalComponentAnalysis〕整理課件3.〔1〕去噪對協(xié)方差矩陣S進行譜分解，去不同維度的相關(guān)性〔非對角元素化為0〕找到一個正交矩陣P，滿足〔2〕降維選取中最大的p個特征值對應的特征向量組成投影矩陣P1：取最大的前p(p<d)個特征值對應的維度，對應的p個特征向量組成了新的特征向量矩陣P1，該P1就是投影矩陣。著名的PCA〔PrincipalComponentAnalysis〕整理課件4.對原始樣本矩陣S進行投影，得到降維后的新樣本矩陣S1：即S1=SP1；理由：假設(shè)PCA降維后的樣本矩陣為S1，顯然，根據(jù)PCA的目的，S1中的各個維度間的協(xié)方差根本為零，也就是說S1的協(xié)方差矩陣應該為對角矩陣。即滿足：著名的PCA〔PrincipalComponentAnalysis〕由〔3〕整理課件著名的PCA〔PrincipalComponentAnalysis〕由于樣本矩陣的每一行是一個樣本，特征向量矩陣的每一列是一個特征向量。右乘相當于以每個樣本的特征向量為基進行線性變換，得到的新樣本矩陣中每個樣本的維數(shù)變?yōu)榱藀，完成了降維操作。實際上，P1中的特征向量就是低維空間新的坐標系，稱之為“主成分〞。這就是“主成分分析〞的名稱由來。整理課件從Beltrami〔1873〕和Jordan〔1874〕提出奇異值分解〔SVD：SingularValueDecomposition〕至今，SVD已經(jīng)成為矩陣計算中最有用和最有效的工具之一，由于奇異值良好的數(shù)學特征,奇異值分解不僅僅應用在主成分分析、圖像壓縮、數(shù)字水印和文章分類中,而且在信號分解、信號重構(gòu)、信號降躁、數(shù)據(jù)融合、目標識別、目標跟蹤、故障檢測和神經(jīng)網(wǎng)絡(luò)等方面有很好的應用?！?.6奇異值分解(SVD)〔SingularValueDecomposition〕整理課件引理1設(shè)ACm×n，那么AHACn×n，AAHCm×m，且〔1〕Rank(AHA)=Rank(AAH)=Rank(A)〔2〕AHA與AAH的特征值均為非負實數(shù)；〔3〕AHA與AAH的非零特征值相同，并且非零特征值的個數(shù)〔重特征值按重數(shù)計算〕等于rank〔A〕；〔4〕AHA=0A=0整理課件定義1設(shè)ACm×n，假設(shè)存在非負實數(shù)和非零向量uCn，vCm，使得Au=v,AHv=u〔*〕稱為矩陣A的奇異值。相應地，u和v分別稱為A對應于奇異值的右奇異向量和左奇異向量。說明：由〔*〕式得(AHA)u=AHv=2u，(AAH)v=Au=2v所以2是AHA的特征值也是AAH的特征值,而u和v分別是對應于2的特征向量。所以有整理課件設(shè)ACm×n，rank(A)=r，設(shè)AHA的特征值12r0，r+1=r+2==n=0，稱為矩陣A的奇異值。假設(shè)i>0,稱i為A的正奇異值。另一種定義：整理課件定理1：正規(guī)矩陣A的奇異值等于A的特征值的模長。證：根據(jù)正規(guī)矩陣的性質(zhì)，知存在酉矩陣U使得A=Udiag(

1,2,,n

)UH,其中

1,2,,n是A的特征值，所以AHA=Udiag(|

1|2,|

2|2,,|

n|2

)UH所以A的奇異值為|

1|,|

2|,,|

n|

#整理課件定理2〔奇異值分解定理〕設(shè)ACm×n，秩〔A〕=r，那么存在m階酉矩陣V和n階酉矩陣U使得其中=diag(1,…,r),且1r>0.整理課件1.U的列向量是AHA的標準正交特征向量；〔也稱為懸掛矩陣〕2.U的前r列向量是AHA對應于r個非零特征值12，r2的標準正交特征向量；3.V的列向量是AAH的標準正交特征向量；〔也稱為對準矩陣〕4.V的前r列向量是AHA對應于特征值12，r2的標準正交特征向量；注記：整理課件第二步：令U1=(u1…ur),計算求矩陣SVD的算法第一步：計算，并計算特征值

1…

n和對應的標準正交特征向量u1…un，取U=(u1…un)注：根據(jù)這樣的取法得AAHV1=A(AHAU1)

-1=A(U1

2)-1=AU1=V1

2即：V1對應于特征值

12，

r2的標準正交特征向量整理課件第三步：求解線性方程組的標準正交根底解系vr+1…vm，令V=(v1,…vr,vr+1,...vm)那么U和V即為所求。整理課件例1求以下矩陣的SVD分解：解：第一步整理課件矩陣AHA的特征值為3,1,0，對應的特征向量為標準正交化得整理課件第二步令：計算：其中整理課件第三步解，得其根底解系為從而整理課件因此所求SVD為整理課件例2：求以下矩陣的奇異值分解表達式整理課件解:〔1〕計算AHA的特征值分別為5,0。對應的兩個標準正交特征向量由這兩個標準正交特征向量組成矩陣U整理課件〔2〕計算AAH的特征值為5，0，0，所以A的奇異值為。下面計算AAH的標準正交特征向量，解得分別與5，0，0對應的三個標準正交特征向量由這三個標準正交特征向量組成矩陣V，所以有整理課件于是可得奇異值分解式為整理課件注：使用第二種方法時選取的U和V不唯一，他們的對應列之間相差一個符號，因此當分解式不成立時，需要調(diào)整相應的特征向量符號。整理課件SVD的幾何意義:

圓S經(jīng)過變換A，變成橢圓AS。圓的正交方向u1,u2變成橢圓的長、短軸方向,。設(shè)矩陣A的奇異值分解為A=V

UT，考慮A對應的線性變換Au1u2

1v1

2v2

2u2

1u1SAS

1v1

2v2整理課件

從變換的角度理解SVD，酉變換U保持球面不變，對角矩陣

將球面拉伸到一個有標準基的橢圓(

1，2是A的兩個奇異值，對應橢圓的長半軸和短半軸)，最后酉變換V旋轉(zhuǎn)或鏡射這個橢圓，但不改變它的形狀。整理課件矩陣奇異值分解的特點：1.數(shù)據(jù)壓縮：矩陣Amn的奇異值分解為：A=VUT，其展開式：A有nm個數(shù)據(jù)，分解后為(m+n+1)r個數(shù)據(jù)，假設(shè)A的秩r遠遠小于m和n,那么通過奇異值分解可以大大降低A的維數(shù),可以到達降維的目的,同時可以降低計算機對存貯器的要求，常用于圖像壓縮。奇異值的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了。也就是說，我們也可以用前k個大的奇異值來近似描述矩陣。整理課件圖像的數(shù)字化技術(shù)與矩陣的奇異值分解

計算機處理圖像技術(shù)的第一步是圖像的數(shù)字化存儲技術(shù)，即將圖像轉(zhuǎn)換成矩陣來存儲。轉(zhuǎn)換的原理是將圖形分解成象素〔pixels〕的一個矩形的數(shù)陣，其中的信息就可以用一個矩陣A=(aij)m×n來存儲。矩陣A的元素aij是一個正的數(shù)，它相應于象素的灰度水平〔graylevel〕的度量值。由于一般來講，相鄰的象素會產(chǎn)生相近的灰度水平值，因此有可能在滿足圖像清晰度要求的條件下，將存儲一個m×n階矩陣需要存儲的m×n個數(shù)減少到n+m+1的一個倍數(shù)。整理課件壓縮數(shù)字化圖形存儲量的方法主要是應用矩陣的奇異值分解和矩陣范數(shù)下的逼近。如果圖象的數(shù)字矩陣A的奇異值分解為：A=U

VT，其展開式：壓縮矩陣A的方法是取一個秩為k(k

r)的矩陣Ak來逼近矩陣A。Ak按如下方法選?。哼@是矩陣A的秩1分解式。整理課件在秩為k(k

n)的所有矩陣中，矩陣Ak所對應的圖象和矩陣A所對應的圖象最相近。一般的，k越大圖象就越清晰。壓縮比：

=(m+n+1)/mn;經(jīng)典的方法是選取接近k，使Ak的存儲量比A的存儲量減少20%。整理課件整理課件整理課件整理課件整理課件矩陣奇異值分解的特點：2.奇異值對矩陣的擾動不敏感,而特征值對矩陣的擾動敏感。3.奇異值的比例不變性。即kA的奇異值是A的奇異值的|k|倍。4.奇異值的旋轉(zhuǎn)不變性。即假設(shè)P是正交陣,PA的奇異值與A的奇異值相同。奇異值的比例和旋轉(zhuǎn)不變性特征在數(shù)字圖像的旋轉(zhuǎn)、鏡像、平移、放大、縮小等幾何變化方面有很好的應用。整理課件5.容易得到矩陣A的秩為k(k≤r)〔低秩〕的一個最正確逼近矩陣。奇異值的這個特征可以應用于信號的分解和重構(gòu),提取有用信息,消除信號噪聲等6.假設(shè)A、B都有相同的奇異向量,那么||A–B||2=,即,我們可以通過控制奇異值的大小來控制兩個矩陣空間的距離。整理課件存儲矩陣Ak只需要存儲k個奇異值，k個m維向量ui和n維向量vj的所有分量，共計k〔m+n+1〕個元素。如果m=n=1000