선형 쿼리(Linear Queries)를 통한 최적 재구성

우리는 근사적인 선형 쿼리(linear queries)로부터 $\mathbb{R}^d$ 공간 내의 미지의 점을 재구성하는 문제를 연구합니다. 이러한 설정은 저차원 원격 탐사(remote sensing) 및 신호 복구(signal recovery)부터 고차원 데이터 분석 및 개인정보 보호가 중요한 추론(privacy-sensitive inference)에 이르기까지 다양한 응용 분야에서 자연스럽게 발생합니다. 우리의 주요 목표는 쿼리 횟수 $T$, 주변 차원(ambient dimension) $d$, 그리고 노이즈 파라미터 $\delta$의 함수로서 최적 재구성 오차(optimal reconstruction error)를 규명하는 것입니다. 먼저 $T \to \infty$인 극한 상황을 분석하여, 최적 재구성 오차가 $\sqrt{2d/(d+1)} \delta$라는 명시적인 값으로 수렴함을 보여줍니다. 이 값은 지도 학습(supervised learning)에서의 베이즈 최적 오차(Bayes optimal error)와 유사한 역할을 합니다. 차원이 고정되었을 때, 우리는 이 극한값 이상의 초과 오차(excess error)가 $T \to \infty$에 따라 이중 지수적으로(doubly exponentially) 빠르게 감소함을 보여주며, 이는 일반적으로 학습 곡선(learning curves)에서 접하는 속도보다 현저히 빠릅니다. 차원이 증가할 때, 우리는 초과 오차를 소멸시키기 위해 $\exp(d)$ 차수의 쿼리 횟수가 필요충분조건임을 보여줍니다. 마지막으로, 재구성 문제의 부적절한 변형(improper variant)을 도입하고 분석합니다. 기술적인 관점에서 우리의 주요 기여는 Jung의 정리(Jung's theorem, 1901)를 일반화한 것입니다. 고전적인 정리는 지름이 1인 집합의 가능한 최대 반지름을 제한하고 극한체(extremal bodies)를 규명합니다. 우리의 일반화는 근사적 극한체(near-extremal bodies)를 규명하는 강건한 변형을 제공하며, 이는 대칭성과 리 군(Lie group) 작용을 활용한 기하학적 및 동역학적 논증을 통해 증명됩니다.