텐서 트레인 (Tensor Train) 랜덤 벡터를 이용한 확률적 트레이스 추정 (Stochastic trace estimation)

확률적 트레이스 추정 (Stochastic trace estimation)은 행렬-벡터 곱 (matrix-vector products)을 통해서만 접근 가능한 대규모 행렬의 트레이스 (trace)를 근사하기 위한 표준적인 도구입니다. 그러나 텐서 구조화된 (tensor-structured) 환경에서는, 구조화되지 않은 가우시안 (Gaussian) 또는 라데마허 (Rademacher) 테스트 벡터를 저장하고 계산하는 비용이 지나치게 높을 수 있는 반면, 더 저렴한 랭크-1 (rank-one) 텐서 곱 벡터는 텐서 차수 (tensor order)에 따라 지수적으로 증가하는 샘플 복잡도 (sample complexities)를 요구할 수 있습니다. 본 연구에서는 확률적 트레이스 추정을 위한 구조화된 대안으로서 가우시안 랜덤 텐서 트레인 (tensor train) 벡터를 연구합니다. 우리는 적절한 텐서 트레인 랭크 (tensor train rank)를 선택하면, 랜덤 텐서 트레인 벡터가 Girard--Hutchinson 추정기에 대해 차원에 독립적인 보장 (dimension-independent guarantees)을 회복함을 보여줍니다. 특히, 텐서 트레인 랭크 $r \geq d-1$인 평균의 중앙값 (median-of-means) 변형은 구조화되지 않은 가우시안 벡터에 기반한 고전적 추정기와 동일한 정확도 $\varepsilon$ 및 실패 확률 $\delta$에 대한 의존성을 달성합니다. 나아가 우리는 독립적인 가우시안 랜덤 텐서 트레인 벡터로 형성된 스케치 (sketches)에 대한 망각적 부분 공간 주입 (oblivious subspace injection) 결과를 증명합니다: $k$차원 타겟 부분 공간 (target subspace)을 위해 텐서 트레인 랭크 $r\geq d-1$ 및 $\mathcal{O}(\varepsilon^{-2}(k+\log(1/\delta)))$개의 샘플이면 충분합니다. 마지막으로, Nyström++ 프레임워크 내에서 이러한 스케치의 사용을 조사합니다. 우리는 추가적인 스펙트럼 꼬리 조건 (spectral-tail condition) 하에서 결과적인 추정기가 원하는 $\mathcal{O}(\varepsilon^{-1})$ 샘플 복잡도를 달성할 수 있음을 보여줍니다. 이러한 결과들은 확률적 트레이스 추정에서 랜덤 텐서 트레인 벡터의 잠재력과 한계 모두에 대한 명확한 설명을 제공합니다.