Johnson–Lindenstrauss와 거리 보존

유한 점 집합의 거리를 함께 보존하기

Johnson–Lindenstrauss의 핵심은 고정한 유한 점 집합의 모든 쌍 거리를 작은 상대 오차로 보존하는 선형 사상입니다. 보통 필요한 출력 차원은 점 개수의 로그와 허용 오차의 역제곱에 의존합니다. 여기서는 노름이 아니라 거리의 제곱에 (1±ε) 허용 범위를 적용합니다.

실습은 R¹²⁸의 네 점 0,e₁,e₂,모든 좌표가 1/√128인 점을 사용합니다. 전체 점은 투영 행렬을 정하기 전에 고정되어 있습니다. 여섯 쌍의 원래 거리 제곱과 투영 뒤 비율을 표에 기록합니다.

왜 1/√m로 나눌까

이상적 행렬 A의 각 원소가 독립 N(0,1/m)이면 고정 벡터 v에 대해 ||Av||²/||v||²은 χ²ₘ/m을 따릅니다. 따라서 기대 제곱 노름이 보존됩니다. 한 쌍의 평균 보존은 모든 쌍이 동시에 가까운 것과 다르므로 꼬리 경계가 필요합니다.

한 쌍에서 여섯 쌍으로

0<ε<1에서 Gaussian 제곱 노름의 꼬리는 2exp[−m(ε²/4−ε³/6)]로 상계할 수 있습니다. 여섯 쌍에 union bound를 적용하면 다음 값이며, 확률 표시에서는 1과의 최솟값을 씁니다.

실패확률을 .05 이하로 만드는 충분한 m은 ln(12/.05)을 괄호의 계수로 나눈 값의 올림입니다. 충분조건이므로 실제로 필요한 최소 차원은 아닙니다. 이 네 점은 작은 부분공간에 있으므로 일반 경계가 보수적일 수 있습니다.

Seed의 실현과 확률 보장 구분

화면은 seed를 고정한 유사난수와 Box–Muller 변환으로 재현 가능한 행렬을 만듭니다. 이는 이상적인 독립 Gaussian 추출의 수학적 보장과 구분해야 합니다. seed를 바꾸면 실제 오차는 바뀌지만 같은 m,ε의 이론 상계는 같습니다. 한 seed가 실패하거나 성공해도 정리를 증명하거나 반박한 것은 아닙니다.

파랑 점은 쌍별 비율이고 주황 수평선은 1과 1±ε입니다. 연결선은 쌍 번호를 따라 읽도록 돕는 것이며 확률밀도 곡선이 아닙니다. 제곱 거리 오차와 원래 거리 오차의 ε를 같은 값으로 혼용하지 마세요.

적용 범위

이 보장은 미리 고정한 유한 점 집합에 대한 것입니다. 행렬을 본 뒤 악의적으로 점을 고르거나 전체 연속 공간의 모든 벡터를 저차원으로 등거리 보존한다는 주장은 아닙니다. 학습·검색 성능도 거리 보존만으로 자동 보장되지는 않습니다.

확인 문제와 해설

1. 행렬 배율은? 표준 Gaussian 원소를 √m으로 나눕니다.
2. 현재 실습의 점 쌍은 몇 개인가요? 6개입니다.
3. 실패 상계 1은 반드시 실패한다는 뜻인가요? 아니요. 이 설정에서 경계가 자명하다는 뜻입니다.

추가 읽기: Stanford CS 368, Lecture 4 — Johnson–Lindenstrauss.