Gaussian Width와 집합의 기하

주변 차원만으로 집합의 복잡도를 알 수 있을까

같은 Rᵈ 안에서도 한 방향만 있는 집합과 모든 방향을 포함한 집합은 다릅니다. Gaussian width는 표준 Gaussian 방향 g로 집합을 바라볼 때 가능한 최대 내적의 평균입니다. 이 단원은 다음 관례를 사용합니다. 어떤 문헌의 차이 집합 폭은 다른 배율을 가질 수 있습니다.

축의 양끝점과 전체 구면

축 집합 T={±Reᵢ}는 2d개의 점이고 최댓값은 R maxᵢ|gᵢ|입니다. 전체 반지름 R 구면은 g의 방향으로 정렬할 수 있어 최댓값이 R||g||₂입니다. 같은 주변 차원과 반지름이어도 두 기하가 다릅니다.

기대값을 실제로 계산하기

최대 절대 좌표의 생존함수는 1−P(|G|≤t)ᵈ입니다. 비음수 변수의 평균은 생존함수 적분이므로 이 식을 [0,10]에서 수치 적분합니다. 정규 CDF도 수치 근사이며 바깥 꼬리는 매우 작지만 값은 근사로 표시합니다.

구면 폭은 chi 분포 평균을 사용합니다. d=1에서는 √(2/π), d=2에서는 √(π/2)이고 두 차원씩 올리는 recurrence로 계산합니다. d=1의 두 집합은 같은 ±R이므로 폭도 같습니다. 단일 seed의 최대값을 기대 폭으로 바꾸어 쓰지 않습니다.

두 가지 상한과 차원 증가

Jensen으로 E||g||≤√E||g||²=√d입니다. 축 집합은 2d개 부호 방향의 Gaussian 최대값에 대한 상계 √(2ln(2d))를 사용할 수 있습니다. 따라서 축 집합의 폭은 대략 √log d, 구면은 √d 규모로 다르게 증가합니다. 유한 차원에서의 정확한 등식이라는 뜻은 아닙니다.

파랑·주황 곡선은 두 폭을 차원에 따라 비교합니다. 집합 선택 조절기는 두 곡선을 지우지 않고 현재 폭과 점의 위치만 바꿉니다. R을 곱하면 두 폭도 같은 배율로 늘어납니다.

연구에서의 쓰임과 범위

제약 집합의 폭은 무작위 측정·추정 오차·표본 복잡도에 나타날 수 있습니다. 다만 모든 문제의 필요 표본 수가 무조건 w²라는 뜻은 아닙니다. 관측 모형·잡음·허용 오차·국소화 등 각 정리의 조건이 필요합니다. Covering number와도 연결되지만 같은 이름의 양은 아니며 실제 집합의 기하를 명시해야 합니다.

확인 문제와 해설

1. g는 집합에서 뽑은 균등 점인가요? 아니요. 표준 Gaussian 벡터입니다.
2. 반지름을 두 배로 하면 폭은? 두 배입니다.
3. 같은 주변 차원이 같은 폭을 뜻하나요? 아니요. 방향 구조가 다릅니다.

추가 읽기: Vershynin, High-Dimensional Probability — publisher’s page.