PCA 優化是凸的嗎？
主成分分析 (PCA) 的目標函數是最小化 L2 範數中的重構誤差（請參見此處的第 2.12 節。另一種觀點是試圖最大化投影方差。我們在這裡也有一篇很好的帖子：什麼是 PCA 的目標函數? )。
我的問題是PCA 優化是凸的嗎？（我在這裡找到了一些討論，但希望有人可以在簡歷上提供一個很好的證明）。
不，PCA 的常用公式不是凸問題。 但它們可以轉化為凸優化問題。
其洞察力和樂趣在於跟踪和可視化轉換的順序，而不僅僅是獲得答案：它在於旅程，而不是目的地。這段旅程的主要步驟是
- 獲得目標函數的簡單表達式。
- 將其非凸的域擴大為一個。
- 將非凸目標修改為凸目標，其方式顯然不會改變其達到最佳值的點。
如果你密切關注，你可以看到潛伏的 SVD 和拉格朗日乘數——但它們只是一個小插曲，只是為了風景，我不會進一步評論它們。
PCA （或至少其關鍵步驟）的標準方差最大化公式是
$$ \text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x=1\tag{*} $$
在哪裡 $ n\times n $ 矩陣 $ \mathbb A $ 是從數據（通常是其平方和乘積矩陣、協方差矩陣或相關矩陣）構造的對稱半正定矩陣。
（等效地，我們可以嘗試最大化無約束目標 $ x^\prime \mathbb{A} x / x^\prime x $ . 這不僅是一個更糟糕的表達式——它不再是一個二次函數——而且繪製特殊情況很快就會表明它也不是一個凸函數。通常人們觀察到這個函數在重新縮放下是不變的 $ x\to \lambda x $ 然後將其簡化為受約束的公式 $ (*) $ .)
任何優化問題都可以抽像地表述為
至少找到一個 $ x\in\mathcal{X} $ 這使得函數 $ f:\mathcal{X}\to\mathbb{R} $ 盡可能大。
回想一下，當一個優化問題具有兩個獨立的屬性時，它是凸的：
- 域名_ $ \mathcal{X}\subset\mathbb{R}^n $ 是凸的。 這可以通過多種方式來表述。一是無論何時 $ x\in\mathcal{X} $ 和 $ y\in\mathcal{X} $ 和 $ 0 \le \lambda \le 1 $ , $ \lambda x + (1-\lambda)y\in\mathcal{X} $ 還。幾何上：當一條線段的兩個端點位於 $ \mathcal X $ , 整個段位於 $ \mathcal X $ .
- 功能_ $ f $ 是凸的。 這也可以通過多種方式來表述。一是無論何時 $ x\in\mathcal{X} $ 和 $ y\in\mathcal{X} $ 和 $ 0 \le \lambda \le 1 $ ,$$ f(\lambda x + (1-\lambda)y) \ge \lambda f(x) + (1-\lambda) f(y). $$（我們需要 $ \mathcal X $ 為了使這個條件有意義，是凸的。）幾何上：無論何時 $ \bar{xy} $ 是任何線段 $ \mathcal X $ , 的圖 $ f $ （僅限於此段）位於連接段的上方或之上 $ (x,f(x)) $ 和 $ (y,f(y)) $ 在 $ \mathbb{R}^{n+1} $ .
凸函數的原型是局部處處拋物線，具有非正前導係數：在任何線段上，它可以表示為 $ y\to a y^2 + b y + c $ 和 $ a \le 0. $
有困難 $ (*) $ 就是它 $ \mathcal X $ 是單位球體 $ S^{n-1}\subset\mathbb{R}^n $ ，這絕對不是凸的。 但是，我們可以通過包含更小的向量來修改這個問題。那是因為當我們擴展 $ x $ 通過一個因素 $ \lambda $ , $ f $ 乘以 $ \lambda^2 $ . 什麼時候 $ 0 \lt x^\prime x \lt 1 $ , 我們可以縮放 $ x $ 乘以單位長度 $ \lambda=1/\sqrt{x^\prime x} \gt 1 $ ，從而增加 $ f $ 但留在單位球內 $ D^n = {x\in\mathbb{R}^n\mid x^\prime x \le 1} $ . 因此，讓我們重新制定 $ (*) $ 作為
$$ \text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x\le1\tag{**} $$
它的域是 $ \mathcal{X}=D^n $ 這顯然是凸的，所以我們已經完成了一半。仍需考慮圖的凸性 $ f $ .
思考問題的好方法 $ () $ ——即使你不打算進行相應的計算——也是根據譜定理。** 它說通過正交變換 $ \mathbb P $ ，你可以找到至少一個基 $ \mathbb{R}^n $ 其中 $ \mathbb A $ 是對角線：也就是說，
$$ \mathbb {A = P^\prime \Sigma P} $$
其中所有非對角線條目 $ \Sigma $ 為零。這樣的選擇 $ \mathbb{P} $ 可以想像成什麼都沒有改變 $ \mathbb A $ ，但只是改變你描述它的方式：當你旋轉你的觀點時，函數的水平超曲面的軸 $ x\to x^\prime \mathbb{A} x $ （始終是橢圓體）與坐標軸對齊。
自從 $ \mathbb A $ 是半正定的，所有的對角線項 $ \Sigma $ 必須是非負數。 我們可以進一步置換軸（這只是另一個正交變換，因此可以吸收到 $ \mathbb P $ ) 以確保$$ \sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0. $$
如果我們讓 $ x=\mathbb{P}^\prime y $ 成為新坐標 $ x $ （包括 $ y=\mathbb{P}x $ ）， 功能 $ f $ 是
$$ f(y) = y^\prime \mathbb{A} y = x^\prime \mathbb{P^\prime A P} x = x^\prime \Sigma x = \sigma_1 x_1^2 + \sigma_2 x_2^2 + \cdots + \sigma_n x_n^2. $$
這個函數絕對不是凸的！ 它的圖形看起來像超拋物面的一部分：在內部的每個點 $ \mathcal X $ , 事實上所有的 $ \sigma_i $ 是非負的，使它向上而不是向下捲曲。
不過，我們可以轉 $ () $ 用一種非常有用的技術解決凸問題。** 知道最大值將出現在哪裡 $ x^\prime x = 1 $ ，讓我們減去常數 $ \sigma_1 $ 從 $ f $ ，至少對於邊界上的點 $ \mathcal{X} $ . 這不會改變邊界上任何點的位置 $ f $ 被優化，因為它降低了所有的值 $ f $ 在邊界上相同的值 $ \sigma_1 $ . 這建議檢查函數
$$ g(y) = f(y) - \sigma_1 y^\prime y. $$
這確實減去了常數 $ \sigma_1 $ 從 $ f $ 在邊界點，並在內部點減去較小的值。 這將確保 $ g $ ， 相比 $ f $ , 內部沒有新的全局最大值 $ \mathcal X $ .
讓我們來看看這個替換的花招發生了什麼 $ -\sigma_1 $ 經過 $ -\sigma_1 y^\prime y $ . 因為 $ \mathbb P $ 是正交的， $ y^\prime y = x^\prime x $ . （這實際上是正交變換的定義。）因此，就 $ x $ 坐標， $ g $ 可以寫
$$ g(y) = \sigma_1 x_1 ^2 + \cdots + \sigma_n x_n^2 - \sigma_1(x_1^2 + \cdots + x_n^2) = (\sigma_2-\sigma_1)x_2^2 + \cdots + (\sigma_n - \sigma_1)x_n^2. $$
因為 $ \sigma_1 \ge \sigma_i $ 對所有人 $ i $ ，每個係數為零或負數。 因此，(a) $ g $ 是凸的並且 (b) $ g $ 優化時 $ x_2=x_3=\cdots=x_n=0 $ . ( $ x^\prime x=1 $ 那麼意味著 $ x_1=\pm 1 $ 並且當達到最優時 $ y = \mathbb{P} (\pm 1,0,\ldots, 0)^\prime $ ，這是 - 直到簽署 - 的第一列 $ \mathbb P $ .)
讓我們概括一下邏輯。 因為 $ g $ 在邊界上優化 $ \partial D^n=S^{n-1} $ 在哪裡 $ y^\prime y = 1 $ ， 因為 $ f $ 不同於 $ g $ 僅僅由常數 $ \sigma_1 $ 在那個邊界上，並且因為 $ g $ 更接近於價值 $ f $ 在的內部 $ D^n $ , 最大值 $ f $ 必須與最大值一致 $ g $ .
