기술 요약: 저계수 분포 행렬 완성 (Low-rank Distributional Matrix Completion)

문제 정의

본 논문은 고전적인 저계수 행렬 완성(low-rank matrix completion) 과업의 일반화인 분포 행렬 완성(distributional matrix completion) 문제를 다룬다. 이 설정에서 대상 행렬 $\rho^* \in \mathcal{P}(\mathcal{X})^{m_1 \times m_2}$는 스칼라 값이 아닌, 도메인 $\mathcal{X}$ 상의 확률 분포를 엔트리로 가진다.

관측 모델은 두 가지 층위의 불완전성을 특징으로 한다:

1. 부분 관측 (Partial Observation): 이진 마스크 $T(i,j)$에 의해 표시된 것처럼, 행렬 엔트리의 일부만 관측된다.
2. 간접 관측 (Indirect Observation): 관측된 엔트리라 할지라도, 기저의 분포 $\rho^*(i,j)$에 직접 접근할 수 없다. 대신, $\rho^*(i,j)$로부터 추출된 유한한 i.i.d. 샘플 집합 $\{X^{(ij)}_1, \dots, X^{(ij)}_{N_{ij}}\}$을 관측한다. 여기서 샘플 크기 $N_{ij}$는 엔트리마다 다를 수 있다.

목표는 이러한 부분적이고 간접적인 관측으로부터 전체 분포값 행렬 $\rho^*$(또는 그 표현식)을 복원하는 것이다. 이 문제는 위치 간 교통 흐름의 변동성을 모델링하거나, 서로 다른 회계 분기 및 기관 간의 수익 예측 분포를 분석하는 등의 응용 분야에서 발생한다.

방법론

커널 평균 임베딩 (Kernel Mean Embeddings, KME)

무한 차원의 확률 분포를 다루고 밀도 함수와 관련된 매니폴드 제약을 피하기 위해, 저자들은 재생 커널 힐베르트 공간(RKHS) $\mathcal{H}$ 내의 **커널 평균 임베딩(KME)**을 통해 각 분포 $\rho^*(i,j)$를 표현한다:
$$\mu^*(i, j, \cdot) = \mathbb{E}_{X \sim \rho^*(i,j)} [K(X, \cdot)] \in \mathcal{H}$$
$\rho^*$를 복원하는 것은 KME 행렬 $\mu^* \in \mathcal{H}^{m_1 \times m_2}$를 복원하는 것과 같다. 분포 간의 거리는 최대 평균 불일치(Maximum Mean Discrepancy, MMD)를 사용하여 측정된다.

함수적 언폴딩을 통한 저계수 모델링 (Low-Rank Modeling via Functional Unfolding)

저자들은 분포 행렬에 대한 터커 계수(Tucker rank) 구조를 제안한다. 이들은 $\mu^*$를 $\mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H}$ 공간의 3차 텐서로 간주한다. $\mathcal{H}$는 종종 무한 차원이므로, 표준적인 텐서 계수 정의를 직접 적용할 수 없다.

이를 해결하기 위해, 저자들은 텐서를 두 공간의 곱으로 매핑하는 함수적 언폴딩 연산자(functional unfolding operators, $U_1, U_2, U_3$)를 도입한다 (예: $U_1: \mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H} \to \mathbb{R}^{m_1} \otimes (\mathbb{R}^{m_2} \otimes \mathcal{H})$). 이러한 연산자들은 그 계수를 다선형 계수(multilinear rank) $(r_1, r_2, r_3)$로 정의하는 선형 연산자를 유도한다.

• 구조적 함의: 낮은 다선형 계수는 KME의 함수적 성분들이 저차원 부분 공간에 존재하며, 관련 기대 함수 행렬(예: 평균 행렬)이 저계수임을 의미한다.

추정 프레임워크

저자들은 핵 노름(nuclear-norm) 페널티가 포함된 손실 함수를 최소화하는 정규화된 M-추정량 $\hat{\mu}$를 제안한다:
$$\hat{\mu} = \arg\min_{\mu} \left[ \frac{1}{m_1 m_2} \sum_{(i,j): T(i,j)=1} \left\| \mu(i, j, \cdot) - \hat{\mu}_{emp}(i, j, \cdot) \right\|_{\mathcal{H}}^2 + \lambda \Psi(\mu) \right]$$

• 손실 항 (Loss Term): 추정된 KME와 관측된 샘플로부터 유도된 경험적(empirical) KME 사이의 제곱 MMD이다.
• 정규화 (Regularization): $\Psi(\mu) = \sum_{j=1}^3 \beta_j \|U_j \mu\|_*$이며, 여기서 $\|\cdot\|_*$는 유도된 선형 연산자의 핵 노름을 나타낸다. 이는 세 가지 모드 모두에 대해 저계수성을 촉진한다.

계산 솔루션

$\mathcal{H}$의 무한 차원적 특성에도 불구하고, **표현 정리(Representer Theorem)**는 해 $\hat{\mu}$가 관측된 커널 함수의 유한 차원 스팬(span) 내에 존재함을 보장한다.

1. 문제는 계수 텐서 $B \in \mathbb{R}^{m_1 \times m_2 \times \tilde{N}}$에 대한 유한 차원 텐서 최적화 문제로 재매개변수화된다.
2. 대규모 샘플 크기를 처리하기 위해, 저자들은 커널 근사 기법(예: Nyström 방법 또는 Random Fourier Features)을 사용하여 그램 행렬(Gram matrix)을 근사하는 것을 제안한다.
3. 최적화는 가속된 **ADMM(Alternating Direction Method of Multipliers)**을 사용하여 해결된다.

주요 기여

1. 새로운 문제 정식화: 부분적이고 노이즈가 있는 샘플 데이터로부터 분포를 복구하는 과제를 해결함으로써, 분포값 엔트리를 가진 행렬 완성을 공식화하였다.
2. 이론적 프레임워크: 함수적 언폴딩 연산자를 사용하여 분포값 텐서에 대한 터커 계수 정의를 도입함으로써, 무한 차원 함수 데이터와 유한 차원 텐서 분석 사이의 간극을 메웠다.
3. 알고리즘 혁신: 제안된 추정량은 유도된 선형 연산자에 대한 핵 노름 정규화를 활용한다. 결정적으로, 저자들은 해가 유한 차원 표현을 가짐을 증명하여, 이 문제가 볼록 최적화(convex optimization)를 통해 계산 가능함을 보여주었다.
4. 통계적 보장: 합계 제곱 MMD에 대한 비점근적 오차 경계(non-asymptotic error bounds)를 설정하였다.
   • 수렴 속도는 스칼라 행렬에 대한 고전적인 핵 노름 정규화 행렬 완성과 일치한다.
   • 기존의 최근접 이웃(nearest-neighbor) 방식(예: Feitelberg et al., 2024)과 달리, 제안된 방법의 일관성(consistency)은 엔트리당 샘플 수($N_{ij}$)가 발산할 필요가 없다. 대신, 행렬의 차원($m_1, m_2$)이 커짐에 따라 정보 공유를 활용하여 저계수 구조를 통해 일관성을 달성한다.

실험 결과

합성 데이터 (Synthetic Data)

• 설정: 가우시안 혼합 분포를 가진 시뮬레이션 행렬을 사용하였다. 최근접 이웃(NN) 방법(Feitelberg et al., 2024) 및 샘플 평균/분산에 적용된 고전적 행렬 완성(SOFTIMPUTE)과 비교하였다.
• 결과:
  • 제안된 방법(LRKME)은 관측된 엔트리와 미관측 엔트리 모두에서, 특히 분산 및 고차 통계량을 추정할 때 NN 방법을 지속적으로 능가하였다.
  • LRKME는 단순한 스칼라 요약 대신 전체 분포 정보를 활용하는 것의 이점을 입증하며 SOFTIMPUTE보다 우수한 성능을 보였다.
  • 2D 설정에서는 다변량 와서스테인(Wasserstein) 거리의 계산적 불가능성으로 인해 NN 방법이 제외되었으나, LRKME는 여전히 효과적이었다.

실제 응용 (Real-World Application)

• 데이터셋: 265개의 출발지 및 목적지 위치 간의 일일 통행 횟수 분포를 모델링한 NYC 택시 운행 데이터.
• 과제: 높은 결측률(>39%)과 엔트리별 매우 가변적인 샘플 크기(1 ~ 372개).
• 결과: LRKME는 테스트 세트에서 NN 방법(0.0212)에 비해 현저히 낮은 경험적 상대 오차(0.0015)를 달성하였다. 특정 사례에 대한 시각적 검토 결과, LRKME는 NN 추정기에 비해 헤비 테일(heavy-tailed) 분포와 집중 패턴을 더 잘 포착하였다.

의의 및 주장

본 논문은 다음과 같은 기능을 갖춘 최초의 분포 행렬 완성 방법을 제공한다고 주장한다:

1. 다양한 샘플 크기를 가진 일반적인 관측 패턴을 수용한다.
2. 와서스테인 기반 방법의 계산적 병목 현상 없이 다차원 분포로 자연스럽게 확장된다.
3. 엔트리당 샘플의 점근적 증가에 의존하지 않고, 행렬의 저계수 구조를 활용하여 전역적 일관성 보장을 제공한다.
4. 유한 차원 표현과 볼록 최적화를 통해 계산 효율적인 솔루션을 제공한다.

저자들은 자신들의 연구가 기존의 최근접 이웃 방식에서 한 단계 나아가, 더 견고하고 이론적으로 근거가 있으며 확장 가능한 프레임워크를 제공한다고 강조한다.