A Note About Algebraic $(s, t)$-Weak Tractability Of Linear Tensor Product Problems In The Worst-Case Setting

문제 정의
본 논문은 정보 기반 복잡도(Information-Based Complexity, IBC)의 프레임워크 내에서, 특히 최악의 경우(worst-case) 설정을 중심으로 선형 텐서 곱 문제의 계산적 난이도를 다룬다. 연구의 핵심 대상은 힐베르트 공간 사이에서 작용하는 컴팩트 선형 연산자 $S_1$의 $d$-중 텐서 곱으로 정의되는 선형 연산자 시퀀스 $S = \{S_d\}_{d \in \mathbb{N}}$이다. 이 문제들의 복잡도는 절대 오차 $\varepsilon$ 내에서 해를 근사하는 데 필요한 연속 선형 범함수의 최소 평가 횟수인 정보 복잡도 $n(\varepsilon, S_d)$로 측정된다.

본 논문은 특히 **대수적 $(s, t)$-약한 추적 가능성(ALG-$(s, t)$-WT)**을 조사한다. 문제가 ALG-$(s, t)$-WT라는 것은 $\varepsilon^{-1} + d \to \infty$일 때, 정보 복잡도의 로그값이 $\varepsilon^{-s} + d^t$에 대해 하선형(sub-linearly)으로 성장함을 의미한다. 정규화된 오차 기준(normalized error criterion)과 최대 고윳값 제곱 $\lambda_1 \leq 1$인 경우의 절대 오차 기준(absolute error criterion)에 대해서는 ALG-$(s, t)$-WT를 위한 필요충분조건이 이전에 확립되었으나, 중요한 공백이 남아 있었다. 구체적으로, $\lambda_1 > 1$인 경우의 절대 오차 기준에 대해서는 부분적인 결과들만 존재했다. 즉, 별개의 필요조건과 충분조건은 알려져 있었으나, 일변량 특이값(univariate singular values)에 대한 통합된 필요충분조건은 도출되지 않았다.

방법론
저자들은 기초가 되는 연산자의 스펙트럼 성질에 근거한 엄밀한 분석적 접근 방식을 채택한다. 방법론은 다음과 같이 진행된다:

1. 정규화(Normalization): $\lambda_1 > 1$인 경우를 처리하기 위해, 저자들은 $S'_1 = \frac{1}{\sqrt{\lambda_1}}S_1$인 정규화된 문제 $S' = \{S'_d\}$를 도입한다. 이 변환을 통해 정규화된 연산자의 고윳값이 $\lambda'_1 = 1$을 만족하게 되어, 정규화된 오차 기준에 관한 기존 결과들과의 비교가 용이해진다.
2. 정보 복잡도 경계(Information Complexity Bounds): 본 논문은 정보 복잡도와 연산자의 특이값 사이의 관계를 활용한다. 절대 오차 기준의 경우, 복잡도는 고윳값의 곱이 특정 임계값을 초과하는 다중 인덱스(multi-indices) $(j_1, \dots, j_d)$의 개수와 연결된다.
3. 조합론적 추정(Combinatorial Estimation): 핵심적인 기술적 도구는 순열과 조합을 사용하여 $n_{NOR}(\varepsilon, S'_d)$의 상한을 제공하는 보조정리(Lemma) 2.2이다. 이 상한은 고윳값이 1보다 작은 인덱스의 수 $a_\varepsilon(d)$와 일변량 계수 함수(univariate counting function) $j(\varepsilon)$에 의존한다.
4. 점근적 분석(Asymptotic Analysis): 저자들은 $\varepsilon \to 0$일 때 계수 함수 $j(\varepsilon)$(고윳값이 $\varepsilon^2$보다 큰 고윳값의 개수)의 점근적 거동을 분석한다. 이들은 보조정리 2.1을 통해 고윳값의 붕괴율(decay rate)과 $j(\varepsilon)$의 성장 사이의 동치 관계를 확립한다.
5. 극한 평가(Limit Evaluation): 유도된 경계값들을 ALG-$(s, t)$-WT의 정의에 대입함으로써, 저자들은 비율 $\frac{\ln n(\varepsilon, S_d)}{\varepsilon^{-s} + d^t}$의 극한을 평가하여 해당 값이 0이 되는 조건을 결정한다.

주요 기여 및 결과
본 연구의 주요 기여는 $\lambda_1 > 1$인 경우의 절대 오차 기준 하에서 선형 텐서 곱 문제에 대한 ALG-$(s, t)$-WT 문제를 해결한 것이다.

• 정리 1.1: 본 논문은 이 특정 설정에서의 ALG-$(s, t)$-WT에 대한 필요충분조건을 확립한다. 문제 $S$가 ALG-$(s, t)$-WT이기 위한 필요충분조건은 다음과 같다:

  1. $t > 1$; 그리고
  2. 일변량 특이값 $\{\lambda_j\}$가 다음의 붕괴 조건을 만족해야 한다:
     $$\lim_{j \to \infty} \frac{(\ln \frac{1}{\lambda_j})^t}{\ln j} = \infty.$$

• 공백의 해결: 이 결과는 (특히 Siedlecki와 Weimar [15]에서) 별개의 필요 및 충분조건을 제공했으나 $\lambda_1 > 1$인 경우에 대해 이를 하나의 특성으로 통합하는 데 실패했던 기존 연구의 공백을 메운다.

• 매개변수 독립성(Parameter Independence): 저자들은 $\lambda_1 > 1$인 경우의 절대 오차 기준에서 흥미로운 발견을 강조한다. 즉, 이 경우의 추적 가능성 조건은 오직 매개변수 $t$(조건 $t > 1$ 요구)와 고윳값의 붕괴에만 의존한다. $\lambda_1 \leq 1$이거나 정규화된 오차 기준인 경우와 달리, 고윳값 붕괴에 대한 필요충분조건에는 매개변수 $s$가 나타나지 않는다.

• 지수적 추적 가능성과의 관계: 본 논문은 지수적 추적 가능성(EXP-tractability)과의 연결성을 언급한다. $\lambda_1 > 1$이고 ABS인 경우, 문제 $S$가 ALG-$(s, t)$-WT인 것은 $S$가 ALG-$(t, t)$-WT인 것과 동치이며, 또한 $s > t$인 ALG-$(s, t)$-EXP-WT인 것과도 동치이다.

의의
본 논문은 이전에 부분적으로만 이해되었던 문제군에 대해 대수적 약한 추적 가능성의 완전한 특성화를 제공함으로써 그 의의를 주장한다. [15]에서 도출된 조건(이전에는 필요조건으로만 알려졌던)이 또한 충분조건임을 증명함으로써, 저자들은 다변량 근사 연구의 이론적 공백을 메운다. 연구 결과는 매개변수 $s, t$와 연산자의 스펙트럼 붕괴의 역할을 명확히 하며, $\lambda_1 > 1$인 경우 $t > 1$을 만족하는 한 고윳값이 충분히 빠르게 붕괴하도록 보장함으로써 "차원의 저주"를 (약한 의미에서) 극복할 수 있음을 보여준다.