I4 · 관측 수와 함께 커지는 공분산 행렬#
상관이 없는 자산에서도 표본 고윳값은 퍼진다#
\(p\)개 자산의 수익률을 모집단 표준편차로 나누어 무차원 벡터 \(X_i\)로 만들었다고 하자. 교육용 모형으로 \(X_i\overset{\rm iid}{\sim}N(0,I_p)\), 알려진 모집단 평균 0을 가정합니다. \(n\)기간의 표본공분산은
여기서 자료행렬 \(X\)는 \(n\times p\)입니다. 모든 모집단 고윳값은 1이지만 표본 고윳값은 같지 않습니다. 더구나 \(p>n\)이면 rank가 최대 \(n\)이므로 적어도 \(p-n\)개 고윳값은 정확히 0입니다. 표본평균을 추정하여 중심화하면 최대 rank는 \(n-1\)로 바뀝니다. 이 장의 실험은 평균 0을 알고 있는 식을 사용합니다.
한 방향 \(u\)를 미리 고정하면 \(u^T\widehat\Sigma u=n^{-1}\sum(u^TX_i)^2\)의 평균은 \(\|u\|^2\)이고 분산은 \(2\|u\|^4/n\)입니다. 그러나 자료를 본 뒤 가장 큰 값을 주는 \(u\)를 고르면 질문이 달라집니다. 모든 방향을 동시에 통제하는 비용이 차원과 함께 커집니다. 고차원 확률은 이 차이를 정량화합니다.
그림 170 곡선은 극한 밀도이며 유한표본 히스토그램이 아니다. \(\gamma=p/n=2\)의 연속 부분은 질량 \(1/2\)만 갖고, 아래 별도 패널의 막대가 0에서의 나머지 질량 \(1/2\)를 표시한다. 밀도 높이와 원자 확률은 단위가 달라 같은 세로축에 놓지 않는다.#
정규분포와 비슷한 꼬리라는 조건#
실수 확률변수의 두 크기를
로 정의합니다. 유한 \(\psi_2\) 노름은 부가우시안, 유한 \(\psi_1\) 노름은 부지수라는 이름을 갖습니다. \(Z=\pm1\)인 Rademacher는 \(e^{1/K^2}\le2\)에서 \(\|Z\|_{\psi_2}=1/\sqrt{\log2}\). 표준정규는 Gaussian 적분으로 \(Ee^{Z^2/K^2}=(1-2/K^2)^{-1/2}\), 따라서 노름은 \(\sqrt{8/3}\)입니다. 유계변수만 부가우시안인 것은 아닙니다.
정의만 비교해도
입니다. 공분산을 추정할 때 합하는 것은 \(Z\)가 아니라 \(Z^2\) 또는 서로 다른 좌표의 곱입니다. \(2|XY|\le aX^2+a^{-1}Y^2\)와 Cauchy–Schwarz로 \(\|XY\|_{\psi_1}\le\|X\|_{\psi_2}\|Y\|_{\psi_2}\)도 얻습니다. 두 좌표의 독립성은 이 부등식에 필요하지 않습니다.
\(Z^2-1\)의 MGF는
\(t\ge1/2\)에는 유한하지 않습니다. 그래서 모든 \(t\)에 Gaussian MGF 경계를 요구할 수 없고, 작은 편차의 제곱 지수와 큰 편차의 일차 지수를 함께 가진 Bernstein 형태가 필요합니다. 예컨대 독립 평균 0 변수 \(W_i\)가 \(\|W_i\|_{\psi_1}\le L\)이면 뒤에서 직접 증명하는 경계는
상수는 날카롭게 최적화하지 않았지만 완전히 명시했습니다. 금융자료의 두꺼운 꼬리가 이 가정을 만족하는지는 별도의 모형 검토입니다.
한 방향에서 모든 방향으로 가는 유한 망#
단위구면의 모든 점이 거리 \(\epsilon\) 이내의 어떤 망점과 연결되도록 유한집합 \(\mathcal N\)을 잡습니다. 서로 \(\epsilon\) 이상 떨어진 점을 더 이상 추가할 수 없을 때까지 고르면 \(\epsilon/2\) 공들이 서로 겹치지 않고 반지름 \(1+\epsilon/2\)의 공 안에 있습니다. 부피를 비교하면
대칭행렬 \(A\)에 \(\|x\|=\|u\|=1\), \(\|x-u\|\le\epsilon\)이면
따라서 \(\epsilon<1/2\)에서 \(\|A\|\le(1-2\epsilon)^{-1}\max_{u\in\mathcal N}|u^TAu|\). \(\epsilon=1/4\)면 배수는 2, 망점 수는 최대 \(9^p\)입니다. 합집합 경계에서 바로 이 \(p\log9\)가 발생합니다. 이를 근거 없이 유효차원 \(r\)로 바꿀 수 없습니다.
구체적으로 평균 0 벡터에
라는 공분산에 대한 상대적 부가우시안 조건을 가정하자. 표본은 독립 동일분포입니다. \(L=2K^2\|\Sigma\|\), \(a=p\log9+\log(2/\eta)\)라 두면 확률 \(1-\eta\) 이상에서
이것은 이번 장에서 완전히 증명하는 명시적 차원 \(p\) 경계입니다. 제곱근 항은 작은 편차 체제, 일차항은 큰 편차 체제에서 옵니다.
유효차원 \(r=\operatorname{tr}\Sigma/\|\Sigma\|\)가 \(p\)보다 훨씬 작을 수 있습니다. 독립 centered Gaussian 표본에서는 보편상수 \(C\)에 대해 확률 \(1-e^{-u}\) 이상으로
라는 더 정교한 결과가 있습니다. 이 결과는 단순한 구면 망 논법을 넘어서는 외부 Gaussian 공분산 정리로 인용합니다. 상수 \(C\)를 수치적으로 특정하지 않았으므로 이를 이용해 “정확히 \(n\)개면 90% 보장” 같은 숫자를 만들어내지 않습니다. Koltchinskii–Lounici의 원논문은 이 유효랭크 의존성을 분석합니다.
\(k\)개 고윳값이 \(pc\), 나머지가 1이면 \(r=[kpc+(p-k)]/(pc)=k+(p-k)/(pc)\). \(p\to\infty\)에서 \(k+1/c\)로 가므로 \(k\)에 무조건 수렴하지 않습니다. \(pc\)가 커질수록 상대오차에는 유리해도 절대오차의 앞 인자 \(\|\Sigma\|=pc\)는 커집니다. 상관이 커질수록 절대 추정오차가 반드시 줄어든다는 해석도 피해야 합니다.
이차형식과 행렬 합의 두 척도#
Gaussian \(z\sim N(0,I)\), 대칭 \(A\)에서는 \(Q=z^TAz-\operatorname{tr}A\)입니다. 직교대각화하면 \(Q=\sum\lambda_j(z_j^2-1)\). 뒤에서 MGF를 전개하여
를 증명합니다. \(A=I_p\)이면 두 척도는 \(\sqrt p,1\), rank 1 사영이면 \(1,1\)입니다. 같은 작용소노름을 가져도 누적되는 독립 방향의 수가 다릅니다.
독립 평균 0 부가우시안 좌표로 확장한 Hanson–Wright 부등식은 보편상수 \(c>0\)에
이며 여기서는 외부 정리로 인용합니다. 대각항은 Bernstein으로 처리할 수 있지만 비대각항은 좌표쌍끼리 겹쳐 독립합이 아니므로 별도의 decoupling 논증이 필요합니다. Gaussian의 직교회전 후 독립성을 일반 좌표에 그대로 적용할 수 없습니다. 참고는 Vershynin의 교재입니다.
또 다른 도구인 행렬 Bernstein은 독립 평균 0 자기수반 \(S_i\)에 \(\|S_i\|\le L\) a.s., \(v=\|\sum E S_i^2\|\)일 때
를 줍니다. \(d\)는 행렬 크기입니다. 비가환 MGF 정리는 Tropp의 원논문의 외부 전제로 두고, 사용에 필요한 값을 계산해 보겠습니다. \(S_i=\xi_iA\), \(\xi_i=\pm1\) 독립이면 \(L=\|A\|\), \(v=n\|A^2\|=n\|A\|^2\)입니다. 반면 Gaussian \(X_iX_i^T-\Sigma\)는 a.s. 유계가 아니므로 이 버전에 유한한 \(L\)을 그냥 대입할 수 없습니다. 절단 오차를 따로 통제하거나 위 부지수 망 논법을 사용해야 합니다.
Marchenko–Pastur: 두 Stieltjes 변환을 구분하기#
\(X\)의 원소가 독립 표준정규이고 \(p/n\to\gamma\in(0,\infty)\)일 때 표본공분산의 경험 스펙트럼은 Marchenko–Pastur 법칙으로 약수렴합니다. 그 확률극한 정리는 원논문의 외부 전제로 쓰고, 법칙을 읽는 대수는 여기서 전개합니다.
\(S=X^TX/n\)의 정규화 resolvent와 \(C=XX^T/n\)의 companion을
로 정의합니다. 두 행렬의 비영 고윳값은 같고 0의 개수만 다르므로 정확히
극한 companion \(q=\underline m\)가 만족하는 식은
이 식을 \(m\)의 식이라고 쓰면 모수 위치를 잘못 읽습니다. \(q=\gamma m-(1-\gamma)/z\)를 넣으면
무한대에서 \(m(z)\sim-1/z\), 상반평면에서 \(\operatorname{Im}m>0\)인 가지를 고릅니다. \(a=(1-\sqrt\gamma)^2,b=(1+\sqrt\gamma)^2\)라 쓰면
제곱근은 무한대에서 \(z\)처럼 되는 해석적 가지입니다. 경계의 허수부를 \(\pi\)로 나누어 얻는 밀도는
그리고 \(\gamma>1\)이면 0에 원자 \(1-1/\gamma\)가 붙습니다. \(\gamma=2\)의 절반 원자는 처음의 rank 계산과 일치합니다.
companion 식이 나타나는 위치도 살펴봅시다. \(C=\sum_{j=1}^pr_jr_j^T\), \(r_j=X_{\cdot j}/\sqrt n\)이고 \(C_{-j}=C-r_jr_j^T\)라 하면 Sherman–Morrison으로
\(C(C-zI)^{-1}=I+z(C-zI)^{-1}\)의 trace를 \(n\)으로 나누면 \(1+z\underline m_n=n^{-1}\sum q_j/(1+q_j)\)입니다. \(r_j\)가 제거된 resolvent와 독립이어서 \(q_j\)를 그 정규화 trace로 근사하는 것이 확률적 핵심입니다. 이 근사와 극한 교환을 정당화하는 부분은 명시한 외부 MP 정리에 맡깁니다. 그 뒤 \(q_j\to q\)를 대입하면 \(1+zq=\gamma q/(1+q)\), 즉 표시한 자기일관 식이 나옵니다. 유한 rank-one 항등식 자체와 확률극한의 정당화를 구분했습니다.
큰 고윳값 하나가 신호를 드러내는 조건#
\(\Sigma=I+\theta vv^T\), \(\|v\|=1\), \(\theta>0\)인 Gaussian 스파이크 모형에서 모집단 첫 고윳값은 \(1+\theta\)입니다. \(0<\gamma<1\)로 고정한 고차원 극한에서 외부 스파이크 정리는
를 줍니다. Paul의 Gaussian 스파이크 연구를 인용한 결과이며 이 장에서 일반 BBP 보편성까지 증명하는 것은 아닙니다. \(\gamma=1/2,\theta=1\)이면 모집단 고윳값 2가 표본에서 3으로, 방향의 제곱상관은 \(1/3\)으로 갑니다. 표본 수가 무한히 커져도 차원이 비례해서 늘면 방향오차가 사라지지 않습니다. 유한표본에서 모든 표본 고윳값이 항상 모집단 고윳값보다 크다는 명제는 이 극한식과 다릅니다.
그림 171 점선 수직선은 \(\theta=\sqrt{1/2}\)다. 위에서 관측되는 고윳값의 분리와 아래에서 회복되는 방향 정보를 함께 읽는다. 선은 외부 정리의 극한 공식이며 Monte Carlo 평균으로 표시하지 않는다.#
유한표본 PCA는 다른 방식으로 인증할 수 있습니다. 모집단 간극 \(\Delta=\lambda_k(\Sigma)-\lambda_{k+1}(\Sigma)>0\), 오차 \(e=\|\widehat\Sigma-\Sigma\|<\Delta/2\)이면 H6의 분리된 스펙트럼 경계로
상위 모집단·표본 공간이라는 한쪽 스펙트럼 분리 조건이 충족되어야 합니다. 위 공분산 경계 \(b_n\)가 \(\Delta/2\)보다 작으면 같은 확률로 \(2b_n/\Delta\)를 보장합니다. Gaussian 유효차원 결과를 외부 전제로 쓰면 \(\|\Sigma\|[\sqrt{r/n}+r/n]/\Delta\to0\)이 충분조건입니다. \(k\)가 고정된 강한 요인, 고윳값 \(O(p)\), 간극이 \(p\)에 비례하고 잔여 고윳값이 유계이면 \(r=O(1)\)라서 상대오차가 줄 수 있습니다. 시점의 독립성을 잃는 시계열 요인모형에는 별도 의존자료 집중정리가 필요합니다.
스케치가 보존해야 하는 것은 잔차공간이다#
\(R\in\mathbb R^{m\times d}\)의 원소를 독립 \(N(0,1/m)\)로 뽑습니다. 고정 벡터 \(x\ne0\)에 \(\|Rx\|^2/\|x\|^2\)는 \(\chi_m^2/m\). 따라서 \(0<\epsilon<1\)에서
\(N\)개 점의 모든 쌍에 합집합 경계를 적용하면 \(m\ge8\epsilon^{-2}\log(N(N-1)/\eta)\)로 제곱거리가 동시에 \(1\pm\epsilon\) 안에 들어갑니다. 이것이 Gaussian Johnson–Lindenstrauss 보장입니다. 유한 점 쌍의 보존과 부분공간 전체의 보존은 다른 사건입니다.
\(k\)차원 부분공간의 정규직교기저 \(U\)에 앞의 \(1/4\)-망을 적용하면
에서 \(\|U^TR^TRU-I\|\le\epsilon\)입니다. least squares에서는 \(\operatorname{col}[A,b]\) 전체를 보존해야 모든 잔차 \(Ax-b\)를 다룰 수 있습니다. 스케치 해 \(\widetilde x\)와 원래 해 \(x^*\)에
이 순서로 목적함수 보장이 나옵니다. 계수오차까지 원하면 \(A\)의 최소특이값이 필요합니다. 보고할 것은 시드, \(m\), 적용 공간, 원래 잔차, 성공확률과 사용한 오차 정의입니다.
역행렬 위험과 이중강하의 제한된 예#
작은 표본 고윳값은 역공분산과 최소제곱에서 크게 증폭됩니다. \(X\)를 고정하고 \(y=X\beta+\varepsilon\), \(E[\varepsilon\varepsilon^T\mid X]=\sigma^2I\)라 합시다. full column rank이면 \(E[\|\widehat\beta-\beta\|^2\mid X]=\sigma^2\sum_j s_j(X)^{-2}\). 능형의 각 특이방향 분산은 \(\sigma^2s_j^2/(s_j^2+\lambda)^2\)여서 작은 \(s_j\)의 폭발을 줄입니다.
특히 \(\beta=0\), 독립 표준정규 설계와 독립 등방 새 입력에서 최소노름 회귀의 기대 예측초과위험은
이는 Wishart 역평균 \(E(W^{-1})=I/(\nu-d-1)\)를 외부 확률 전제로 사용한 결과입니다. 중간 영역에서는 해당 평균이 발산합니다. 유한 Monte Carlo에서 큰 값이 나오는 것과 무한 기대값은 구분해야 합니다. 비영 신호에는 과모수화 구간에서 영공간 편향이 추가되며, 차원을 바꾸는 동안 신호를 어떻게 유지할지도 지정해야 합니다.
그림 172 \(n=100\), \(\sigma^2=1\), 참계수 0이라는 명시적 모형의 기대 초과위험이다. \(p\in\{99,100,101\}\)에는 기대값이 무한하여 곡선을 연결하지 않는다. 이는 모든 자료에서의 보편적 이중강하나 실제 교차검증의 성능을 주장하는 그림이 아니다.#
import numpy as np
rng=np.random.default_rng(440)
for n,p in [(160,80),(80,160)]:
X=rng.normal(size=(n,p)); S=X.T@X/n
eig=np.linalg.eigvalsh(S)
zeros=np.count_nonzero(abs(eig)<1e-10)
assert zeros==max(0,p-n)
print('n,p,zero count,largest:',n,p,zeros,eig[-1])
# Finite rank-one resolvent identity, checked without an asymptotic claim.
X=rng.normal(size=(20,30)); C=X@X.T/20; z=1+2j
r=X[:,0]/np.sqrt(20); Cminus=C-np.outer(r,r)
q=r@np.linalg.solve(Cminus-z*np.eye(20),r)
assert np.allclose(r@np.linalg.solve(C-z*np.eye(20),r),q/(1+q))
n,p,zero count,largest: 160 80 0 2.792036961861533
n,p,zero count,largest: 80 160 80 5.5456614675908575
n,d,m=180,6,80
A=rng.normal(size=(n,d)); b=rng.normal(size=n)
R=rng.normal(size=(m,n))/np.sqrt(m)
x=np.linalg.lstsq(A,b,rcond=None)[0]
xt=np.linalg.lstsq(R@A,R@b,rcond=None)[0]
U=np.linalg.qr(np.column_stack([A,b]),mode='reduced')[0]
eps=np.linalg.norm(U.T@R.T@R@U-np.eye(d+1),2)
ratio=np.linalg.norm(A@xt-b)**2/np.linalg.norm(A@x-b)**2
assert eps<1 and ratio<=(1+eps)/(1-eps)+1e-12
print('measured embedding distortion:',eps,'squared residual ratio:',ratio)
measured embedding distortion: 0.7749085978210117 squared residual ratio: 1.030172004260313
연습문제와 전체 풀이#
1. 제곱의 꼬리. 표준정규 \(Z\)에 \(\|Z\|_{\psi_2}\)와 \(\|Z^2\|_{\psi_1}\)를 구하고 \(Z^2-1\)이 부가우시안인지 판정하라.
풀이. Gaussian 적분에서 각각 \(\sqrt{8/3}\)와 \(8/3\)입니다. 중심화한 제곱의 MGF는 \(t=1/2\)에서 발산하므로 모든 실수 \(t\)에 \(Ee^{t(Z^2-1)}\le e^{Ct^2}\)인 부가우시안 경계를 만족할 수 없습니다. 부지수 합의 Bernstein을 적용하는 것이 적절합니다.
2. 유효차원 계산. \(p=500\), \(k=3\), \(c=2\)인 강한 요인 스펙트럼의 \(r\)을 계산하라.
풀이. 상위 고윳값은 1000 세 개, 나머지 497개는 1입니다. \(r=(3000+497)/1000=3.497\). \(p\)보다 훨씬 작지만 정확히 3은 아닙니다. 상대오차의 유효차원 이득과 앞 인자 \(\|\Sigma\|=1000\)을 함께 해석해야 합니다.
3. Stieltjes의 부호와 정규화. \(\gamma=2\)에서 companion과 원래 변환의 관계를 쓰고 0 질량을 설명하라.
풀이. \(q=2m+1/z\). \(p=2n\)일 때 \(S\)는 \(n\)개 0을 더 가지므로 \(m=(q-1/z)/2\)입니다. \(-1/(2z)\)가 0 원자 \(1/2\)의 Stieltjes 항입니다. \(z=-1/q+2/(1+q)\)를 \(m\) 자체의 방정식이라고 읽으면 이 원자와 평균 정규화를 혼동합니다.
4. 신호와 표본 방향. \(\gamma=1/2\), \(\theta=1/2\)와 \(1\)을 비교하라.
풀이. 임계값은 \(\sqrt{1/2}\approx.7071\). \(\theta=.5\)는 임계 아래여서 최대고윳값 극한은 \((1+\sqrt{.5})^2\approx2.9142\), 제곱상관은 0입니다. \(\theta=1\)은 최대고윳값 3, 제곱상관 \((1-.5)/(1+.5)=1/3\). 신호를 검출하는 것과 방향을 일치추정하는 것은 다릅니다.
5. 망 논법의 오류 찾기. \(9^p\)개 망점을 사용한 합집합 경계에서 \(p\)를 \(\operatorname{tr}\Sigma/\|\Sigma\|\)로 대체한 증명을 비판하라.
풀이. 합집합 확률은 \(2\cdot9^p e^{-a}\)이며 이를 \(\eta\) 이하로 하려면 \(a\ge p\log9+\log(2/\eta)\). 고윳값이 작은 방향이 많다는 사실만으로 유클리드 단위구면의 망점 수가 \(9^r\)로 줄지 않습니다. 공분산에 따른 비등방 기하 또는 더 강한 확률과정 정리가 필요합니다. 그래서 본문은 \(p\) 버전을 증명하고 Gaussian \(r\) 버전은 외부 정리로 분리했습니다.
6. 스케치 목적함수와 계수. full column rank \(A\)에서 잔차비가 \(c\ge1\) 이하이면 계수오차를 어떻게 제한하는가?
풀이. 원래 최소제곱의 직교성으로 \(\|A\widetilde x-b\|^2=\|Ax^*-b\|^2+\|A(\widetilde x-x^*)\|^2\). 따라서 \(\|\widetilde x-x^*\|\le\sqrt{c-1}\|Ax^*-b\|/s_{\min}(A)\). 작은 최소특이값에서는 좋은 잔차비가 좋은 계수오차를 보장하지 않습니다. rank가 부족하면 영공간 방향의 계수오차는 아예 제한할 수 없습니다.
7. 축소 강도를 고르는 위험. 결정론적 목표 \(\tau I\)와 알려진 평균 아래 불편 표본공분산 \(S\)에 \(S_\delta=(1-\delta)S+\delta\tau I\)의 Frobenius 위험을 최소화하라.
풀이. \(A=E\|S-\Sigma\|_F^2\), \(B=\|\tau I-\Sigma\|_F^2\)라 하면 교차항은 \(E(S-\Sigma)=0\)으로 사라져 위험은 \((1-\delta)^2A+\delta^2B\). 미분하면 \(\delta^*=A/(A+B)\)이고 \(A=B=0\)이면 모든 강도가 같습니다. Gaussian 표본에서는 \(A=[(\operatorname{tr}\Sigma)^2+\operatorname{tr}\Sigma^2]/n\)입니다.
이는 \(\operatorname{Var}(X_jX_k)=\Sigma_{jj}\Sigma_{kk}+\Sigma_{jk}^2\)를 모든 \(j,k\)에 합해서 얻습니다. 표본으로 추정한 \(\tau=\operatorname{tr}S/p\)는 랜덤이라 이 교차항 계산을 그대로 쓸 수 없습니다. 이 oracle 식을 실제 Ledoit–Wolf 추정량이나 최소분산 포트폴리오 최적 강도와 동일시하지 않습니다.
지금까지의 내용을 수학의 언어로 정리해 봅시다#
한 방향의 꼬리, 유한개의 망점, 모든 방향의 오차라는 연결을 증명합니다. MP·스파이크·유효차원·일반 Hanson–Wright·행렬 Bernstein은 앞에서 출처와 가정을 적은 외부 정리입니다. 아래 증명들은 그 결과를 슬쩍 가정하지 않고 명시한 초등 적분과 유한차원 선형대수에서 출발합니다.
정리 1 · 부가우시안의 동치 조건. 다음은 보편적인 상수배 차이로 동치다: 유한 \(\psi_2\) 노름, \(P(|Z|>t)\le2e^{-t^2/K_1^2}\), 모든 \(q\ge1\)에 \(\|Z\|_{L^q}\le K_2\sqrt q\). 평균 0이면 모든 \(\lambda\in\mathbb R\)에 \(Ee^{\lambda Z}\le e^{K_3^2\lambda^2}\)라는 조건도 동치입니다.
증명. \(Ee^{Z^2/K^2}\le2\)에 Markov를 쓰면 꼬리 경계입니다. 그 꼬리에서 비음수 적분 항등식을 쓰면 \(E|Z|^{2k}=\int_0^\infty2kt^{2k-1}P(|Z|>t)dt\le2K^{2k}k!\). \(k!\le k^k\)와 \(2k\ge q\)인 가장 작은 짝수에 대한 \(L^q\) 노름 단조성으로 \(\|Z\|_q\le CK\sqrt q\). 역으로 모멘트 경계에 지수급수를 적용하면
for \(L^2\ge4eK_2^2\). 여기서 \(\log k!=\sum_{j=1}^k\log j\ge\int_1^k\log t\,dt\ge k\log k-k\)로 factorial 하한을 얻었습니다.
평균 0이고 \(\|Z\|_{\psi_2}\le K\)라 합시다. 독립 복사본 \(Z'\)에 Jensen으로 \(Ee^{\lambda Z}\le Ee^{\lambda(Z-Z')}\). \(W=Z-Z'\)는 대칭이고 \(Ee^{W^2/(4K^2)}\le2\): \((Z-Z')^2\le2Z^2+2Z'^2\)와 독립성·Cauchy–Schwarz를 적용하면 됩니다. 위 꼬리 모멘트 경계는 \(EW^{2k}\le2(4K^2)^kk!\)를 줍니다. 따라서
\((2k)!\ge(k!)^2\)와 \((e^a-1)^2\ge0\)를 썼습니다. 역으로 MGF 경계에 Chernoff를 적용하고 \(\lambda=t/(2K_3^2)\)를 고르면 양쪽 꼬리의 합이 \(2e^{-t^2/(4K_3^2)}\). 평균 0 조건은 필수입니다. 상수 \(Z=1\)은 \(\psi_2\)가 유한하지만 \(e^\lambda\le e^{C\lambda^2}\)를 작은 양의 \(\lambda\)에서 만족하지 않습니다. \(\square\)
정리 2 · 부지수 Bernstein과 명시적 공분산 경계. 위 평균 0 독립 \(W_i\)의 Bernstein 식과 \(p\)-차원 공분산 식이 성립합니다.
증명. \(Ee^{|W|/L}\le2\)에서 \(E|W|^k\le2L^kk!\). 평균 0으로 일차항이 사라져 \(|\lambda|L<1\)이면
독립합의 로그 MGF는 이 값의 \(n\)배 이하. \(t\le4L\)에는 \(\lambda=t/(8L^2)\), \(t>4L\)에는 \(\lambda=1/(2L)\)를 택하면 Chernoff 지수가 각각 \(-nt^2/(16L^2)\) 이하, \(-nt/(4L)\) 이하가 됩니다. \(-W_i\)에도 적용하여 양쪽을 합칩니다.
중심화는 \(\psi_1\) 노름을 최대 두 배 키웁니다. 독립 복사본 \(V'\)와 Jensen으로 \(E\exp(|V-EV|/(2K))\le E\exp(|V-V'|/(2K))\le(Ee^{|V|/(2K)})^2\le2\) for \(\|V\|_{\psi_1}\le K\).
따라서 \(W_i=(u^TX_i)^2-u^T\Sigma u\)에는 \(L=2K^2\|\Sigma\|\)를 공통으로 쓸 수 있습니다. 각 망점의 편차에 \(t=4L(\sqrt{a/n}+a/n)\)를 넣으면 \(n\min\{t^2/(16L^2),t/(4L)\}\ge a\). 최대 \(9^p\)점 합집합 확률은 \(2\cdot9^pe^{-a}=\eta\). 본문의 망 보조정리가 작용소노름을 \(2t\) 이하로 바꾸어 줍니다. \(\Sigma=0\)이면 \(X=0\) a.s.여서 자명하고 그 외 경우에 위 계산을 적용합니다. \(\square\)
정리 3 · Gaussian 이차형식. 본문의 Frobenius·작용소노름 두 척도 경계가 성립합니다.
증명. \(a=\|A\|_F\), \(b=\|A\|\)라 합시다. 정규벡터의 직교회전 불변성으로 독립 \(Z_j\)에 \(Q=\sum\lambda_j(Z_j^2-1)\). \(|t|<1/(2b)\)에서 Gaussian 적분과 로그급수로
각 급수의 \(k\ge2\) 항 계수 \(2^{k-1}/k\le2^{k-2}\)와 \(|\lambda_j|^k\le\lambda_j^2 b^{k-2}\)를 썼습니다. \(a>0,u>0\)에서 \(t=\sqrt u/(a+2b\sqrt u)\)를 넣으면 \(-t(2a\sqrt u+2bu)+t^2a^2/(1-2bt)=-u\). 음의 꼬리에는 \(-A\)를 적용합니다. \(A=0\)인 경우는 즉시 성립합니다. \(\square\)
정리 4 · Gaussian JL와 부분공간 보존. 본문에 표시한 \(m\)의 충분조건 아래 유한 점 쌍과 고정 부분공간의 제곱노름 보장이 각각 확률 \(1-\eta\) 이상으로 성립합니다.
증명. \(\chi_m^2\)의 MGF를 Chernoff 최적값에 대입하면 위쪽 꼬리는 \(\exp[-m(\epsilon-\log(1+\epsilon))/2]\), 아래쪽은 \(\exp[-m(-\epsilon-\log(1-\epsilon))/2]\) 이하. \(0<\epsilon<1\)에서 첫 괄호는 \(\int_0^\epsilon t/(1+t)dt\ge\epsilon^2/4\), 둘째는 \(\int_0^\epsilon t/(1-t)dt\ge\epsilon^2/2\)입니다. 따라서 두 꼬리의 합은 \(2e^{-m\epsilon^2/8}\). 고정 \(x\)의 정규 분포와 \(N(N-1)/2\)개 비영 차이에 합집합 경계를 적용하면 JL 조건이 나옵니다. 같은 점끼리의 영 차이는 자동 보존됩니다.
부분공간에서는 \(U^TR^TRU-I\)라는 대칭 \(k\times k\) 행렬의 \(1/4\)-망을 잡습니다. 각 점에 편차 \(\epsilon/2\)를 사용하면 실패확률은 최대 \(2\cdot9^k e^{-m\epsilon^2/32}\). 이를 \(\eta\) 이하로 하고 망 보조정리의 배수 2를 적용하면 전체 부분공간에서 왜곡 \(\epsilon\)입니다. 본문의 세 단계 최소제곱 부등식에 이 사건을 적용하면 목적함수 보장도 따릅니다. \(\square\)
고차원에서는 고정된 방향의 오차와 모든 방향에서 동시에 성립하는 오차를 구별해야 합니다. 다음 장에서는 사영·쌍대성·분리의 관점으로 효율적 추정과 부분식별, 자산가격의 문제를 연결합니다. I5로 이어 읽기.