矩陣 Chernoff 不等式（matrix Chernoff inequality）

矩陣 Chernoff 不等式控制獨立、半正定隨機矩陣之和的極端「特徵值」——最小與最大者。矩陣 Bernstein 界定零均值偏差的算子範數，而矩陣 Chernoff 是針對半正定和的工具，當你關心的是隨機和保持良態：其最小特徵值不塌縮到零（故和可逆／矩陣滿秩）且其最大特徵值不爆掉。這是非負有界變數之和的純量 Chernoff 界的矩陣類比。

陳述如下：設 X_1、…、X_n 為獨立、半正定的 d×d 隨機矩陣，每個幾乎必然 ||X_k|| <= L，並令 S = sum_k X_k、均值矩陣 M = E[S]。記 mu_min = lambda_min(M)、mu_max = lambda_max(M) 為期望和的極端特徵值。則最小特徵值滿足，對 eps in [0,1)，P(lambda_min(S) <= (1 - eps) mu_min) <= d * (e^(-eps) / (1-eps)^(1-eps))^(mu_min / L)，而最大特徵值滿足，對 eps >= 0，P(lambda_max(S) >= (1 + eps) mu_max) <= d * (e^(eps) / (1+eps)^(1+eps))^(mu_max / L)。指數 (e^(-eps)/(1-eps)^(1-eps)) 及其兄弟恰是純量 Chernoff 指數；唯一的矩陣開銷又是維度前因子 d。證明遵循與矩陣 Bernstein 相同的跡-動差母函數／Lieb 凹性機器，但為半正定矩陣量身打造，此時可取單邊指數並直接讀出特徵值界。與矩陣 Bernstein 一樣，維度只透過因子 d 進入，故界又近乎無維度：大致上，lambda_min(S) >= mu_min - O(sqrt(L mu_min log d)) 且 lambda_max(S) <= mu_max + O(sqrt(L mu_max log d))。

致命的應用是譜的。矩陣 Chernoff 是證明以下事項的標準工具：隨機圖的拉普拉斯良態（譜稀疏化：以正確機率抽樣邊所稀疏化的圖保持譜，這正是快速拉普拉斯求解器的動力）、矩陣列的隨機樣本構成良好的子空間嵌入（行子集選取、槓桿分數抽樣），以及獨立秩一外積之和滿秩。誠實的提醒與矩陣 Bernstein 平行。此界需要被加項為半正定且算子範數一致受 L 界；每個不等式是單邊的，而最小特徵值界在 mu_min / L 小時降級——該比值是有效的「每維度樣本數」，要控制最小特徵值你確實需要 mu_min >= L log d，這正是譜稀疏化與槓桿分數抽樣中須以 log d 因子過抽樣的嚴格原因。維度的 log d 又是真實的，只能降到內在維度為止。