혼합 곱분포 간의 총 변동 거리 계산에 관한 연구
요약
본 논문은 n차원 이산 도메인 위의 두 혼합 곱분포 간의 총 변동 거리(Total Variation Distance, TV distance)를 근사하는 확률적 알고리즘을 제시합니다. 특히 k_1개의 곱분포를 가진 혼합 분포 P와 Q에 대해 시간 복잡도 poly((nq)^{k_1+k_2}, 1/ε) 내에 높은 정확도로 TV 거리를 추정할 수 있음을 보였습니다. 또한, Boolean 서브큐브 혼합 분포의 특수한 경우에 대해서는 결정적 알고리즘을 제공하고, 이 계산이 #P-난해임을 입증했습니다.
핵심 포인트
- n차원 이산 도메인 위의 두 혼합 곱분포 간의 총 변동 거리(TV distance)를 다룸.
- 일반적인 경우에 대해 시간 poly((nq)^{k_1+k_2}, 1/ε) 내에 TV 거리를 근사하는 확률적 알고리즘을 제공함.
- Boolean 서브큐브 혼합 분포의 특수한 경우에는 결정적 알고리즘을 제시함.
- 이 특수 클래스에서 총 변동 거리 계산이 #P-난해(hard)임을 증명하여 계산 복잡도의 한계를 설정함.
우리는 n 차원 이산 도메인 위의 두 혼합 곱분포 간의 총 변동 거리 (Total Variation Distance, TV distance) 를 근사하는 문제를 다룹니다. [q]^n 위에서 k_1 개의 곱분포를 가진 혼합 분포 P 와 Q 가 주어졌을 때, 우리는 시간 poly((nq)^{k_1+k_2}, 1/ε) 내에 (1±ε) 배의 오차로 d_TV(P,Q) 를 근사하는 확률적 알고리즘을 제공합니다. 또한 {0,1}^n 위의 Boolean 서브큐브 혼합 분포의 특수한 경우를 다룹니다. 이 클래스에 대해 우리는 시간 poly(n, 2^{O(k_1+k_2)}) 내에 총 변동 거리를 정확히 계산하는 결정적 알고리즘을 제공하며, k_1+k_2=Θ(n) 일 때 정확한 계산이 #P-난해임을 보여줍니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기