用 PCA 獲得的低秩近似矩陣最小化了重構誤差的範數？
給定矩陣的 PCA（或 SVD）近似值有一個矩陣， 我們知道是的最佳低秩近似.
這是按照誘導範數（即最大特徵值範數）或根據 Frobenius規範？
一個字回答：兩者都有。
讓我們從定義規範開始。對於矩陣 $ X $ ， 操作員 $ 2 $ -norm 定義為$$ |X|_2 = \mathrm{sup}\frac{|Xv|_2}{|v|2} = \mathrm{max}(s_i) $$和 Frobenius 範數為$$ |X|F = \sqrt {\sum{ij} X{ij}^2} = \sqrt{\mathrm{tr}(X^\top X)} = \sqrt{\sum s_i^2}, $$ 在哪裡 $ s_i $ 是奇異值 $ X $ ，即對角元素 $ S $ 在奇異值分解中 $ X = USV^\top $ .
當數據居中時，PCA 由相同的奇異值分解給出。 $ US $ 是主要成分， $ V $ 是主軸，即協方差矩陣的特徵向量，以及 $ X $ 只有 $ k $ 對應的主成分 $ k $ 最大奇異值由下式給出 $ X_k = U_k S_k V_k^\top $ .
Eckart -Young 定理說 $ X_k $ 是最小化重構誤差範數的矩陣 $ |X-A| $ 在所有矩陣中 $ A $ 等級 $ k $ . 這對 Frobenius 範數和運算符都是正確的 $ 2 $ -規範。正如@cardinal 在評論中指出的那樣，1907 年，施密特（Gram-Schmidt 成名）首次證明了 Frobenius 案。它後來在 1936 年被 Eckart 和 Young 重新發現，現在主要與他們的名字有關。Mirsky 在 1958 年將該定理推廣到在酉變換下不變的所有範數，這包括算子 2-範數。
這個定理有時被稱為 Eckart-Young-Mirsky 定理。Stewart (1993) 稱之為施密特近似定理。我什至見過它叫做施密特-埃卡特-楊-米爾斯基定理。
- Eckart 和 Young，1936 年，一個矩陣由另一個較低等級的矩陣逼近
- Mirsky，1958，對稱規範函數和酉不變範數
- Stewart，1993，關於奇異值分解的早期歷史
運營商證明 $ 2 $ -規範
讓 $ X $ 滿級 $ n $ . 作為 $ A $ 有等級 $ k $ , 它的零空間有 $ n-k $ 方面。所跨越的空間 $ k+1 $ 的右奇異向量 $ X $ 對應的最大奇異值有 $ k+1 $ 方面。所以這兩個空間必須相交。讓 $ w $ 是交點的單位向量。然後我們得到： $$ |X-A|^2_2 \ge |(X-A)w|^2_2 = |Xw|^2_2 = \sum_{i=1}^{k+1}s_i^2(v_i^\top w)^2 \ge s_{k+1}^2 = |X-X_k|_2^2, $$QED。
Frobenius 範數的證明
我們想找到矩陣 $ A $ 等級 $ k $ 最小化 $ |X-A|^2_F $ . 我們可以分解 $ A=BW^\top $ ， 在哪裡 $ W $ 擁有 $ k $ 正交列。最小化 $ |X-BW^\top|^2 $ 對於固定 $ W $ 是一個有解的回歸問題 $ B=XW $ . 插入它，我們看到我們現在需要最小化$$ |X-XWW^\top|^2=|X|^2-|XWW^\top|^2=\mathrm{const}-\mathrm{tr}(WW^\top X^\top XWW^\top)\=\mathrm{const}-\mathrm{const}\cdot\mathrm{tr}(W^\top\Sigma W), $$在哪裡 $ \Sigma $ 是協方差矩陣 $ X $ ， IE $ \Sigma=X^\top X/(n-1) $ . 這意味著通過將 $ W $ 一些 $ k $ 正交向量最大化投影的總方差。
眾所周知，這些是第一 $ k $ 協方差矩陣的特徵向量。確實，如果 $ X=USV^\top $ ， 然後 $ \Sigma=VS^2V^\top/(n-1)=V\Lambda V^\top $ . 寫作 $ R=V^\top W $ 它也有正交列，我們得到$$ \mathrm{tr}(W^\top\Sigma W)=\mathrm{tr}(R^\top\Lambda R)=\sum_i \lambda_i \sum_j R_{ij}^2 \le \sum_{i=1}^k \lambda_k, $$達到最大值時 $ W=V_k $ . 然後定理立即成立。
請參閱以下三個相關線程：
Frobenius 範數的早期證明嘗試
正如@cardinal 在評論中所解釋的那樣，我在網上某處找到了這個證明，但它是錯誤的（包含一個空白）。
Frobenius 範數在酉變換下是不變的，因為它們不會改變奇異值。所以我們得到：$$ |X-A|F=|USV^\top - A| = |S - U^\top A V| = |S-B|, $$在哪裡 $ B=U^\top A V $ . 繼續：$$ |X-A|F = \sum{ij}(S{ij}-B_{ij})^2 = \sum_i (s_i-B_{ii})^2 + \sum_{i\ne j}B_{ij}^2. $$當所有非對角線元素 $ B $ 是零和所有 $ k $ 對角項抵消了 $ k $ 最大奇異值 $ s_i $ [這裡的差距：這並不明顯]，即 $ B_\mathrm{optimal}=S_k $ 因此 $ A_\mathrm{optimal} = U_k S_k V_k^\top $ .