차원의 저주와 유효 차원

각 좌표의 작은 비용이 곱해질 때

각 좌표에 q개 후보를 놓는 d차원 격자는 qᵈ개 점을 가집니다. q=4,d=16만 해도 4,294,967,296개입니다. [0,1]ᵈ의 중심에서 L∞ 반지름 .1인 이웃의 균등 확률도 .2ᵈ로 작아집니다. 이는 특정 격자·거리·균등 분포 모형이며 모든 알고리즘의 필수 비용을 뜻하지는 않습니다.

큰 정수는 JavaScript 부동소수점 정수 정밀도를 넘을 수 있습니다. 수치창은 log₁₀(qᵈ)를 표시하고, 표는 BigInt로 계산한 정확한 십진 문자열을 보여줍니다. q=10,d=32인 10³²도 정확한 문자열로 읽습니다.

주변 차원과 스펙트럼 구조

별도 예제는 공분산의 고유값 λᵢ=ρⁱ⁻¹을 설계합니다. 실제 데이터에서 추정한 값이 아닙니다. ρ=1이면 모든 방향의 크기가 같고, ρ=0이면 첫 방향만 1이고 나머지는 0입니다. 작은 ρ에서는 에너지가 앞의 방향에 모입니다.

서로 다른 유효 차원의 정의

참여 랭크는 (Σλ)²/Σλ²입니다. 공분산의 effective rank는 trace/최대 고유값으로, 여기서는 최대값이 1이라 Σλ입니다. 이는 Gram 스펙트럼이 λ인 데이터 행렬의 stable rank에 대응하지만, 공분산 행렬 자체의 stable rank Σλ²/λmax²와는 다릅니다. Ridge 크기 τ>0를 사용하는 regularized dimension은 Σλ/(λ+τ)입니다.

같은 d에서 다른 구조

d=16,ρ=.5이면 참여 랭크는 약 3입니다. ρ=1로 바꾸면 참여 랭크는 16입니다. 그러나 격자 qᵈ는 ρ와 무관하므로 두 경우 모두 같은 주변 격자 비용을 가집니다. 구조를 활용하는 알고리즘을 설계해야 낮은 유효 차원의 이점이 생길 수 있습니다.

τ가 커지면 약한 고유방향을 더 줄여 ridge dimension도 줄어듭니다. 추정 대상과 정규화 단위 없이 숫자만 비교하면 다른 의미의 차원을 섞게 됩니다. 첫 방향만 활성인 경우에도 ridge dimension은 1/(1+τ)로 1보다 작을 수 있습니다.

구조가 표본 복잡도 보장을 대신하지 않는다

낮은 참여 랭크가 모든 과제의 필요 표본 수를 자동 결정하지는 않습니다. 회귀·분류·복원에서 관측 구조, 잡음, 목표 오차와 식별 가능성이 추가로 필요합니다. 이 그림은 격자 증가와 세 스펙트럼 지표를 비교하는 입문 예제입니다.

확인 문제와 해설

1. q를 두 배로 하면 격자 수는 몇 배인가요? 2ᵈ배입니다.
2. ρ=0의 참여 랭크는? 1입니다.
3. 유효 차원 셋은 언제나 같나요? 아니요. 정의와 정규화에 따라 다릅니다.

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