第四章矩陣的因子分解..ppt

第4章矩陣的因子分解 MatrixFactorizationandDecomposition 教學要求掌握矩陣的滿秩分解 掌握矩陣的三角分解 掌握矩陣的正交分解 掌握Schur定理和正規(guī)矩陣的定義 熟練掌握矩陣的奇異值分解 數(shù)據(jù)集中可能包含大量特征 維災難使得數(shù)據(jù)分析很困難 1 維歸約 降維 利用舊屬性的線性組合得到新屬性 使得新屬性相互正交 捕獲到數(shù)據(jù)的最大變差 PCA 主成分分析 principlecomponentsanalysis 和SVD 2 選擇特征子集 嵌入 決策樹分類其 過濾和包裝 搜索 特征加權等 矩陣的各種分解在矩陣計算中也扮演相當重要的角色 由于變換即矩陣 所以各種分解從根本上看是各種變換 其目的是將矩陣變換成特殊的矩陣 4 2矩陣的滿秩分解滿秩分解定理 設為任意矩陣 則存在使得A BC 其中B為列滿秩矩陣 C為行滿秩矩陣 任一非 行或列 滿秩的非零矩陣可表示為一列滿秩矩陣和一行滿秩矩陣的積 B的列可取為A的列的任一極大線性無關組 C可取為其行為A的行所生成的空間的基 然后用定理確定矩陣B 應用于極小最小二乘解和極小范數(shù)最小二乘解的算法中 例1求下面矩陣的滿秩分解 解思路 對矩陣A實施初等行變換得簡化階梯形矩陣H 階梯型的非零行的第一個非零元為1 其所在的列其它元素為0 取A的r個使H陣滿秩的列為B 將H全為零的行去掉后即可構成行滿秩矩陣C 由此可知rank A 2 且該矩陣第一列 第三列是線性無關的 選取 同樣 我們也可以選取 由上述例子可以看出矩陣的滿秩分解形式并不唯一 但是不同的分解形式之間有如下聯(lián)系 注 如果均為矩陣A的滿秩分解 那么存在矩陣滿足 則稱其為A的LU分解或三角分解 4 3矩陣的三角分解 定義1如果方陣A可以分解成一個單位下三角矩陣L與一個上三角矩陣U的乘積 初等下三角矩陣 初等下三角矩陣性質 1 det Li 1 2 用初等下三角矩陣左乘矩陣A 等于將A的第i行依次乘以 li 1i lni分別加到第i 1行到第n行上去 3 設A aij n n 且ajj 0 并且取 則LiA在 i 1 j i 2 j n j 的位置上為0 4 定理1 LU分解定理 設A是n階非奇異矩陣 則存在唯一的單位下三角矩陣L 主對角線上元素全為1的下三角矩陣 與唯一的上三角矩陣U 使得的充要條件是A的所有順序主子式均非零 即 矩陣的LU分解也稱為Doolitte分解若L為下三角矩陣 U為單位上三角矩陣 稱為Crout分解 定理2 LDU分解定理 設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設e1 e2 en是n階單位矩陣I的n個列向量 矩陣P ei1 ei2 ein 稱為一個n階排列陣 其中i1 i2 in是1 2 n的一個排列 P是排列陣的充要條件是P為一系列形如P i j 的初等交換矩陣的乘積 排列陣的性質 1 P是排列陣 則PT和P 1也是排列陣 且PT P 12 P1 P2是排列陣 則P1P2是排列陣3 即 用排列陣左乘矩陣A相當于將A的行按照排列陣的次序重排 右乘對A的列按排列陣的次序重排 引理1設A是n階非奇異矩陣 則存在排列陣P 使得PA的所有順序主子式要條件均非零 定理3設A是n階非奇異矩陣 則存在排列陣P 使得PA LDU所其中L是單位下三角矩陣 U是單位上三角矩陣 D是對角矩陣 三角方程組易于求解 矩陣LU分解的一個應用 解線性方程組 定理 設矩陣A對稱正定 則存在唯一的對角元為正的下三角陣L 使得 稱為對稱正定矩陣A的喬累斯基分解 利用喬累斯基 Cholesky 分解式來求解Ax b的方法也稱Cholesky方法或平方根法MATLAB函數(shù) Chol A lu A 是求矩陣的LU分解函數(shù) 喬累斯基 Cholesky 分解 4 4QR分解 QR分解在矩陣計算中占據(jù)相當重要的地位 利用QR分解 可以解決各種應用中 例如圖像壓縮處理 結構分析等 出現(xiàn)的最小二乘問題 特征值問題等矩陣計算中的核心問題 以初等變換為工具的三角分解無法消除病態(tài)矩陣的不穩(wěn)定性 因此引入以正交變換為工具的QR分解方法 定理1 QR分解定理 設A是n階非奇異實 復 矩陣 則存在正交 酉 矩陣Q與非奇異實 復 上三角矩陣R 使得A QR且除去相差一個對角元絕對值全等于1的對角矩陣因子 分解式是唯一的 矩陣的QR分解也稱為正交三角分解 若規(guī)定上三角矩陣R的對角元符號 則A的QR分解唯一 證明 先證明分解的存在性 將矩陣A按列分塊得到由于 所以是線性無關的 利用Schmidt正交化與單位化方法 先得到一組正交向量組 再單位化 這樣得到一組標準正交向量組 并且向量組之間有如下關系 于是有 為正交矩陣 證畢 唯一性 設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設A是列滿秩的m n實 復 矩陣 則存在m階正交 酉 矩陣Q和n階非奇異實 復 上三角矩陣R 使得定理3設A是m n矩陣 且rank A r 0 則存在m階正交 酉 矩陣Q和r n階行滿秩矩陣R 使得 非奇異矩陣的QR分解的推廣 推論設A是m n矩陣 且rank A r 0 則存在m r列正交規(guī)范矩陣Q1和r n行滿秩矩陣R 使得A Q1R 列正交規(guī)范矩陣指的是m r矩陣Q1滿足 矩陣Q1是列正交規(guī)范矩陣的充要條件是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矩陣性質知存在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設A B Rn n Cn n 若存在n階正交 酉 矩陣U使得UTAU U 1AU B UHAU U 1AU B 稱A正交 酉 相似B 4 5Schur定理和正規(guī)矩陣 SchurtheoryandNormalMatrices 定理1 Schur定理 任何一個n階復矩陣A都酉相似于一個上三角矩陣 即存在一個n階酉矩陣U和一個n階上三角矩陣R使得UHAU R其中R的對角元是A的特征值 可以按要求的順序排列 定義2設A Cn n 若AHA AAH 稱A為正規(guī)矩陣 常見的正規(guī)矩陣 對角矩陣 對稱和反對稱矩陣 AT A AT A Hermite矩陣和反Hermite矩陣 AH A AH A正交矩陣和酉矩陣 ATA AAT I AHA AAH I 正規(guī)矩陣 正規(guī)矩陣的性質 1 正規(guī)矩陣有n個線性無關的特征向量 2 正規(guī)矩陣屬于不同特征值的特征向量是正交的 3 與正規(guī)矩陣酉相似的矩陣都是正規(guī)矩陣 由定理2若A是n階正規(guī)矩陣 則A酉相似于一個對角陣 即存在一個n階酉矩陣U使得UHAU 其中 diag 1 n i i 1 2 n 是A的特征值 該式稱為正規(guī)矩陣的譜分解式 正規(guī)是酉相似的不變性質 定理2n階矩陣A酉相似于一個對角陣的充要條件是A是正規(guī)矩陣 即 i是矩陣A的特征值 i所對應的單位特征向量 設U 1 2 n 則由定理2知UHAU diag 1 n 可得 即A i i i 1 2 n 求譜分解式的步驟 例1 求正規(guī)矩陣 的譜分解表達式 解 首先求出矩陣A的特征值與特征向量 容易計算 從而A的特征值為 1 2 3 1 4 3當 1時 求得三個線性無關的特征向量為 1 1 1 0 0 T 2 1 0 1 0 T 3 1 0 0 1 T 當 3時 求得一個線性無關的特征向量為 4 1 1 1 1 T將 1 2 3正交化與單位化可得 將 4單位化可得 于是有 這樣可得其譜分解表達式為A U UH 推論1設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降掉的那些維度只能是那些噪聲或是冗余的目的就是 降噪 和 去冗余 降噪 的目的就是使保留下來的維度間的相關性盡可能小 去冗余 的目的就是使保留下來的維度含有的 能量 盡可能大 著名的PCA PrincipalComponentAnalysis 形成樣本矩陣SN d 假設我們有一個樣本集X 里面有N個樣本 每個樣本的維度為d 即 即每行為一個樣本 每一列為一個維度 得到樣本矩陣S 著名的PCA PrincipalComponentAnalysis 2 計算樣本矩陣的協(xié)方差矩陣 協(xié)方差矩陣度量的是維度與維度之間的關系 主對角線上的元素是各個維度上的方差 即能量 其他元素是兩兩維度間的協(xié)方差 即相關性 著名的PCA PrincipalComponentAnalysis 3 1 去噪對協(xié)方差矩陣S進行譜分解 去不同維度的相關性 非對角元素化為0 找到一個正交矩陣P 滿足 2 降維選取 中最大的p個特征值對應的特征向量組成投影矩陣P1 取最大的前p p d 個特征值對應的維度 對應的p個特征向量組成了新的特征向量矩陣P1 該P1就是投影矩陣 著名的PCA PrincipalComponentAnalysis 4 對原始樣本矩陣S進行投影 得到降維后的新樣本矩陣S1 即S1 SP1 理由 假設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ù)字水印和文章分類中 而且在信號分解 信號重構 信號降躁 數(shù)據(jù)融合 目標識別 目標跟蹤 故障檢測和神經(jīng)網(wǎng)絡等方面有很好的應用 4 6奇異值分解 SVD SingularValueDecomposition 引理1設A Cm n 則AHA Cn n AAH Cm m 且 1 Rank AHA Rank AAH Rank A 2 AHA與AAH的特征值均為非負實數(shù) 3 AHA與AAH的非零特征值相同 并且非零特征值的個數(shù) 重特征值按重數(shù)計算 等于rank A 4 AHA 0 A 0 定義1設A Cm n 若存在非負實數(shù) 和非零向量u Cn v Cm 使得Au v AHv u 稱 為矩陣A的奇異值 相應地 u和v分別稱為A對應于奇異值 的右奇異向量和左奇異向量 說明 由 式得 AHA u AHv 2u AAH v Au 2v所以 2是AHA的特征值也是AAH的特征值 而u和v分別是對應于 2的特征向量 所以有 設A Cm n rank A r 設AHA的特征值 1 2 r 0 r 1 r 2 n 0 稱為矩陣A的奇異值 若 i 0 稱 i為A的正奇異值 另一種定義 定理1 正規(guī)矩陣A的奇異值等于A的特征值的模長 證 根據(jù)正規(guī)矩陣的性質 知存在酉矩陣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 奇異值分解定理 設A Cm n 秩 A r 則存在m階酉矩陣V和n階酉矩陣U使得其中 diag 1 r 且 1 r 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不唯一 他們的對應列之間相差一個符號 因此當分解式不成立時 需要調整相應的特征向量符號 SVD的幾何意義 圓S經(jīng)過變換A 變成橢圓AS 圓的正交方向u1 u2變成橢圓的長 短軸方向 設矩陣A的奇異值分解為A V UT 考慮A對應的線性變換A u1 u2 1v1 2v2 AS 1v1 2v2 從變換的角度理解SVD 酉變換U保持球面不變 對角矩陣 將球面拉伸到一個有標準基的橢圓 1 2是A的兩個奇異值 對應橢圓的長半軸和短半軸 最后酉變換V旋轉或鏡射這個橢圓 但不改變它的形狀 矩陣奇異值分解的特點 1 數(shù)據(jù)壓縮 矩陣Am n的奇異值分解為 A V UT 其展開式 A有nm個數(shù)據(jù) 分解后為 m n 1 r個數(shù)據(jù) 若A的秩r遠遠小于m和n 則通過奇異值分解可以大大降低A的維數(shù) 可以達到降維的目的 同時可以降低計算機對存貯器的要求 常用于圖像壓縮 奇異值的減少特別的快 在很多情況下 前10 甚至1 的奇異值的和就占了全部的奇異值之和的99 以上了 也就是說 我們也可以用前k個大的奇異值來近似描述矩陣 圖像的數(shù)字化技術與矩陣的奇異值分解 計算機處理圖像技術的第一步是圖像的數(shù)字化存儲技術 即將圖像轉換成矩陣來存儲 轉換的原理是將圖形分解成象素 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 奇異值的旋轉不變性 即若P是正交陣 PA的奇異值與A的奇異值相同 奇異值的比例和旋轉不變性特征在數(shù)字圖像的旋轉 鏡像 平移 放大 縮小等幾何變化方面有很好的應用 5 容易得到矩陣A的秩為k k r 低秩 的一個最佳逼近矩陣 奇異值的這個特征可以應用于信號的分解和重構 提取有用信息 消除信號噪聲等6 若A B都有相同的奇異向量 則 A B 2 即 我們可以通過控制奇異值的大小來控制兩個矩陣空間的距離 存儲矩陣Ak只需要存儲k個奇異值 k個m維向量ui和n維向量vj的所有分量 共計k m n 1 個元素 如果m n 1000 存儲原矩陣A需要存儲1000 1000個元素 取k 100時 圖象已經(jīng)非常清晰了 這時的存儲量是100 2000 1 200100個數(shù) 和矩陣A比較 存儲量減少了80 SVD用于文本分類 用一個大矩陣A來描述一百萬篇文章和五十萬詞的關聯(lián)性