PCA 優化是凸的嗎？

主成分分析 (PCA) 的目標函數是最小化 L2 範數中的重構誤差（請參見此處的第 2.12 節。另一種觀點是試圖最大化投影方差。我們在這裡也有一篇很好的帖子：什麼是 PCA 的目標函數? )。

我的問題是PCA 優化是凸的嗎？（我在這裡找到了一些討論，但希望有人可以在簡歷上提供一個很好的證明）。

不，PCA 的常用公式不是凸問題。 但它們可以轉化為凸優化問題。

其洞察力和樂趣在於跟踪和可視化轉換的順序，而不僅僅是獲得答案：它在於旅程，而不是目的地。這段旅程的主要步驟是

1. 獲得目標函數的簡單表達式。
2. 將其非凸的域擴大為一個。
3. 將非凸目標修改為凸目標，其方式顯然不會改變其達到最佳值的點。

如果你密切關注，你可以看到潛伏的 SVD 和拉格朗日乘數——但它們只是一個小插曲，只是為了風景，我不會進一步評論它們。

---

PCA （或至少其關鍵步驟）的標準方差最大化公式是

Maximize f(x)= x′Ax  subject to  x′x=1

在哪裡 n×n 矩陣 A 是從數據（通常是其平方和乘積矩陣、協方差矩陣或相關矩陣）構造的對稱半正定矩陣。

（等效地，我們可以嘗試最大化無約束目標 x′Ax/x′x . 這不僅是一個更糟糕的表達式——它不再是一個二次函數——而且繪製特殊情況很快就會表明它也不是一個凸函數。通常人們觀察到這個函數在重新縮放下是不變的 x→λx 然後將其簡化為受約束的公式 (∗) .)

任何優化問題都可以抽像地表述為

至少找到一個 x∈X 這使得函數 f:X→R 盡可能大。

回想一下，當一個優化問題具有兩個獨立的屬性時，它是凸的：

1. 域名_ X⊂Rn 是凸的。 這可以通過多種方式來表述。一是無論何時 x∈X 和 y∈X 和 0≤λ≤1 , λx+(1−λ)y∈X 還。幾何上：當一條線段的兩個端點位於 X , 整個段位於 X .
2. 功能_ f 是凸的。 這也可以通過多種方式來表述。一是無論何時 x∈X 和 y∈X 和 0≤λ≤1 ,f(λx+(1−λ)y)≥λf(x)+(1−λ)f(y).
   （我們需要 X 為了使這個條件有意義，是凸的。）幾何上：無論何時 ¯xy 是任何線段 X , 的圖 f （僅限於此段）位於連接段的上方或之上 (x,f(x)) 和 (y,f(y)) 在 Rn+1 .

凸函數的原型是局部處處拋物線，具有非正前導係數：在任何線段上，它可以表示為 y→ay2+by+c 和 a≤0.

有困難 (∗) 就是它 X 是單位球體 Sn−1⊂Rn ，這絕對不是凸的。 但是，我們可以通過包含更小的向量來修改這個問題。那是因為當我們擴展 x 通過一個因素 λ , f 乘以 λ2 . 什麼時候 0<x′x<1 , 我們可以縮放 x 乘以單位長度 λ=1/√x′x>1 ，從而增加 f 但留在單位球內 Dn=x∈Rn∣x′x≤1 . 因此，讓我們重新制定 (∗) 作為

Maximize f(x)= x′Ax  subject to  x′x≤1

它的域是 X=Dn 這顯然是凸的，所以我們已經完成了一半。仍需考慮圖的凸性 f .

思考問題的好方法 $ () ——即使你不打算進行相應的計算——也是根據譜定理。∗∗它說通過正交變換 \mathbb P ，你可以找到至少一個基 \mathbb{R}^n 其中 \mathbb A $ 是對角線：也就是說，

A=P′ΣP

其中所有非對角線條目 Σ 為零。這樣的選擇 P 可以想像成什麼都沒有改變 A ，但只是改變你描述它的方式：當你旋轉你的觀點時，函數的水平超曲面的軸 x→x′Ax （始終是橢圓體）與坐標軸對齊。

自從 A 是半正定的，所有的對角線項 Σ 必須是非負數。 我們可以進一步置換軸（這只是另一個正交變換，因此可以吸收到 P ) 以確保σ1≥σ2≥⋯≥σn≥0.

如果我們讓 x=P′y 成為新坐標 x （包括 y=Px ）， 功能 f 是

f(y)=y′Ay=x′P′APx=x′Σx=σ1x21+σ2x22+⋯+σnx2n.

這個函數絕對不是凸的！ 它的圖形看起來像超拋物面的一部分：在內部的每個點 X , 事實上所有的 σi 是非負的，使它向上而不是向下捲曲。

不過，我們可以轉 $ () 用一種非常有用的技術解決凸問題。∗∗知道最大值將出現在哪裡 x^\prime x = 1 $ ，讓我們減去常數 σ1 從 f ，至少對於邊界上的點 X . 這不會改變邊界上任何點的位置 f 被優化，因為它降低了所有的值 f 在邊界上相同的值 σ1 . 這建議檢查函數

g(y)=f(y)−σ1y′y.

這確實減去了常數 σ1 從 f 在邊界點，並在內部點減去較小的值。 這將確保 g ， 相比 f , 內部沒有新的全局最大值 X .

讓我們來看看這個替換的花招發生了什麼 −σ1 經過 −σ1y′y . 因為 P 是正交的， y′y=x′x . （這實際上是正交變換的定義。）因此，就 x 坐標， g 可以寫

g(y)=σ1x21+⋯+σnx2n−σ1(x21+⋯+x2n)=(σ2−σ1)x22+⋯+(σn−σ1)x2n.

因為 σ1≥σi 對所有人 i ，每個係數為零或負數。 因此，(a) g 是凸的並且 (b) g 優化時 x2=x3=⋯=xn=0 . ( x′x=1 那麼意味著 x1=±1 並且當達到最優時 y=P(±1,0,…,0)′ ，這是 - 直到簽署 - 的第一列 P .)

讓我們概括一下邏輯。 因為 g 在邊界上優化 ∂Dn=Sn−1 在哪裡 y′y=1 ， 因為 f 不同於 g 僅僅由常數 σ1 在那個邊界上，並且因為 g 更接近於價值 f 在的內部 Dn , 最大值 f 必須與最大值一致 g .

引用自：https://stats.stackexchange.com/questions/301532