隨機向量範數的集中(concentration of the norm)
範數集中是高維幾何的第一個、也最鮮明的驚奇:具獨立次高斯座標的隨機向量並不把其長度攤開,反而其歐氏範數緊緊集中在 sqrt(n) 附近,本質上活在一層薄薄的球殼上。這個「薄殼現象」正是高維直覺與低維圖像如此天差地別的原因,也是隨機投影、最近鄰方法與資料雲幾何背後的引擎。
設 X = (X_1, ..., X_n) 具獨立、零均值、單位變異數的次高斯座標,psi_2 範數至多為 K。則 E[||X||_2^2] = sum E[X_i^2] = n,故典型長度為 sqrt(n)。集中陳述是 ||X||_2 本身(而非其平方)集中:||X||_2 - sqrt(n) 為次高斯,其變異數代理「不」隨 n 增長,對所有 t >= 0,P(| ||X||_2 - sqrt(n) | >= t) <= 2 exp(-c t^2 / K^4)。範數的偏差為 O(1),與維度無關——因此相對波動 ||X||/sqrt(n) - 1 為 1/sqrt(n) 量級並趨於零。證明是乾淨的兩步:首先 ||X||_2^2 = sum X_i^2 是獨立次指數變數之和(每個 X_i^2 均值為 1),故由 Bernstein 它以偏差 O(sqrt(n)) 集中在 n 附近;接著不等式 | ||X|| - sqrt(n) | <= |||X||^2 - n| / sqrt(n) 把平方的 O(sqrt(n)) 偏差轉成範數的 O(1) 偏差。平方根正是馴服波動者。
其後果在資料科學中俯拾即是。在大 n 的 R^n 中,球的幾乎全部體積都靠近其表面,高斯的幾乎全部質量都靠近半徑 sqrt(n) 的球面,而兩個獨立的高維高斯向量幾乎正交,其內積為 sqrt(n) 量級而長度為 n 量級。這些事實是 Johnson-Lindenstrauss 引理與隨機特徵成功的基礎。誠實的提醒:乾淨的 sqrt(n) 集中需要座標為次高斯(或至少 X_i^2 為一致受控的次指數);對於重尾座標,薄殼可能失效或變寬,而獨立性假設要緊——強相依的座標不一定集中,這正是一般對數凹向量之「薄殼猜想」(仍部分未解)的內容。
在維度 n = 10000 抽取 X ~ N(0, I_n)。則 ||X||_2 集中在 100 = sqrt(10000) 附近、波動為 1 量級(事實上 ||X||/sqrt(n) 以壓倒性機率落在 1 的 1% 之內)。兩個獨立的這類向量 X、Y 之 cos(夾角) = <X,Y>/(||X|| ||Y||) 為 1/sqrt(n) ~ 0.01 量級——它們幾乎恰好正交。
高維向量活在半徑 sqrt(n) 的薄殼上且幾乎正交。
偏差為 O(1)、無維度者是「範數」(而非其平方);平方範數偏差為 O(sqrt(n))。這需要次高斯、獨立的座標——重尾或強相依(薄殼猜想領域)可能破壞它。