矩陣 Bernstein 不等式（matrix Bernstein inequality）
/ BERN-shtine /
矩陣 Bernstein 不等式是把純量集中推廣到「獨立隨機矩陣」之和，它控制這類和偏離其均值的算子範數（最大奇異值）。它是現代應用機率中最有用的結果之一，因為如此多的高維對象都是獨立矩陣之和——樣本共變異數矩陣、隨機圖的圖拉普拉斯、由隨機量測重建的矩陣、隨機化矩陣草圖——而人們幾乎總想知道隨機和的譜接近其期望的譜。
陳述如下：設 S = sum_k X_k 為獨立、零均值的 d×d（厄米）隨機矩陣之和，每個矩陣的算子範數幾乎必然 ||X_k|| <= L。定義矩陣變異數參數 v = || sum_k E[X_k^2] ||（二階動差矩陣之和的算子範數）。則對所有 t >= 0，P(||S|| >= t) <= 2d exp(-t^2 / (2(v + Lt/3)))。其結構正是純量 Bernstein——小 t 的高斯區段 exp(-t^2 / 2v) 與大 t 的指數區段 exp(-3t / 2L)——但有兩個關鍵差異。變異數現在是一個矩陣 v 的「算子範數」，捕捉二階動差散布的最壞方向，且前面有顯式的「維度」前因子 2d。那個 d 是非交換性的代價：證明以矩陣指數的跡 E[tr exp(lambda S)] 取代純量動差母函數 E[e^(lambda S)]，並使用深刻的 Lieb 凹性定理（矩陣類比，讓你儘管矩陣不交換仍能以乘積結構界定 E[tr exp(lambda S)]）加上跡不等式 tr exp(A) <= d * lambda_max(exp(A))。d 出現是因為算子範數是 d 個特徵值上的最大值，而對它們取聯集界的風味殘留下來。
讀作樣本複雜度陳述，矩陣 Bernstein 說：n 個範數至多為 L 的獨立零均值矩陣之和，集中在其均值的約 sqrt(v log d) + L log d 之內——log d 是維度留下的唯一痕跡，這正是這些界被稱為「近乎無維度」的原因，也是它們如此強大的原因：d 維中的隨機矩陣集中得幾乎和純量一樣好，只付一個對數的維度通行費。誠實的提醒。log d 因子是真實的，一般無法去除；它使矩陣 Bernstein 對於「內在維度遠小於 d」的問題略有損耗，此時內在維度精煉（以「穩定秩」tr(sum E[X_k^2])/v 取代 d）給出更尖銳的界。此形式需要幾乎必然的範數界 L；無界被加項需要矩陣次指數／截斷論證。而矩陣 Bernstein 控制「偏差」的算子範數，而非個別特徵值——要使最小特徵值保持為正（共變異數估計、矩陣補全），可對 S 套用並讀出兩端。
從 n 個獨立同分布樣本 x_i（||x_i|| <= sqrt(d)）估計共變異數矩陣 Sigma（d×d）。經驗共變異數為 (1/n) sum x_i x_i^T，是獨立秩一矩陣之和。矩陣 Bernstein 給出 || 經驗 Sigma - Sigma || <= O(sqrt(||Sigma|| d log d / n) + d log d / n)，故 n ~ d log d 個樣本即足以得到良好的算子範數估計——log d 是唯一的維度開銷。
隨機矩陣集中得幾乎和純量一樣好，只付 log d 的通行費。
維度前因子（界中的 log d）是真實的；對於低內在維度問題，以穩定秩取代 d 可得更尖銳的界。此不等式需要幾乎必然的算子範數界 L；它控制偏差的算子範數，而非直接控制個別特徵值。